Subject: bug#10651: closed (Re: bug#10651: There should be a fix to this bug)

From: [email-masked] (GNU bug Tracking System)
Date: Fri, 08 Jun 2012 10:48:02 +0000

Your bug report

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

which was filed against the guile package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
10651: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=10651
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#10651: There should be a fix to this bug
From: [email-masked] (Ludovic Courtès)
To: Stefan Israelsson Tampe <[email-masked]>
Cc: [email-masked], [email-masked]
Date: Fri, 08 Jun 2012 12:45:14 +0200
List-Id: <debbugs-submit.debbugs.gnu.org>

Hello!

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

Thanks!

Ludo’.

Subject: compiling pattern matching for (or ...) takes forever
From: [email-masked]
To: [email-masked]
Date: Mon, 30 Jan 2012 11:10:36 +0100
List-Id: <debbugs-submit.debbugs.gnu.org>

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.