bug#10651: compiling pattern matching for (or ...) takes forever

bug#10651: compiling pattern matching for (or ...) takes forever

[rixed]

Not really a bug per se (although the manual states that "When Guile
hangs or takes forever to complete a task, it is a bug."), but the time
complexity behind the compilation of (or ...) patterns in (ice-9 match)
module is so high that anything more than 8 sub-patterns takes forever
for me.  Here is a short demonstration of the problem:

% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b)) 'ab])"
 0.06s user 0.00s system 102% cpu 0.054 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 0.13s user 0.01s system 99% cpu 0.136 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 0.44s user 0.01s system 100% cpu 0.443 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 1.78s user 0.01s system 100% cpu 1.792 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 7.28s user 0.02s system 100% cpu 7.308 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 29.31s user 1.50s system 99% cpu 30.823 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 133.75s user 0.14s system 99% cpu 2:13.94 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) % ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) 'ab])"
 ?

It's easy to work around by splitting the or in smaller chunks but it
can take some time to understand why the compiler hangs. I believe such
time complexity behavior should be advertised in the manual.

bug#10651: There should be a fix to this bug

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 540 bytes --]

Hi,

In the compilation of the or pattern the sk is made a lambda
but not the fk hence the observed geometric explosion. I have a fix
for this that works but intend to talk with foof about it
to fix ithe upstream matcher. There is really no need to change the doc

The fix is easy (I beleve). Actually a small diff for it shows shows,

482,483c482
<      (let ((ffk (lambda () (match-gen-or-step v q g+s sk fk i))))
<        (match-one v p g+s sk (ffk) i)))
---
>      (match-one v p g+s sk (match-gen-or-step v q g+s sk fk i) i))

/Stefan

[-- Attachment #2: Type: text/html, Size: 609 bytes --]

bug#10651: There should be a fix to this bug

[Ludovic Courtès]

Hello!

I updated (ice-9 match) from Chibi as recommended by Stefan, and it
appears to fix the problem for me.

Thanks!

Ludo’.