A dreadful discovery about variadic recursive procedures

[John Cowan]

It was worked out on #scheme this weekend that some harmless-looking Scheme functions that appear to have linear behavior actually have quadratic behavior. Here is an example:

(define (plus x . xs)
(if (null? xs)
x
(+ x (apply plus xs))))

[Yes, I know that + is already variadic and handles zero arguments nicely. That isn't the point. This version is not tail recursive, which is not the point either.]

This procedure *seems* to be linear in the number of arguments. However, all Scheme standards require that a variadic function be passed a *freshly allocated* list of the values with which it was called, and at least a large number of Scheme implementations are in fact conformant. (This feature is probably to prevent trouble if the callee mutates the list it is passed.)

Therefore, at each step of the recursion, (apply plus xs) makes a shallow copy of xs. This O(n) behavior is performed n times, making the procedure quadratic.

The simplest resolution is this:

(define (plus x . xs) (safe-plus x xs)

(define (safe-plus x xs)
(if (null? xs)
x
(+ x (safe-plus (car xs) (cdr xs)))))

For what it's worth, the Common Lisp standard allows implementations not to make this copy when a function is invoked via APPLY, but tests show that at least abcl, ccl, ecl, and sbcl actually do make the copy; clisp makes a copy in some circumstances only.

Be warned.

--
John Cowan http://vrici.lojban.org/~cowan co...@ccil.org
If I have seen farther than others, it is because they are closer than
I am. --Noetica
Noetica’s standing on the shoulders of galahs. --Gibbon
Better than standing on the shoulders of hobyahs (not to be confused
with hobbits, though some have done so). --me

[Helmut Eller]

On Sat, Dec 01 2018, John Cowan wrote:

[...]

> (define (plus x . xs)
> (if (null? xs)
> x
> (+ x (apply plus xs))))
>
> [Yes, I know that + is already variadic and handles zero arguments
> nicely. That isn't the point. This version is not tail recursive,
> which is not the point either.]
>
> This procedure *seems* to be linear in the number of arguments.
> However, all Scheme standards require that a variadic function be
> passed a *freshly allocated* list of the values with which it was
> called, and at least a large number of Scheme implementations are in
> fact conformant. (This feature is probably to prevent trouble if the
> callee mutates the list it is passed.)

Are you saying that all Scheme standards prohibit sufficiently smart
compilers that would transform the example to

(define (plus x . xs) (apply + x xs))

?

That would indeed be a sign of dreadful standards.

Helmut

[Nils M Holm]

Helmut Eller <eller....@gmail.com> wrote:

> John Cowan <johnw...@gmail.com> wrote:
> > (define (plus x . xs)
> > (if (null? xs)
> > x
> > (+ x (apply plus xs))))
>

> Are you saying that all Scheme standards prohibit sufficiently smart
> compilers that would transform the example to
>
> (define (plus x . xs) (apply + x xs))

John already pointed out that + already being variadic is
beside the point. Imagine a non-variadic function in the
place of +. What will your "sufficiently smart compiler"
do with that?

I think John pointed out something interesting here! I
searched my code for constructs like the one above
and -- fortunately -- found only ones where the expected
number of arguments is small.

--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org

[Helmut Eller]

On Mon, Dec 03 2018, Nils M Holm wrote:

> Helmut Eller <eller....@gmail.com> wrote:
>> John Cowan <johnw...@gmail.com> wrote:
>> > (define (plus x . xs)
>> > (if (null? xs)
>> > x
>> > (+ x (apply plus xs))))
>>
>> Are you saying that all Scheme standards prohibit sufficiently smart
>> compilers that would transform the example to
>>
>> (define (plus x . xs) (apply + x xs))
>
> John already pointed out that + already being variadic is
> beside the point.

I read that. Or are you saying that John has chosen a confusing example
on purpose?

> Imagine a non-variadic function in the
> place of +. What will your "sufficiently smart compiler"
> do with that?

How would I know what a standard compliant compiler is allowed to do or
not. John is the language lawyer. That's why I asked him if such a
transformation is allowed by the standards for his example.

[A more general transformation would be

(define (plus x . xs) (fold-left F x xs))

if the compiler can prove that F is "pure" (for some definition of
"pure").

The more general transformation would probably be allowed too if the
specific transformation for + is allowed. But I guess that's obvious.]

Helmut

[Barry Margolin]

In article <m2tvjuw...@gmail.com>,

Helmut Eller <eller....@gmail.com> wrote:

> On Mon, Dec 03 2018, Nils M Holm wrote:
>
> > Helmut Eller <eller....@gmail.com> wrote:
> >> John Cowan <johnw...@gmail.com> wrote:
> >> > (define (plus x . xs)
> >> > (if (null? xs)
> >> > x
> >> > (+ x (apply plus xs))))
> >>
> >> Are you saying that all Scheme standards prohibit sufficiently smart
> >> compilers that would transform the example to
> >>
> >> (define (plus x . xs) (apply + x xs))
> >
> > John already pointed out that + already being variadic is
> > beside the point.
>
> I read that. Or are you saying that John has chosen a confusing example
> on purpose?
>
> > Imagine a non-variadic function in the
> > place of +. What will your "sufficiently smart compiler"
> > do with that?
>
> How would I know what a standard compliant compiler is allowed to do or
> not. John is the language lawyer. That's why I asked him if such a
> transformation is allowed by the standards for his example.

Presumably the compiler is allowed to do any optimizations that don't
alter the visible effects of the program. The requirement to allocate a
fresh list for the variadic argument should only be relevant if the
function modifies the list destructively, or compares it with the list
from another iteration in the recursion.

However, these are optimizations that would be *allowed*, not *required*
(like tail call optimization is). This means you can't count on it, and
an implementation just following the standard will produce the quadratic
performance effect mentioned in the OP.

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

[Pascal J. Bourguignon]

This can be found often in newbie code. Then we explain them that it's
bad because it makes their code O(n^2), but because of apply copying the
list, it's worse, it's O(n^3).

So now we can make newbies even more afraid! :-)

--
__Pascal J. Bourguignon__
http://www.informatimago.com

[Pascal J. Bourguignon]

Barry Margolin <bar...@alum.mit.edu> writes:

> Presumably the compiler is allowed to do any optimizations that don't
> alter the visible effects of the program. The requirement to allocate a
> fresh list for the variadic argument should only be relevant if the
> function modifies the list destructively, or compares it with the list
> from another iteration in the recursion.

Not only.

The argument list can be modified in a different thread (or from the
middle of the callee by the caller if continuations are used).

So taking a snapshot of the list is an essential property in presence of
threads or continuations.

> However, these are optimizations that would be *allowed*, not *required*
> (like tail call optimization is). This means you can't count on it, and
> an implementation just following the standard will produce the quadratic
> performance effect mentioned in the OP.

--

[Brad Lucier]

On Saturday, December 1, 2018 at 8:57:32 PM UTC-5, John Cowan wrote:

> Therefore, at each step of the recursion, (apply plus xs) makes a shallow copy of xs. This O(n) behavior is performed n times, making the procedure quadratic.

In each Scheme there's usually a bound on the number of arguments you can pass to a function, so on the size of the lists that you can "apply" a function to, so the "quadratic" time problem is actually bounded, e.g. (in Gambit):

> (compile-file "sum")
"/tmp/mozilla_lucier0/sum.o1"
> (load "sum")
"/tmp/mozilla_lucier0/sum.o1"
> (define 100i (make-list 100 1))
> (define 1000i (make-list 1000 1))
> (time (apply plus 100i))
(time (apply plus 100i))
0.000179 secs real time
0.000182 secs cpu time (0.000109 user, 0.000073 system)
no collections
237600 bytes allocated
32 minor faults
no major faults
100
> (time (apply plus 1000i))
(time (apply plus 1000i))
0.010328 secs real time
0.010331 secs cpu time (0.002577 user, 0.007754 system)
no collections
23976000 bytes allocated
2968 minor faults
no major faults
1000
> (define 10000i (make-list 10000 1))
> (time (apply plus 10000i))
*** ERROR IN ##exec-stats -- Number of arguments exceeds implementation limit
(plus 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...)

So you can't really apply this code for large lists.

Brad

[John Cowan]

On Tue, Dec 4, 2018 at 6:39 PM Brad Lucier <luc...@math.purdue.edu> wrote:

> > (define 10000i (make-list 10000 1))
> > (time (apply plus 10000i))
> *** ERROR IN ##exec-stats -- Number of arguments exceeds implementation limit

(> plus 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...)

So you can't really apply this code for large lists.

In Chicken 5 the number of arguments is bounded only by the stack size,
which can be adjusted at startup time. Code similar to the above will work
with more than 100,000 arguments on the default stack for a 64-bit build,
though it gives a stack overflow error at 250,000 arguments.

--
John Cowan http://vrici.lojban.org/~cowan co...@ccil.org

May the hair on your toes never fall out! --Thorin Oakenshield (to Bilbo)

[Barry Margolin]

In article <71d4bad3-4582-488a...@googlegroups.com>,

Brad Lucier <luc...@math.purdue.edu> wrote:

> In each Scheme there's usually a bound on the number of arguments you can
> pass to a function, so on the size of the lists that you can "apply" a
> function to, so the "quadratic" time problem is actually bounded, e.g. (in
> Gambit):

In the real world there are always physical and implementation limits,
so everything is bounded. But including that would make everything O(1),
so we ignore it and assume abstract machines.

In this case it's quadratic until it reaches the limit, then just stops
working.

[Marc Nieper-Wißkirchen]

I think an example like the one John gave was one of the main motivations for Racket to make pairs immutable by default.

As this is a heavily non-backwards compatible change, what about extending the procedure call syntax of Scheme instead to include dotted lists like:

(x y ... . z)

This should have the same behavior as (apply x y ... z) with the difference that z may be modified by the call.

This syntax fits nicely to the syntax of procedure formals.

-- Marc

[John Cowan]

On Sunday, December 9, 2018 at 10:28:52 AM UTC-5, Marc Nieper-Wißkirchen wrote:

> As this is a heavily non-backwards compatible change, what about extending the procedure call syntax of Scheme instead to include dotted lists like:
>
> (x y ... . z)
>
> This should have the same behavior as (apply x y ... z) with the difference that z may be modified by the call.

z in this case would typically be of the form (list z1 z2 z3 ...), so you might as well just use a calling convention in which the callee expects a list argument. The workaround of providing a helper procedure like this:

(define (foo . x) (foo* x))

(define (foo* x) ...)

seems much better to me. For example, the standard Scheme procedure `vector` can
be defined in terms of `vector->list` in this way:

(define (vector . x) (vector->list x))

The main thing is to disseminate the warning against variadic recursion widely so that people aren't tempted to use it. As I noted in the original post, although the Common Lisp language
does not require this copying, most implementations including sbcl actually do it.

--
John Cowan http://vrici.lojban.org/~cowan co...@ccil.org

XQuery Blueberry DOM
Entity parser dot-com
Abstract schemata / XPointer errata
Infoset Unicode BOM --Richard Tobin

[Pascal J. Bourguignon]

John Cowan <johnw...@gmail.com> writes:

> On Sunday, December 9, 2018 at 10:28:52 AM UTC-5, Marc Nieper-Wißkirchen wrote:
>
>> As this is a heavily non-backwards compatible change, what about extending the procedure call syntax of Scheme instead to include dotted lists like:
>>
>> (x y ... . z)
>>
>> This should have the same behavior as (apply x y ... z) with the difference that z may be modified by the call.
>
> z in this case would typically be of the form (list z1 z2 z3 ...), so
> you might as well just use a calling convention in which the callee
> expects a list argument. The workaround of providing a helper
> procedure like this:
>
> (define (foo . x) (foo* x))
>
> (define (foo* x) ...)
>
> seems much better to me. For example, the standard Scheme procedure `vector` can
> be defined in terms of `vector->list` in this way:
>
> (define (vector . x) (vector->list x))

You mean: (define (vector . x) (list->vector x))

> The main thing is to disseminate the warning against variadic recursion widely so that people aren't tempted to use it. As I noted in the original post, although the Common Lisp language
> does not require this copying, most implementations including sbcl actually do it.

While some implementation have a short limit on the number of arguments,
some modern implementations do not constrain it, or not much. So the
caveat on processing time (and temp space) matters.