From: David Kastrup <dak@gnu.org>
To: Mark H Weaver <mhw@netris.org>
Cc: 17147@debbugs.gnu.org, request@debbugs.gnu.org
Subject: bug#17147: Performance regression by 3000000% for evaluating "and" form
Date: Tue, 01 Apr 2014 01:21:15 +0200 [thread overview]
Message-ID: <87mwg6kl90.fsf@fencepost.gnu.org> (raw)
In-Reply-To: <87r45im25m.fsf@yeeloong.lan> (Mark H. Weaver's message of "Mon, 31 Mar 2014 18:30:45 -0400")
[-- Attachment #1: Type: text/plain, Size: 1540 bytes --]
Mark H Weaver <mhw@netris.org> writes:
> severity 17147 wishlist
> thanks
>
> David Kastrup <dak@gnu.org> writes:
>
>> 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))
>
> I suspect the reason this works well on Guile 1.8 is that macros are
> expanded lazily, and since the first argument is #f, it doesn't need to
> expand the rest.
>
> Guile 2.0 uses a different macro expander which is vastly superior in
> most respects and needed to support modern Scheme programs, but it is
> not lazy. Guile 2 is primarily designed to work in a compiled mode
> anyway, where laziness is pointless and would most likely slow things
> down.
>
> (and x y ...) expands into (if x (and y ...) #f), so your huge 'and'
> form turns into a very deeply nested expression, and this overflows the
> compiler's stack on Guile 2.0.x. Thanks to Andy's recent work on
> expandable stacks in master, this case works properly there.
I think you are overlooking here that a mere 10000-term expression here
is taking 80 seconds to complete. That's 8ms for each term
corresponding to several million clock cycles. The only way to arrive
at such a performance impact is by at least quadratic behavior, and
quadratic behavior is a bad idea. As a point of reference, the
equivalent and just as deeply nested
[-- Attachment #2: zorpo.scm --]
[-- Type: text/plain, Size: 208 bytes --]
(use-modules (srfi srfi-19) (srfi srfi-1))
(define start-time (current-time))
(primitive-eval (fold (lambda (a n) (list 'if #f n)) #f (make-list 10000)))
(display (time-difference (current-time) start-time))
[-- Attachment #3: Type: text/plain, Size: 1046 bytes --]
takes 100ms.
> While it would of course be ideal for our compiler to efficiently
> handle expressions 10000 levels deep (if it can be done without
> sacrificing maintainability), dealing with such pathological cases
> should not be a high priority, IMO. There are many more important
> things to work on.
>
> Is this just an academic exercise, or does Lilypond generate massively
> huge expressions like this?
LilyPond evaluates a lot of one-shot expressions in the course of its
operation, including complex ones. But Guilev2 offers enough other
stumbling blocks. We have not yet arrived at a state where it would
even be possible to evaluate performance.
I tripped over this problem here merely while trying to find a
persuasive example for benefits of improving scm_reverse_x performance,
as scm_reverse_x is used quite a bit in libguile/expand.c.
Since the performance impact of reverse! in this example is
indistinguishable from thermal noise, its use seems to be outside of the
quadratically behaving code parts.
--
David Kastrup
next prev parent reply other threads:[~2014-03-31 23:21 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-03-31 9:58 bug#17147: Performance regression by 3000000% for evaluating "and" form David Kastrup
2014-03-31 22:30 ` Mark H Weaver
2014-03-31 23:21 ` David Kastrup [this message]
2014-04-01 2:55 ` Mark H Weaver
2014-04-01 6:17 ` David Kastrup
2014-04-01 7:10 ` Mark H Weaver
2014-04-01 8:22 ` David Kastrup
2014-04-01 11:59 ` David Kastrup
2014-04-01 16:19 ` Mark H Weaver
2014-05-12 6:08 ` bug#17147: Another idea David Kastrup
2014-05-13 13:03 ` bug#17147: Scalability front and back David Kastrup
2014-06-04 14:18 ` bug#17147: [PATCH] Add versions of and/or avoiding O(n^2) argument matching David Kastrup
2014-06-05 1:09 ` Mark H Weaver
2014-06-05 4:06 ` David Kastrup
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87mwg6kl90.fsf@fencepost.gnu.org \
--to=dak@gnu.org \
--cc=17147@debbugs.gnu.org \
--cc=mhw@netris.org \
--cc=request@debbugs.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).