Does anyone here knows what kind of optimizations are performed by Lisp
compilers to try and avoid allocating lists for the &rest arguments?
I'm thinking especially at cases like

(lambda (&rest args) (do foo) (apply bar args))

-- Stefan

On 1/14/2022 11:56 AM, Stefan Monnier wrote:
> Does anyone here knows what kind of optimizations are performed by Lisp
> compilers to try and avoid allocating lists for the &rest arguments?
> I'm thinking especially at cases like
>
> (lambda (&rest args) (do foo) (apply bar args))
I believe that some stack allocate the lists and cdr code them there.
Thus, the actual answer to your question involves storage conventions as
well as compiler optimizations, e.g., can you cdr code on the stack, etc.

I think there are also some words of wisdom or warnings in the Common
Lisp spec about what you can and cannot do (shall and shall not do?)
with rest lists so that theses optimizations are possible.
--
Jeff Barnett

Jeff Barnett [2022-01-14 13:18:07] wrote:
> On 1/14/2022 11:56 AM, Stefan Monnier wrote:
>> Does anyone here knows what kind of optimizations are performed by Lisp
>> compilers to try and avoid allocating lists for the &rest arguments?
>> I'm thinking especially at cases like
>> (lambda (&rest args) (do foo) (apply bar args))
> I believe that some stack allocate the lists and cdr code them there.

Clever, thanks.
I didn't know cdr-coding was still in use.

> Thus, the actual answer to your question involves storage conventions
> as well as compiler optimizations, e.g., can you cdr code on the
> stack, etc.

