search

oridb / mc

Myrddin Compiler
MIT License
387 stars 34 forks source link

Merge decision tree nodes when possible #197

Closed typeless closed 4 years ago

typeless commented 4 years ago

(Tested on Linux/AMD64) Sample count: 506 Dtree Refcnt avg: 5.38 95th percentile: 3.00 maximum: 100 Dtree Size avg: 5.23 95th percentile: 3.00 maximum: 84 Dtree Height avg: 1.39 95th percentile: 1.00 maximum: 12

References: Mikael Pettersson. A term pattern-match compiler inspired by finite automata theory. (p.6 "Step 3: Optimizing the DFA")

typeless commented 4 years ago

This is ready for review. It is not related to the heuristics but helps a lot.

I experimented with some heuristics like the q and b described in the paper (, Compiling Pattern Matching to Good Decision Trees by Luc Maranget). But it does not produce promising results, even slightly worse. There are probably bugs in my implementation, but I suspect that it's also related to how the string matching currently works (it dominates a lot of test nodes, which the ML languages. does not seem to have.)

typeless commented 4 years ago

It seems there is nameeq , Let me change that too. Fixed.