GNU bug report logs - #17485
(srfi srfi-1) reduce-right does not scale, version 2.0.9

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#17485: closed (Re: bug#17485: (srfi srfi-1) reduce-right does
 not scale, version 2.0.9)
Date: Tue, 12 Jul 2016 07:09:02 +0000

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

Your bug report

#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9

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 17485 <at> debbugs.gnu.org.

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

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

From: Andy Wingo <wingo <at> pobox.com>
To: David Kastrup <dak <at> gnu.org>
Cc: 17485-done <at> debbugs.gnu.org
Subject: Re: bug#17485: (srfi srfi-1) reduce-right does not scale,
 version 2.0.9
Date: Tue, 12 Jul 2016 09:07:58 +0200

On Tue 21 Jun 2016 17:31, David Kastrup <dak <at> gnu.org> writes:

> Andy Wingo <wingo <at> pobox.com> writes:
>
>> I think on 2.0 that this might be an OK workaround:
>>
>>  (define (reduce-right f ridentity lst)
>>    (reduce f ridentity (reverse lst)))
>
> So if we don't store the inverse list in-space, it needs to be either a
> copy in heap (reverse) or stack (recursion).  Stack allocation is likely
> cheaper in execution time (though the total memory cost depends on the
> stack frame size taken per call).  The limited stack size on 2.0 does
> not seem like a good fit, however.  Which makes your workaround seem
> like the best option.

Applied this fix to stable-2.0.  Thanks for the report.

Andy

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

From: David Kastrup <dak <at> gnu.org>
To: bug-guile <at> gnu.org
Subject: (srfi srfi-1) reduce-right does not scale, version 2.0.9
Date: Tue, 13 May 2014 12:47:32 +0200

The following code results in an error:

(use-modules (srfi srfi-1))
(reduce-right + 0 (make-list 10000 1))

Backtrace:
In srfi/srfi-1.scm:
 379: 19 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 18 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 17 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 16 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 15 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 14 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 13 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 12 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 11 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 10 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 9 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 8 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 7 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 6 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 5 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 4 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 3 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 2 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 1 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
 379: 0 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]

srfi/srfi-1.scm:379:31: In procedure recur:
srfi/srfi-1.scm:379:31: Throw to key `vm-error' with args `(vm-run "VM: Stack overflow" ())'.

This is for Guile version 2.0.9 as distributed by Ubuntu 14.04.

Somewhat surprisingly, fold-right does not suffer from the same error.

Surprisingly because the definition of reduce-right is

(define (reduce-right f ridentity lst)
  "`reduce-right' is a variant of `fold-right', where the first call to
F is on two elements from LST, rather than one element and a given
initial value.  If LST is empty, RIDENTITY is returned.  If LST
has just one element then that's the return value."
  (check-arg procedure? f reduce)
  (if (null? lst)
      ridentity
      (fold-right f (last lst) (drop-right lst 1))))

It turns out that the call of drop-right is responsible here:

(define (drop-right lis k)
  (let recur ((lag lis) (lead (drop lis k)))
    (if (pair? lead)
        (cons (car lag) (recur (cdr lag) (cdr lead)))
        '())))

For all the cleverness involved here, one has to run through the whole
list anyway.  It makes no real sense to do this in this manner.  The
motivation may be to have a warm cache when k is small, but the result
is self-defeating because of VM stack buildup.

(define (drop-right lis k)
    (drop lis (- (length lis) k)))

should be all that is needed.

-- 
David Kastrup

Previous Next

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