GNU bug report logs - #17147
Performance regression by 3000000% for evaluating "and" form

Previous Next

Full log

View this message in rfc822 format

From: David Kastrup <dak <at> gnu.org>
To: Mark H Weaver <mhw <at> netris.org>
Cc: 17147-done <at> debbugs.gnu.org
Subject: bug#17147: [PATCH] Add versions of and/or avoiding O(n^2) argument matching
Date: Thu, 05 Jun 2014 06:06:53 +0200

Mark H Weaver <mhw <at> netris.org> writes:

> David Kastrup <dak <at> gnu.org> writes:
>
>> Fixes <http://bugs.gnu.org/17147>
>>
>> * module/ice-9/boot-9.scm (and, or): Add syntax rules that only do one
>>   pattern matching operation per and/or rather than per argument.
>
> Thanks, but I ended up simply changing the macros to dotted tail
> patterns.  It's commit 1ea8954814d124b995f2296bc6aec92adb566bc1.

Still one matching operation per argument (though an O(1) rather than an
O(n) one) rather than a single match.

Incidentally, most other syntax rules don't degrade on ... like that
because they do not do recursive matching on already matched patterns
either, case in point being the cond rule.  So indeed and/or have been
about the worst culprits for this case.

-- 
David Kastrup

Previous Next

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