[Report] Optimization attempt: cache TypeOps$.asSeenFrom

[tanishiking]

This is a report of optimization attempt by caching TypeOps$.asSeenFrom

Summary

• TypeOps.asSeenFrom accounts for 9.3% of CPU time on scalaz
• Caching TypeOps.asSeenFrom (per Context) achieves around a 33% cache hit rate and gives a consistent 5-6% CPU time speedup in scalaz (on my local machine)
• On other benchmarks, the effect was within the margin of error (±1.0%)
• How about other projects like app that uses scalaz or cats? Is this cache worth it?

Observation: CPU samples of TypeOps$.asSeenFrom

Ran several scala3-benchmarks projects with async-profiler attached and measured the CPU samples (and found asSeenFrom accounts for 10% of scalaz)

Benchmark	asSeenFrom
Scalaz	10.27%
Parallel Collections	4.59%
Indigo	1.74%
Tasty Query	1.13%
Scala YAML	1.17%

It seems like asSeenFrom % grow with generic type definitions, deeper class hierarchies, and heavier implicit searches? At least for projects like scalaz, there seems to be room for optimization.
(TBH, caching is the last thing I want to do for optimization, because cache is a cause of a lot of wired bugs if the implementation isn't correct. I tried optimizing it's implementation, but there was no win... 😢 )

What hit rate can we expect if we cached asSeenFrom (at most)?

Roughly speaking, asSeenFrom should be cacheable as long as the phase and its three inputs match (actually, it's not though).

scala3/compiler/src/dotty/tools/dotc/core/TypeOps.scala

Lines 32 to 35 in 18df09c

	/** The type `tp` as seen from prefix `pre` and owner `cls`. See the spec
	* for what this means.
	*/
	final def asSeenFrom(tp: Type, pre: Type, cls: Symbol)(using Context): Type = {

I measured the hit rate when caching using those four values as the key.

Benchmark	hit	miss	hit rate
Scalaz	278,429	289,213	49.0%
Parallel Collections	57,832	61,338	48.5%
Indigo	181,911	246,369	42.5%
Tasty Query	41,574	46,355	47.3%
Scala YAML	28,100	33,759	45.4%

It looks like TypeOps.asSeenFrom is being called repeatedly with the same inputs. In practice, simply using those four values as the key is unsafe, but it does seem worth caching.

Per-Context cache

Is tp, pre, and cls enough for the cache key of asSeenFrom? I don't think so... Context is also part of the input. In fact, the output of asSeenFrom can be different depending on the contents of the Context (e.g. isLegalPrefix called from AsSeenFromMap#apply).
However, since it's discouraged to use Context as a key for a cache with a longer lifetime than the Context itself, I tried instead having the cache for asSeenFrom inside the Context (see my PR #26778) ¹

Here's the result, cache hit rate and compile time improvements

Benchmark	hit rate
Scalaz	33.1%
Parallel Collections	24.3%
Indigo	7.9%
Tasty Query	20.1%
Scala YAML	23.7%

blue = main 1082b3d
red = cached #26778

 ./run.sh \
    --versions \
      3.10.0-RC1-bin-1082b3dda37abeec688f83fc284a27e98e1e8cf8-BENCH \
      3.10.0-RC1-bin-a6a7c2847be6cfa500f49e2f28f574db1fbca120-BENCH \
    --jvm temurin:25 \
    --runs 3 \
    --filter 'scalaz|indigo|parallelCollections|tastyQuery|scalaYaml' // randomly picked
// And visualized using `visualize.py`

In the scala3-benchmark suite, only scalaz showed a consistent improvement, and the other projects were within the margin of error (at least those 5 benches I picked randomly).
That makes sense, since in most projects asSeenFrom accounts for only around ~5% of CPU samples, so even caching it with 20-30% hit rate would only yield a 1-2% improvement at most.

Future work

• We see a benchmark improvement on scalaz, but how about users of scalaz or cats would be affected?
• This attempt conservatively discards the cache whenever the context is refreshed. How much would the hit rate improve if the cache were retained across context switches such as localContext?

Footnotes

1. Discarding the cache on every new Context is a conservative design, in practice, cases like localContext where only the tree or owner changes probably don't require discarding the cache. Still, this seems like a good, safe first step. ↩

[tanishiking]

vibe-added scalaSteward (core) to benchmark and run locally again

[tanishiking]

benchmark source for scala-steward lampepfl/scala3-benchmarks#41