Description
On a large customer app, SsaSimplifyInterceptors is taking >20% of total compile time due to slow AbstractValueDomain.isInterceptor checks.
isInterceptor is slow because the isDisjoint check devolves into an all-pairs check of 933 instantiated Interceptor types against a large number subtypes of some other interface. I have seen this with List, where there are 50-60 List implementations, but that exits early because many of the intercepted classes implement List and one of them is early in the iteration of the instantiated subclasses of Interceptor. I suspect the large app has a similar pattern with a widely used interface type, perhaps a mixin, but the intersection (isDisjoint) is empty, leading to many exhaustive N*M comparisons.
There are many ways to improve the situation:
Short term fix
We can get a 30x speedup by caching, but the cache does seem to cause more objects to be retained in memory. It seems like a small cache would help. Data gathered from the full cache indicates that we could improve performance with a much smaller fixed size cache of a few hundred TypeMasks, flushing the cache when full.
Longer term
Faster set operations
isDisjoint is essentially a set operation, A∩B = ∅.
This can be implemented much more efficiently using an ordered set.
Classes could be assigned integer indexes to make this compact, e.g. DFS pre- or post- order over the subclasses. The declared-subclasses-of-Interceptor set would be a range, and the instantiated-subclasses-of-Interceptor would be small number of ranges rather than 933 elements.
Specialized abstract domains.
A small union-of-disjoint-subsets (powerset) abstract domain could be efficiently computed for each TypeMask. It would allow the TypeMask to directly answer the isIntercepted query.
2{intercepted,unintercepted} would take two bits. It could be packed with other small powerset domains into a single int value. The values for the inclusive- and exclusive- subclass- and subtype- cones can be precomputed bottom-up in a single pass over the class hierarchy.