Unreachable case analysis in pattern matcher is allocation heavy

[retronym]

This stack has shown up as a leading allocation source in the compiler under some workloads:

Object scala.tools.nsc.transform.patmat.Solving$Solver.$anonfun$dropUnit$1(...)	219
   Object scala.tools.nsc.transform.patmat.Solving$Solver$$Lambda$2842.268435976.apply(...)	219
   void scala.collection.IndexedSeqOptimized.foreach(...)	219
   void scala.collection.IndexedSeqOptimized.foreach$(...)	219
   void scala.collection.mutable.ArrayOps$ofRef.foreach(...)	219
   Set[] scala.tools.nsc.transform.patmat.Solving$Solver.dropUnit(...)	219
   Set scala.tools.nsc.transform.patmat.Solving$Solver.findTseitinModel0(...)	219
   Set scala.tools.nsc.transform.patmat.Solving$Solver.findTseitinModelFor(...)	219
   Set scala.tools.nsc.transform.patmat.Solving$Solver.findTseitinModelFor$(...)	219
   Set scala.tools.nsc.transform.patmat.PatternMatching$OptimizingMatchTranslator.findTseitinModelFor(...)	219
   Map scala.tools.nsc.transform.patmat.Solving$Solver.findModelFor(...)	219
   Map scala.tools.nsc.transform.patmat.Solving$Solver.findModelFor$(...)	219
   Map scala.tools.nsc.transform.patmat.PatternMatching$OptimizingMatchTranslator.findModelFor(...)	219
   Map scala.tools.nsc.transform.patmat.PatternMatching$OptimizingMatchTranslator.findModelFor(...)	219
   Option scala.tools.nsc.transform.patmat.MatchAnalysis$MatchAnalyzer.unreachableCase(...)	219

Tasks:

• Use a debugger / logging to characterize the pattern of data that arrives in dropUnit, and relate this back to patterns of source code.
• As a diagnostics, add a counter of the total number of bytes allocated by simplified.toArray in that method.
• Synthesize a test case that can demonstrate that this number grows O(N^2) or worse with respect to the complexity of the source code.
• Devise a more efficient implementation. Could we make dropUnit mutate an Array[Clause] in place to insert nulls, rather than returning a new, smaller array?

[retronym]

Here's what I have in mind: https://github.com/retronym/scala/tree/faster/patmat-solving

[retronym]

Here's a benchmark that stresses this analysis: scala/compiler-benchmark@master...retronym:topic/patmat-bench

Results in the commit comment. Seems to run slow, despite having a lower allocation rate.

More investigation required.

[retronym]

We could also look into using a pair of BitSets to represent Set[Lit] for Clause. Or maybe just a specialized IntHashSet. We're paying a big cost for boxing the Lit value class in collections/options.

[retronym]

This branch seems to work. I ended up adding some other unrelated commits to reduce allocation in other parts of the compiler: scala/scala@2.12.x...retronym:faster/patmat-intset

It improves JMH-measured compilation time the patmat-exhaust-huge corpus from 5.7s to 3.2s (gc.alloc.rate.norm improves from 9.4GB/op to 2GB/op.

For "normal" codebases, the branch in total reduces allocation rates by 10-20%.

[rorygraves]

Wow