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: David Kastrup <dak <at> gnu.org>
Subject: bug#17147: closed (Re: bug#17147: [PATCH] Add versions of and/or
 avoiding O(n^2) argument matching)
Date: Thu, 05 Jun 2014 01:10:05 +0000

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

Your bug report

#17147: Performance regression by 3000000% for evaluating "and" form

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 17147 <at> debbugs.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: 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

[Message part 3 (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 4 (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 6 (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

Previous Next

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