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

Previous Next

Full log

View this message in rfc822 format

From: help-debbugs <at> gnu.org (GNU bug Tracking System)
To: Mark H Weaver <mhw <at> netris.org>
Cc: tracker <at> debbugs.gnu.org
Subject: bug#17147: closed (Performance regression by 3000000% for
 evaluating "and" form)
Date: Thu, 05 Jun 2014 01:10:03 +0000

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

Your message dated Wed, 04 Jun 2014 21:09:23 -0400
with message-id <87lhtctb5o.fsf <at> yeeloong.lan>
and subject line Re: bug#17147: [PATCH] Add versions of and/or avoiding O(n^2) argument matching
has caused the debbugs.gnu.org bug report #17147,
regarding Performance regression by 3000000% for evaluating "and" form
to be marked as done.

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


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

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

From: David Kastrup <dak <at> gnu.org>
To: bug-guile <at> gnu.org
Subject: Performance regression by 3000000% for evaluating "and" form
Date: Mon, 31 Mar 2014 11:58:00 +0200

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

The following program goes from 2.3ms execution time to 80s execution
time when going from Guile-1.8 to current master.

[zorpo.scm (text/plain, inline)]

(use-modules (srfi srfi-19))
(define start-time (current-time))
(primitive-eval (cons 'and (make-list 10000 #f)))
(display (time-difference (current-time) start-time))

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

With Guile-2.0.9 (Ubuntu package), it crashes with
Backtrace:
In ice-9/psyntax.scm:
2683: 19 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 18 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 17 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 16 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 15 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 14 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 13 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 12 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 11 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 10 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 9 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 8 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 7 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 6 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 5 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 4 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 3 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 2 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 1 [match-each-any (#f #f #f ...) ((#f top) shift) ...]
2683: 0 [match-each-any (#f #f #f ...) ((#f top) shift) ...]

ice-9/psyntax.scm:2683:37: In procedure match-each-any:
ice-9/psyntax.scm:2683:37: Throw to key `vm-error' with args `(vm-run "VM: Stack overflow" ())'.

which might give a clue as to where Guile-v2 is spending all its time.

-- 
David Kastrup

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

From: Mark H Weaver <mhw <at> netris.org>
To: David Kastrup <dak <at> gnu.org>
Cc: 17147-done <at> debbugs.gnu.org
Subject: Re: bug#17147: [PATCH] Add versions of and/or avoiding O(n^2)
 argument matching
Date: Wed, 04 Jun 2014 21:09:23 -0400

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.

I'm closing this bug now.

      Mark

Previous Next

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