Scala-dev: 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: https://github.com/scala/compiler-benchmark/compare/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: https://github.com/scala/scala/compare/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