Typescript 5.5 performance regression on arktype

[DanielRosenwasser]

It seems likely it was #58337 that was responsible for the performance hit in https://github.com/arktypeio/arktype

{
    "checkTime": 9.68,
    "types": 483415,
    "instantiations": 2629152
}

devDependencies:
- typescript 5.5.0-dev.20240429
+ typescript 5.5.0-dev.20240430

{
    "checkTime": 12.2,
    "types": 514846,
    "instantiations": 2819487
}

(previously incorrectly attributed it to #58372)

Originally posted by @ssalbdivad in #58337 (comment)

[DanielRosenwasser]

I tried to do a quick profile to look for major differences. Here's what I'm seeing:

5.4.5

      flat  flat%   sum%        cum   cum%
     1.46s  7.20%  7.20%      1.46s  7.20%  (garbage collector)
     1.18s  5.83% 13.03%      3.55s 17.47%  createUnionOrIntersectionProperty
     0.65s  3.20% 16.23%      4.12s 20.33%  getUnionOrIntersectionProperty
     0.53s  2.63% 18.87%      2.08s 10.25%  getPropertyOfType
     0.38s  1.85% 20.72%      0.66s  3.27%  getIntersectionType
     0.38s  1.85% 22.57%      8.36s 41.18%  recursiveTypeRelatedTo
     0.35s  1.73% 24.31%      1.68s  8.27%  getObjectTypeInstantiation
     0.35s  1.72% 26.02%     11.32s 55.77%  instantiateTypeWorker
     0.31s  1.55% 27.57%      1.23s  6.07%  getUnionTypeWorker
     0.31s  1.51% 29.09%      9.43s 46.48%  checkTypeRelatedTo
     0.27s  1.31% 30.40%      4.19s 20.63%  invokeOnce
     0.26s  1.30% 31.70%      9.21s 45.38%  isRelatedTo
     0.23s  1.13% 32.83%      4.37s 21.56%  getPropertiesOfUnionOrIntersectionType
     0.21s  1.03% 33.86%      1.45s  7.13%  getUnionType
     0.20s  0.98% 34.84%     10.59s 52.17%  getConditionalTypeInstantiation
     0.19s  0.95% 35.79%      0.38s  1.86%  addTypesToUnion
     0.18s   0.9% 36.69%      0.19s  0.92%  addTypeToUnion
     0.18s   0.9% 37.59%      0.24s  1.17%  getUnionTypeFromSortedList
     0.18s  0.89% 38.48%      4.48s 22.08%  inferFromTypes
     0.17s  0.86% 39.34%      0.17s  0.86%  getStringLiteralType
     0.17s  0.85% 40.19%      8.10s 39.92%  structuredTypeRelatedToWorker
     0.17s  0.83% 41.02%      0.32s  1.56%  getTemplateLiteralType
     0.16s  0.81% 41.83%      7.76s 38.26%  getConditionalType
     0.16s  0.76% 42.60%      1.92s  9.45%  resolveStructuredTypeMembers
     0.15s  0.75% 43.35%      0.15s  0.75%  getTypeListId
     0.14s   0.7% 44.05%      0.84s  4.15%  getTypeFromTypeNode
     0.14s   0.7% 44.75%      0.76s  3.75%  getUnmatchedProperties
     0.14s  0.68% 45.43%      0.26s  1.27%  getAllocationProfile
     0.14s  0.68% 46.11%      0.14s  0.68%  wrapSafe
     0.13s  0.64% 46.75%      2.79s 13.75%  getIndexedAccessTypeOrUndefined
     0.12s  0.59% 47.34%      0.12s  0.59%  monitorOutOfMemory
     0.12s  0.57% 47.92%     11.27s 55.54%  instantiateType
     0.11s  0.56% 48.48%      0.17s  0.82%  scan
     0.11s  0.56% 49.04%      2.27s 11.21%  some
     0.11s  0.54% 49.57%      0.19s  0.95%  isDeeplyNestedType
     0.11s  0.54% 50.11%      8.96s 44.18%  isTypeRelatedTo
     0.11s  0.52% 50.63%      0.11s  0.52%  arrayFrom
     0.10s  0.51% 51.14%      0.13s  0.63%  createTypeReference
     0.10s  0.49% 51.63%      0.20s  0.97%  createInstantiatedSymbolTable
     0.10s  0.47% 52.10%      8.18s 40.31%  structuredTypeRelatedTo

5.6.0-dev.20240607

      flat  flat%   sum%        cum   cum%
     1.45s  6.95%  6.95%      1.45s  6.95%  (garbage collector)
     1.21s  5.82% 12.77%      3.52s 16.85%  createUnionOrIntersectionProperty
     0.67s  3.22% 15.99%      4.07s 19.49%  getUnionOrIntersectionProperty
     0.56s  2.71% 18.69%      2.16s 10.37%  getPropertyOfType
     0.45s  2.18% 20.87%      5.25s 25.17%  invokeOnce
     0.42s  2.01% 22.88%      9.27s 44.45%  recursiveTypeRelatedTo
     0.41s  1.95% 24.83%     12.35s 59.17%  instantiateTypeWorker
     0.37s  1.79% 26.62%      1.73s  8.28%  getObjectTypeInstantiation
     0.36s  1.70% 28.32%      0.68s  3.28%  getIntersectionType
     0.36s  1.70% 30.03%      1.30s  6.22%  getUnionTypeWorker
     0.28s  1.34% 31.37%     10.17s 48.76%  isRelatedTo
     0.27s  1.31% 32.68%     10.34s 49.54%  checkTypeRelatedTo
     0.23s  1.08% 33.77%      0.44s  2.11%  addTypesToUnion
     0.22s  1.06% 34.83%     11.69s 56.03%  getConditionalTypeInstantiation
     0.22s  1.06% 35.89%      4.31s 20.67%  getPropertiesOfUnionOrIntersectionType
     0.21s  1.02% 36.91%      0.21s  1.03%  addTypeToUnion
     0.20s  0.96% 37.87%      0.41s  1.96%  getTemplateLiteralType
     0.20s  0.96% 38.82%      1.50s  7.20%  getUnionType
     0.20s  0.95% 39.78%      0.40s  1.92%  isDeeplyNestedType
     0.19s  0.92% 40.70%      9.12s 43.69%  getConditionalType
     0.18s  0.86% 41.56%      5.53s 26.50%  inferFromTypes
     0.17s  0.83% 42.39%      0.22s  1.07%  getUnionTypeFromSortedList
     0.17s  0.81% 43.20%      9.04s 43.32%  structuredTypeRelatedToWorker
     0.17s   0.8% 44.00%      0.30s  1.42%  getAllocationProfile
     0.17s  0.79% 44.79%      0.17s  0.79%  getTypeListId
     0.16s  0.77% 45.56%      0.81s  3.87%  getUnmatchedProperties
     0.16s  0.75% 46.31%      0.16s  0.75%  getStringLiteralType
     0.14s  0.65% 46.97%      0.18s  0.88%  getDeclarationModifierFlagsFromSymbol
     0.13s  0.64% 47.61%      1.82s  8.73%  resolveStructuredTypeMembers
     0.13s  0.64% 48.25%      2.11s 10.13%  some
     0.13s  0.63% 48.88%      0.19s   0.9%  scan
     0.13s  0.62% 49.50%      0.13s  0.62%  monitorOutOfMemory
     0.13s  0.61% 50.10%      0.13s  0.61%  wrapSafe
     0.12s   0.6% 50.70%      9.11s 43.68%  structuredTypeRelatedTo
     0.12s  0.58% 51.29%      6.53s 31.28%  getMappedType
     0.12s  0.58% 51.86%      3.07s 14.70%  getIndexedAccessTypeOrUndefined
     0.12s  0.57% 52.43%      0.30s  1.44%  getLiteralTypeFromProperty
     0.11s  0.52% 52.96%      9.85s 47.19%  isTypeRelatedTo
     0.10s  0.49% 53.45%     12.30s 58.97%  instantiateType
     0.10s  0.49% 53.94%      0.18s  0.88%  createInstantiatedSymbolTable

[jakebailey]

I think I've mostly figured out what's going on here; #58337 made getResolvedSignature move the bottom of the resolution stack up. However, this also affects other functions that use the resolution stack for querying whether or not resolution is progress (without push/pop/error-ing). In this particular case, it looks like isResolvingReturnTypeOfSignature is what has changed behavior.

If I make it so that only the push/pop circularity code starts at the "new" bottom, allowing all of the other functions to use the whole stack for their queries, the perf problem goes away.

I'll send a PR for looking, or at least to spawn a better investigation.