On 1/14/2022 11:56 AM, Stefan Monnier wrote:
Does anyone here knows what kind of optimizations are performed by LispI believe that some stack allocate the lists and cdr code them there.
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))
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.
Does anyone here knows what kind of optimizations are performed by Lisp compilers to try and avoid allocating lists for the &rest arguments?I believe that some stack allocate the lists and cdr code them there.
I'm thinking especially at cases like
(lambda (&rest args) (do foo) (apply bar args))
Jeff Barnett [2022-01-14 13:18:07] wrote:Unfortunately, I don't. I haven't thought about this in years. But there
On 1/14/2022 11:56 AM, Stefan Monnier wrote:
Does anyone here knows what kind of optimizations are performed by LispI believe that some stack allocate the lists and cdr code them there.
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))
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"?
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 doubt any implementations use cdr coding now but perhaps I am wrong.
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)
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.
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 Monnier <monnier@iro.umontreal.ca> wrote:
None of those examples are like the one I showed, tho. The trick in myUnless 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.
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`.
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.
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 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.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 296 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 54:21:38 |
| Calls: | 6,650 |
| Calls today: | 2 |
| Files: | 12,200 |
| Messages: | 5,330,625 |