I guess this falls in the category of those implementations which
don't copy the list when going from `apply` to &rest`.
In ELisp, we've had a "NEWLY-ALLOCATED" semantics from the start, so the
general case is inevitably expensive :-(

> I think there are also some words of wisdom or warnings in the Common Lisp
> spec about what you can and cannot do (shall and shall not do?) with rest
> lists so that theses optimizations are possible.

Do you know of any other discussion around this than "Issue
REST-LIST-ALLOCATION Writeup"?

Stefan

On 1/14/2022 2:15 PM, Stefan Monnier wrote:
> Jeff Barnett [2022-01-14 13:18:07] wrote:
>> On 1/14/2022 11:56 AM, Stefan Monnier wrote:
>>> Does anyone here knows what kind of optimizations are performed by Lisp
>>> compilers to try and avoid allocating lists for the &rest arguments?
>>> I'm thinking especially at cases like
>>> (lambda (&rest args) (do foo) (apply bar args))
>> I believe that some stack allocate the lists and cdr code them there.
>
> Clever, thanks.
> I didn't know cdr-coding was still in use.
>
>> Thus, the actual answer to your question involves storage conventions
>> as well as compiler optimizations, e.g., can you cdr code on the
>> stack, etc.
>
> I guess this falls in the category of those implementations which
> don't copy the list when going from `apply` to &rest`.
> In ELisp, we've had a "NEWLY-ALLOCATED" semantics from the start, so the
> general case is inevitably expensive :-(
>
>> I think there are also some words of wisdom or warnings in the Common Lisp
>> spec about what you can and cannot do (shall and shall not do?) with rest
>> lists so that theses optimizations are possible.
>
> Do you know of any other discussion around this than "Issue
> REST-LIST-ALLOCATION Writeup"?
Unfortunately, I don't. I haven't thought about this in years. But there
are regular contributors here that I'm sure have.
--
Jeff Barnett

Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> Does anyone here knows what kind of optimizations are performed by Lisp
> compilers to try and avoid allocating lists for the &rest arguments?
> I'm thinking especially at cases like
>
> (lambda (&rest args) (do foo) (apply bar args))
>
>

In CL it is allowed (but not required) that &rest lists share with the last
argument to apply. In a case like this what that means is essentially
this:

(let ((x '(1 2))) (apply (lambda (&rest args) (apply (lambda (&rest args)
(eq args x)) args) x))

may return true, as (obviously) may

(let ((x '(1 2))) (apply (lambda (&rest args) (eq args x)) x))

In a case like

(funcall (lambda (&rest args) args) 1 2)

This is not possible and the rest list must be freshly consed.

It is possible to declare that the rest list may be stack allocated:

(funcall (lambda (&rest args) (declare (dynamic-extent args)) ...)1 2)

Would allow args to be stack allocated (and returning it would be an error
in that case).

I doubt any implementations use cdr coding now but perhaps I am wrong.

--
the small snake

Zyni Moë <no_email@invalid.invalid> wrote:

>
> I doubt any implementations use cdr coding now but perhaps I am wrong.
>

Should have read: 'any stock hardware implementations'

--
the small snake

On 2/2/2022 5:51 AM, Zyni Moë wrote:
> Zyni Moë <no_email@invalid.invalid> wrote:
>
>>
>> I doubt any implementations use cdr coding now but perhaps I am wrong.
>>
>
> Should have read: 'any stock hardware implementations'
Actually cdr coding was invented and implemented in several Lisp systems
before there were any special hardware for it. Memory used to be a very
precious resource. Think of tiny memories and no virtually addresses.
Glorious Lisp systems lived and thrived in less space than many people
use for their address books today.
--
Jeff Barnett

> In CL it is allowed (but not required) that &rest lists share with the last
> argument to apply. In a case like this what that means is essentially
> this:
>
> (let ((x '(1 2))) (apply (lambda (&rest args) (apply (lambda (&rest args)
> (eq args x)) args) x))
>
> may return true, as (obviously) may
>
> (let ((x '(1 2))) (apply (lambda (&rest args) (eq args x)) x))

Right, ELisp hasn't said a word about it, but given that it's created
a fresh list for the last almost 40 years it de-facto guarantees a fresh copy.

> In a case like
>
> (funcall (lambda (&rest args) args) 1 2)

None of those examples are like the one I showed, tho. The trick in my
example is that the &rest argument is only used by passing it further to
`apply`, so whether it's fresh or not doesn't really matter.
Even better if `FCT` is defined as

(lambda (&rest args) (do foo) (apply bar args))

then when we execute

(funcall FCT <blabla>)

it might be possible to avoid allocating a list at all for those
<blabla> arguments and instead passing them on the stack or even in
registers to `bar`.

Stefan

Jeff Barnett <jbb@notatt.com> wrote:

> Actually cdr coding was invented and implemented in several Lisp systems
> before there were any special hardware for it. Memory used to be a very
> precious resource. Think of tiny memories and no virtually addresses.
> Glorious Lisp systems lived and thrived in less space than many people
> use for their address books today.

Am aware of that. But those machines were very, very different than modern
ones.

--
the small snake

Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> None of those examples are like the one I showed, tho. The trick in my
> example is that the &rest argument is only used by passing it further to
> `apply`, so whether it's fresh or not doesn't really matter.
> Even better if `FCT` is defined as
>
> (lambda (&rest args) (do foo) (apply bar args))
>
> then when we execute
>
> (funcall FCT <blabla>)
>
> it might be possible to avoid allocating a list at all for those
> <blabla> arguments and instead passing them on the stack or even in
> registers to `bar`.
>

Unless you know that bar cannot return this list (or place it in any
structure which outlives a call to it) then you cannot do this. If you do
know that, then if you wish to allow bar to be redefined, then you must
then either be willing to recompile its callers or not do this.

If bar is a variable (as it seems to be in your example) that means you
must know this about all the functions to which it may be bound.

So yes, perhaps system which is able to do heroic whole-program analysis
can do this. Sometimes.

--
the small snake

Zyni Moë [2022-02-03 20:22:00] wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>> None of those examples are like the one I showed, tho. The trick in my
>> example is that the &rest argument is only used by passing it further to
>> `apply`, so whether it's fresh or not doesn't really matter.
>> Even better if `FCT` is defined as
>>
>> (lambda (&rest args) (do foo) (apply bar args))
>>
>> then when we execute
>>
>> (funcall FCT <blabla>)
>>
>> it might be possible to avoid allocating a list at all for those
>> <blabla> arguments and instead passing them on the stack or even in
>> registers to `bar`.
> Unless you know that bar cannot return this list (or place it in any
> structure which outlives a call to it) then you cannot do this.

I think you misunderstood: the stack and/or registers I refer to are
those used by the normal function call API (whichever it is).

If `bar` itself has an `&rest` arg, then we may need to turn those args
into a list after all, but that'd be part of the normal course of
"calling bar".

More specifically the code would simply end up executing the

(apply bar args)

in the same as way as

(funcall bar <blabla>)

would be processed.

> If you do know that, then if you wish to allow bar to be redefined,
> then you must then either be willing to recompile its callers or not
> do this.

I don't think redefinition of bar would cause any issue since the
optimization should only change the execution until we get to `bar` but not
once we're calling `bar` (unless `bar` itself has that same wrapper-like
property of taking a `&rest` only to pass it to `apply`, in which case
the same optimization would apply again, of course).

> So yes, perhaps system which is able to do heroic whole-program analysis
> can do this. Sometimes.

I think the only analysis needed is to discover that the `args` in the
function is only ever passed to `apply` and hence doesn't need to
represented as an actual list but can be represented in any way we fancy
(as long as `apply` also understands it, obviously). And then try and
make use of that info in `funcall` and `apply`.

Stefan

Stefan Monnier <monnier@iro.umontreal.ca> wrote:

>
> I think the only analysis needed is to discover that the `args` in the
> function is only ever passed to `apply` and hence doesn't need to
> represented as an actual list but can be represented in any way we fancy
> (as long as `apply` also understands it, obviously). And then try and
> make use of that info in `funcall` and `apply`.
>

I think what you are saying is that if you can prove some &rest list is
only used in very constrained ways (which may even happen sometimes) you
can stack allocate it because no-one will be able to know you did. Yes.

Also you are free to represent it in linear B, carve into clay tablets, so
long as no-one can tell.

--
the small snake

Zyni Moë [2022-02-05 23:59:51] wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>> I think the only analysis needed is to discover that the `args` in the
>> function is only ever passed to `apply` and hence doesn't need to
>> represented as an actual list but can be represented in any way we fancy
>> (as long as `apply` also understands it, obviously). And then try and
>> make use of that info in `funcall` and `apply`.
>>
>
> I think what you are saying is that if you can prove some &rest list is
> only used in very constrained ways (which may even happen sometimes) you
> can stack allocate it because no-one will be able to know you did. Yes.
>
> Also you are free to represent it in linear B, carve into clay tablets, so
> long as no-one can tell.

That's right. But the original question is not what is legal w.r.t to
the Common Lisp spec, but "what kind of optimizations are performed by
Lisp compilers" ;-)

Stefan