search

guicho271828 / trivia

Pattern Matcher Compatible with Optima
Other
332 stars 22 forks source link

Exponential time for match compilation #108

Closed pfdietz closed 4 years ago

pfdietz commented 4 years ago

The time to compile a MATCH form can increase exponentially with the depth of the pattern. The attached file shows the issue. (try 8) takes nearly an order of magnitude longer than (try 7).

example2.lisp.gz

pfdietz commented 4 years ago

Simply compiling the pattern (list (list (list ... (list x) ...))) in a match takes exponential time in the depth of nesting.

guicho271828 commented 4 years ago

you can fall back to the simpler compiler by (declare (trivia:optimizer :trivial)). does it still have the same behavior?

pfdietz commented 4 years ago

I tried that (on the first example there). It did not fix the problem. The time seems to be being spent in "repair", which has something to do with or patterns?

guicho271828 commented 4 years ago

Ah, "repair" is used to check & fix the disjunctives (ORs) in order to ensure that each branch of OR has the same set of variables. Yes, the algorithm has a room for improvement, it is currently implemented quite naively.

pfdietz commented 4 years ago

In more detail, in sbcl:

(sb-cltl2:macroexpand-all '(match (x) ((list (list (list ... (list y) ...))) y)))

when profiled shows most of the time is being spent under TRIVIA.LEVEL1:CORRECT-PATTERN, and also TRIVIA.LEVEL1:VARIABLES. What's sad here is that the pattern doesn't have any OR in it, so all the work is being done for nothing.

Tracing that function, I see it being called on the same arg and returning the same value multiple times, so maybe memoization could save this?

pfdietz commented 4 years ago

Attaching a memoization patch that greatly reduces the time growth rate.

trivia.exp-time.patch.gz

guicho271828 commented 4 years ago

will probably check in the weekends, thanks!

pfdietz commented 4 years ago

That's not necessarily the best patch -- the time spent hashing the large keys could probably be reduced -- but it's a lot faster than exponential time.

guicho271828 commented 4 years ago

Tested the patch, I don't find any problem in the code.

It dramatically reduced the compile time of type-r library which parses the CL type specifier with complex patterns --- from 21sec to 2.5 sec!

Thanks for contributing the code. I looked up the internet to find your contact address. Do you mind using the university address from U. Rochester (found in the persistent array paper)? Thank you.

pfdietz commented 4 years ago

No, that's an old and dead email address. Reach me at paul.f.dietz@gmail.com

guicho271828 commented 4 years ago

merged into master. Thank you very much!