GNU bug report logs - #10651
compiling pattern matching for (or ...) takes forever

Previous Next

Full log

View this message in rfc822 format

From: help-debbugs <at> gnu.org (GNU bug Tracking System)
To: ludo <at> gnu.org (Ludovic Courtès)
Cc: tracker <at> debbugs.gnu.org
Subject: bug#10651: closed (compiling pattern matching for (or ...) takes
 forever)
Date: Fri, 08 Jun 2012 10:48:02 +0000

[Message part 1 (text/plain, inline)]

Your message dated Fri, 08 Jun 2012 12:45:14 +0200
with message-id <87wr3i2ibp.fsf <at> gnu.org>
and subject line Re: bug#10651: There should be a fix to this bug
has caused the debbugs.gnu.org bug report #10651,
regarding compiling pattern matching for (or ...) takes forever
to be marked as done.

(If you believe you have received this mail in error, please contact
help-debbugs <at> gnu.org.)


-- 
10651: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=10651
GNU Bug Tracking System
Contact help-debbugs <at> gnu.org with problems

[Message part 2 (message/rfc822, inline)]

From: rixed <at> happyleptic.org
To: bug-guile <at> gnu.org
Subject: compiling pattern matching for (or ...) takes forever
Date: Mon, 30 Jan 2012 11:10:36 +0100

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.

[Message part 3 (message/rfc822, inline)]

From: ludo <at> gnu.org (Ludovic Courtès)
To: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
Cc: foof <at> synthcode.com, 10651-done <at> debbugs.gnu.org
Subject: Re: bug#10651: There should be a fix to this bug
Date: Fri, 08 Jun 2012 12:45:14 +0200

Hello!

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

Thanks!

Ludo’.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.