Subject: bug#17147: closed (Re: bug#17147: [PATCH] Add versions of and/or avoiding O(n^2) argument matching)

From: [email-masked] (GNU bug Tracking System)
Date: Thu, 05 Jun 2014 01:10:05 +0000

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 [email-masked].

-- 
17147: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=17147
GNU Bug Tracking System
Contact [email-masked] with problems

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

David Kastrup <[email-masked]> 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

Subject: Performance regression by 3000000% for evaluating "and" form
From: David Kastrup <[email-masked]>
To: [email-masked]
Date: Mon, 31 Mar 2014 11:58:00 +0200
List-Id: <debbugs-submit.debbugs.gnu.org>

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

(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))

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