Called-arity analysis can be quite slow
While looking into #18787, I noticed that called-arity analysis sometimes takes significantly longer than the surrounding simplifier runs:
For instance, when compiling Cubix.Transformations.Hoist.Custom (in the library component) we have:
...
!!! Simplifier [Cubix.Transformations.Hoist.Custom]: finished in 5165.03 milliseconds, allocated 3856.175 megabytes
Simplifier [Cubix.Transformations.Hoist.Custom]: alloc=4043492976 time=5165.031
*** Simplifier [Cubix.Transformations.Hoist.Custom]:
Result size of Simplifier iteration=1
= {terms: 125,012,
types: 1,879,379,
coercions: 653,833,
joins: 11/64}
Result size of Simplifier iteration=2
= {terms: 124,937,
types: 1,874,464,
coercions: 653,810,
joins: 12/60}
Result size of Simplifier
= {terms: 124,937,
types: 1,874,464,
coercions: 653,810,
joins: 12/60}
!!! Simplifier [Cubix.Transformations.Hoist.Custom]: finished in 8663.68 milliseconds, allocated 2890.067 megabytes
Simplifier [Cubix.Transformations.Hoist.Custom]: alloc=3030454976 time=8663.675
*** Float inwards [Cubix.Transformations.Hoist.Custom]:
Result size of Float inwards
= {terms: 124,937,
types: 1,874,464,
coercions: 653,810,
joins: 12/60}
!!! Float inwards [Cubix.Transformations.Hoist.Custom]: finished in 121.60 milliseconds, allocated 94.945 megabytes
Float inwards [Cubix.Transformations.Hoist.Custom]: alloc=99557424 time=121.605
*** Called arity analysis [Cubix.Transformations.Hoist.Custom]:
Result size of Called arity analysis
= {terms: 124,937,
types: 1,874,464,
coercions: 653,810,
joins: 12/60}
!!! Called arity analysis [Cubix.Transformations.Hoist.Custom]: finished in 111594.82 milliseconds, allocated 77722.139 megabytes
Called arity analysis [Cubix.Transformations.Hoist.Custom]: alloc=81497569472 time=111594.817
*** Simplifier [Cubix.Transformations.Hoist.Custom]:
Result size of Simplifier iteration=1
= {terms: 124,925,
types: 1,872,004,
coercions: 653,805,
joins: 13/60}
Result size of Simplifier
= {terms: 124,925,
types: 1,872,004,
coercions: 653,805,
joins: 13/60}
!!! Simplifier [Cubix.Transformations.Hoist.Custom]: finished in 2271.06 milliseconds, allocated 1926.801 megabytes
...That is called arity analysis takes over two minutes where the simplifier takes less than 10 seconds on what is likely a very similar Core program.
It sounds to me like there may be something quadratic lurking here.