Skip to content

Call arity: Fix #18789

Ben Gamari requested to merge wip/T18789-a into master

The Main Act

UnVarGraph: Improve asymptotics fixes #18789 by improving the asymptotics of the UnVarGraph data structure. Improves Specifically, deletions were previously O(n) in the case of graphs consisting of many complete (bipartite) sub-graphs. Together with the nature of call arity this would produce quadratic behavior.

We now encode deletions specifically, taking care to do some light normalization of empty structures. In the case of the Network.AWS.EC2.Types.Sum module from #19203, this brings the runtime of the call-arity analysis from over 50 seconds down to less than 2 seconds.

Other notable changes

Avoids another potential performance cliff by ensuring sharing of conservative called-with set used by callArityRecEnv in the case of non-thunks.

Also includes changes from !4792 (closed) .

Fixes #18789.

Edited by Ben Gamari

Merge request reports