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

Previous Next

Full log

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

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.

Previous Next

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