return-with-dynamic-extent...

[Pascal Costanza]

Content preview: Hi, Here is a description of what I think is a feature missing
in Common Lisp, both the standard and current implementations, namely a more
complete way to ensure stack allocation of objects. Based on some recent
experience with translating some C++ benchmarks to Common Lisp - more specifically
the fluid animate benchmark from the PARSEC benchmark suite - being able
to allocate objects on the stack can be a major performance win. Unfortunately,
this is harder than necessary to achieve in Common Lisp. [...]

Content analysis details: (-100.0 points, 5.0 required)

pts rule name description
---- ---------------------- --------------------------------------------------
-0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/, no
trust
[217.70.183.195 listed in list.dnswl.org]
-100 USER_IN_WHITELIST From: address is in the user's white-list
Archived-At: <http://permalink.gmane.org/gmane.lisp.cl-pro/637>

Hi,

Here is a description of what I think is a feature missing in Common Lisp, both the standard and current implementations, namely a more complete way to ensure stack allocation of objects.

Based on some recent experience with translating some C++ benchmarks to Common Lisp - more specifically the fluid animate benchmark from the PARSEC benchmark suite - being able to allocate objects on the stack can be a major performance win. Unfortunately, this is harder than necessary to achieve in Common Lisp.

Here is a simplified example. Assume you have the following class definition in C++:

struct vec {
int x; int y; int z;
vec(int x, int y, int z): x(x), y(y), z(z) {}
};

Then you can define the following operations on such a class:

vec vplus(vec v1, vec v2) {
vec v(v1.x+v2.x, v1.y+v2.y, v1.z+v2.z);
return vec;
}

In such a function definition, the local variable v is stack allocated, plus the return value is returned by value, not by reference. This holds for any intermediate values as well, so if you have other operations like vminus, vmul and vdiv, etc., defined accordingly, you can write expressions like this:

vplus(v1, vmul(v2, v3));

…and rest assured that all intermediate values are allocated on the stack as well. (C++ loses some performance in some cases because it can happen that it relies too much on copying of data structures, but this has been largely resolved in C++11, where move operations are supported really well.)

In Common Lisp, you can declare local variables with dynamic extent:

(let ((v (make-vec :x 1 :y 2 :z 3)))
(declare (dynamic-extent v))
…)

This has the effect that (in Common Lisp that support this) the struct that v refers to is stack allocated. Unfortunately, Common Lisp implementations can only do this for data structure constructors that the implementation knows about - there is no way for users to add additional operations to the set of known dynamic extent 'allocators.'

For example, if you say the following:

(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
v))

…you can be very sure that the resulting program will fail, because the reference to the stack allocated data structure is returned, but the data will be gone afterwards. This had the consequence that in our attempts at translating the fluid animate benchmark, we had to introduce all intermediate results explicitly in separate variables, and be very explicit about all the necessary computational steps. This was very tedious and the result is not nice to look at.

What would be nice is, if we could instead have some form of saying that we want to return a data structure on the stack:

(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
(return-with-dynamic-extent v))

The idea is that now, the data that v refers to is returned by value on the stack. If the call site receives the value with a matching dynamic-extent declaration, then v can just stay on the stack. Same (hopefully) for intermediate results in more complex expressions.

Just like dynamic-extent declarations, an implementation should be allowed to ignore return-with-dynamic-extent and replace it with a mere return form.

To be able to support move operations on the stack, it may be interesting to specify that eq and eql are not reliable anymore for data that is return by return-with-dynamic-extent.

I presented the idea at ELS'12 in Zadar, and Christophe Rhodes commented that it may also be necessary to have some form of global declaim that states that a function will always return something with return-with-dynamic-extent, so it's easier for the compiler to know what to do with a return value.

I don't claim that I have completely thought this through, but I think this should be doable and shouldn't have too many negative consequences for the rest of a system that doesn't use dynamic extents.

I won't be able to implement this, but I just wanted to make sure that the idea is on the table, so someone who is interested may pick it up…


Pascal

--
Pascal Costanza
The views expressed in this email are my own, and not those of my employer.

[Nikodemus Siivola]

Post by Pascal Costanza
What would be nice is, if we could instead have some form of saying that we want to
(defun vplus (v1 v2)
 (let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
                    :y (+ (vec-y v1) (vec-y v2))
                    :z (+ (vec-z v1) (vec-z v2)))))
   (declare (dynamic-extent v))
   (return-with-dynamic-extent v))
The idea is that now, the data that v refers to is returned by value on the stack.
If the call site receives the value with a matching dynamic-extent declaration,
then v can just stay on the stack. Same (hopefully) for intermediate results in
more complex expressions.

I don't see a way to support this in SBCL without massive effort. On
the face of it this is very much at odds with the way SBCL reasons
about stack allocation. No idea about other implementations.

However, you /can/ write code like this in SBCL and "just" have it
work by inlining VPLUS -- and leaving the DX declarations out from
there. If that doesn't produce the expected results, I would consider
it a bug in SBCLs intended level of DX support.

In my experience, what is more helpful is a way to declare the a
certain argument is either dynamic extent (ie. not retained or
incorportated into the result), or specifically incorporated to the
result -- but not retained in any other way.

So:

(declaim (ftype (function ((dynamic-extent t) (result-extent t)) t) foo)

would mean that in

(let ((x (foo (list 1) (list 2)))
(y (foo (list 3) (list 4)))
(declare (dynamic-extent x y))
...)

the compiler would know it can stack allocate (LIST 1) and (LIST 2),
because the first argument to FOO is /always/ DX, and it can also
stack allocate (LIST 4) because the second argument to FOO is DX if
the result of FOO is DX.

SBCL implements the RESULT-EXTENT bit internally for things like FILL,
but the DX argument bit isn't actually in place -- but could be added
almost trivially.

I would guess that implementations supporting DX could take advantage
of such declarations as well with only reasonable (in the "SMOP"
sense...) amount of work.

Cheers,

-- nikodemus

[Peter Seibel]

This is verging on worrying about the color of the bikeshed but why should
EQL not necessarily work with these objects. I can see EQ not working, by
analogy with numbers and characters but EQL should perhaps do a value
comparison. (Hmmm, are you assuming that these objects are immutable? Sort
of seems like they'd better be.)

-Peter

Post by Pascal Costanza
Hi,
Here is a description of what I think is a feature missing in Common Lisp,
both the standard and current implementations, namely a more complete way
to ensure stack allocation of objects.
Based on some recent experience with translating some C++ benchmarks to
Common Lisp - more specifically the fluid animate benchmark from the PARSEC
benchmark suite - being able to allocate objects on the stack can be a
major performance win. Unfortunately, this is harder than necessary to
achieve in Common Lisp.
struct vec {
int x; int y; int z;
vec(int x, int y, int z): x(x), y(y), z(z) {}
};
vec vplus(vec v1, vec v2) {
vec v(v1.x+v2.x, v1.y+v2.y, v1.z+v2.z);
return vec;
}
In such a function definition, the local variable v is stack allocated,
plus the return value is returned by value, not by reference. This holds
for any intermediate values as well, so if you have other operations like
vminus, vmul and vdiv, etc., defined accordingly, you can write expressions
vplus(v1, vmul(v2, v3));

and rest assured that all intermediate values are allocated on the stack
as well. (C++ loses some performance in some cases because it can happen
that it relies too much on copying of data structures, but this has been
largely resolved in C++11, where move operations are supported really well.)
(let ((v (make-vec :x 1 :y 2 :z 3)))
(declare (dynamic-extent v))

)
This has the effect that (in Common Lisp that support this) the struct
that v refers to is stack allocated. Unfortunately, Common Lisp
implementations can only do this for data structure constructors that the
implementation knows about - there is no way for users to add additional
operations to the set of known dynamic extent 'allocators.'
(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
v))

you can be very sure that the resulting program will fail, because the
reference to the stack allocated data structure is returned, but the data
will be gone afterwards. This had the consequence that in our attempts at
translating the fluid animate benchmark, we had to introduce all
intermediate results explicitly in separate variables, and be very explicit
about all the necessary computational steps. This was very tedious and the
result is not nice to look at.
What would be nice is, if we could instead have some form of saying that
(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
(return-with-dynamic-extent v))
The idea is that now, the data that v refers to is returned by value on
the stack. If the call site receives the value with a matching
dynamic-extent declaration, then v can just stay on the stack. Same
(hopefully) for intermediate results in more complex expressions.
Just like dynamic-extent declarations, an implementation should be allowed
to ignore return-with-dynamic-extent and replace it with a mere return form.
To be able to support move operations on the stack, it may be interesting
to specify that eq and eql are not reliable anymore for data that is return
by return-with-dynamic-extent.
I presented the idea at ELS'12 in Zadar, and Christophe Rhodes commented
that it may also be necessary to have some form of global declaim that
states that a function will always return something with
return-with-dynamic-extent, so it's easier for the compiler to know what to
do with a return value.
I don't claim that I have completely thought this through, but I think
this should be doable and shouldn't have too many negative consequences for
the rest of a system that doesn't use dynamic extents.
I won't be able to implement this, but I just wanted to make sure that the
idea is on the table, so someone who is interested may pick it up

Pascal
--
Pascal Costanza
The views expressed in this email are my own, and not those of my employer.
_______________________________________________
pro mailing list
http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro

[Pascal Costanza]

Hi,

I have something like the following in mind:

(defvar *x*)

(defun foo ()
(let ((x (make-bar …)))
(declare (dynamic-extent x))
(setq *x* x)
(return-with-dynamic-extent x)))

(defun test ()
(eql *x* (foo)))

If the result of test is not guaranteed to be t, implementations should have more freedom to move stack-allocated values up and down the stack, which could potentially simplify things internally. For users, I don't think this would be a great restriction, because it seems to me it's unlikely that would want to rely on eq/eql in the first place here…

[eql is not only defined on numbers and chars, but also other objects, and is the same as eq in most cases…]

Pascal

This is verging on worrying about the color of the bikeshed but why should EQL not necessarily work with these objects. I can see EQ not working, by analogy with numbers and characters but EQL should perhaps do a value comparison. (Hmmm, are you assuming that these objects are immutable? Sort of seems like they'd better be.)
-Peter
Hi,
Here is a description of what I think is a feature missing in Common Lisp, both the standard and current implementations, namely a more complete way to ensure stack allocation of objects.
Based on some recent experience with translating some C++ benchmarks to Common Lisp - more specifically the fluid animate benchmark from the PARSEC benchmark suite - being able to allocate objects on the stack can be a major performance win. Unfortunately, this is harder than necessary to achieve in Common Lisp.
struct vec {
int x; int y; int z;
vec(int x, int y, int z): x(x), y(y), z(z) {}
};
vec vplus(vec v1, vec v2) {
vec v(v1.x+v2.x, v1.y+v2.y, v1.z+v2.z);
return vec;
}
vplus(v1, vmul(v2, v3));
…and rest assured that all intermediate values are allocated on the stack as well. (C++ loses some performance in some cases because it can happen that it relies too much on copying of data structures, but this has been largely resolved in C++11, where move operations are supported really well.)
(let ((v (make-vec :x 1 :y 2 :z 3)))
(declare (dynamic-extent v))
…)
This has the effect that (in Common Lisp that support this) the struct that v refers to is stack allocated. Unfortunately, Common Lisp implementations can only do this for data structure constructors that the implementation knows about - there is no way for users to add additional operations to the set of known dynamic extent 'allocators.'
(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
v))
…you can be very sure that the resulting program will fail, because the reference to the stack allocated data structure is returned, but the data will be gone afterwards. This had the consequence that in our attempts at translating the fluid animate benchmark, we had to introduce all intermediate results explicitly in separate variables, and be very explicit about all the necessary computational steps. This was very tedious and the result is not nice to look at.
(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
(return-with-dynamic-extent v))
The idea is that now, the data that v refers to is returned by value on the stack. If the call site receives the value with a matching dynamic-extent declaration, then v can just stay on the stack. Same (hopefully) for intermediate results in more complex expressions.
Just like dynamic-extent declarations, an implementation should be allowed to ignore return-with-dynamic-extent and replace it with a mere return form.
To be able to support move operations on the stack, it may be interesting to specify that eq and eql are not reliable anymore for data that is return by return-with-dynamic-extent.
I presented the idea at ELS'12 in Zadar, and Christophe Rhodes commented that it may also be necessary to have some form of global declaim that states that a function will always return something with return-with-dynamic-extent, so it's easier for the compiler to know what to do with a return value.
I don't claim that I have completely thought this through, but I think this should be doable and shouldn't have too many negative consequences for the rest of a system that doesn't use dynamic extents.
I won't be able to implement this, but I just wanted to make sure that the idea is on the table, so someone who is interested may pick it up…
Pascal
--
Pascal Costanza
The views expressed in this email are my own, and not those of my employer.
_______________________________________________
pro mailing list
http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
--
Peter Seibel
http://www.gigamonkeys.com/

--
Pascal Costanza

[Peter Seibel]

Yes, I'm aware that EQL is defined for all objects. That's what I'm getting
at. It's like EQ except in the case of numbers and chars because those are
immutable objects that can be copied willy-nilly under the covers. EQL is
an abstraction that hides those under the covers shenanigans making
equivalently valued numbers and chars "the same" object (in the terminology
of the spec). It seems to me that in your example since you only made one
object it should be "the same" from the point of view of EQL even if the
compiler has the latitude to make copies that render *x* and the return
value of (foo) not EQ. Or to put it another way, it seems to me that what
your proposing is a mechanism for users to define new types that have some
of the efficiency advantages that currently only numbers and chars are
allowed so I think they should be fit into the language in a similar way.

-Peter

Post by Pascal Costanza
Hi,
(defvar *x*)
(defun foo ()
(let ((x (make-bar 
)))
(declare (dynamic-extent x))
(setq *x* x)
(return-with-dynamic-extent x)))
(defun test ()
(eql *x* (foo)))
If the result of test is not guaranteed to be t, implementations should
have more freedom to move stack-allocated values up and down the stack,
which could potentially simplify things internally. For users, I don't
think this would be a great restriction, because it seems to me it's
unlikely that would want to rely on eq/eql in the first place here

[eql is not only defined on numbers and chars, but also other objects, and
is the same as eq in most cases
]
Pascal
This is verging on worrying about the color of the bikeshed but why should
EQL not necessarily work with these objects. I can see EQ not working, by
analogy with numbers and characters but EQL should perhaps do a value
comparison. (Hmmm, are you assuming that these objects are immutable? Sort
of seems like they'd better be.)
-Peter

Post by Pascal Costanza
Hi,
Here is a description of what I think is a feature missing in Common
Lisp, both the standard and current implementations, namely a more complete
way to ensure stack allocation of objects.
Based on some recent experience with translating some C++ benchmarks to
Common Lisp - more specifically the fluid animate benchmark from the PARSEC
benchmark suite - being able to allocate objects on the stack can be a
major performance win. Unfortunately, this is harder than necessary to
achieve in Common Lisp.
struct vec {
int x; int y; int z;
vec(int x, int y, int z): x(x), y(y), z(z) {}
};
vec vplus(vec v1, vec v2) {
vec v(v1.x+v2.x, v1.y+v2.y, v1.z+v2.z);
return vec;
}
In such a function definition, the local variable v is stack allocated,
plus the return value is returned by value, not by reference. This holds
for any intermediate values as well, so if you have other operations like
vminus, vmul and vdiv, etc., defined accordingly, you can write expressions
vplus(v1, vmul(v2, v3));

and rest assured that all intermediate values are allocated on the stack
as well. (C++ loses some performance in some cases because it can happen
that it relies too much on copying of data structures, but this has been
largely resolved in C++11, where move operations are supported really well.)
(let ((v (make-vec :x 1 :y 2 :z 3)))
(declare (dynamic-extent v))

)
This has the effect that (in Common Lisp that support this) the struct
that v refers to is stack allocated. Unfortunately, Common Lisp
implementations can only do this for data structure constructors that the
implementation knows about - there is no way for users to add additional
operations to the set of known dynamic extent 'allocators.'
(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
v))

you can be very sure that the resulting program will fail, because the
reference to the stack allocated data structure is returned, but the data
will be gone afterwards. This had the consequence that in our attempts at
translating the fluid animate benchmark, we had to introduce all
intermediate results explicitly in separate variables, and be very explicit
about all the necessary computational steps. This was very tedious and the
result is not nice to look at.
What would be nice is, if we could instead have some form of saying that
(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
(return-with-dynamic-extent v))
The idea is that now, the data that v refers to is returned by value on
the stack. If the call site receives the value with a matching
dynamic-extent declaration, then v can just stay on the stack. Same
(hopefully) for intermediate results in more complex expressions.
Just like dynamic-extent declarations, an implementation should be
allowed to ignore return-with-dynamic-extent and replace it with a mere
return form.
To be able to support move operations on the stack, it may be interesting
to specify that eq and eql are not reliable anymore for data that is return
by return-with-dynamic-extent.
I presented the idea at ELS'12 in Zadar, and Christophe Rhodes commented
that it may also be necessary to have some form of global declaim that
states that a function will always return something with
return-with-dynamic-extent, so it's easier for the compiler to know what to
do with a return value.
I don't claim that I have completely thought this through, but I think
this should be doable and shouldn't have too many negative consequences for
the rest of a system that doesn't use dynamic extents.
I won't be able to implement this, but I just wanted to make sure that
the idea is on the table, so someone who is interested may pick it up

Pascal
--
Pascal Costanza
The views expressed in this email are my own, and not those of my employer.
_______________________________________________
pro mailing list
http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro

--
Peter Seibel
http://www.gigamonkeys.com/
--
Pascal Costanza

[Pascal Costanza]

Ah, that's an interesting idea. I have to think about that.

Thanks,
Pascal

Sent from my iPad

Yes, I'm aware that EQL is defined for all objects. That's what I'm getting at. It's like EQ except in the case of numbers and chars because those are immutable objects that can be copied willy-nilly under the covers. EQL is an abstraction that hides those under the covers shenanigans making equivalently valued numbers and chars "the same" object (in the terminology of the spec). It seems to me that in your example since you only made one object it should be "the same" from the point of view of EQL even if the compiler has the latitude to make copies that render *x* and the return value of (foo) not EQ. Or to put it another way, it seems to me that what your proposing is a mechanism for users to define new types that have some of the efficiency advantages that currently only numbers and chars are allowed so I think they should be fit into the language in a similar way.
-Peter
Hi,
(defvar *x*)
(defun foo ()
(let ((x (make-bar 
)))
(declare (dynamic-extent x))
(setq *x* x)
(return-with-dynamic-extent x)))
(defun test ()
(eql *x* (foo)))
If the result of test is not guaranteed to be t, implementations should have more freedom to move stack-allocated values up and down the stack, which could potentially simplify things internally. For users, I don't think this would be a great restriction, because it seems to me it's unlikely that would want to rely on eq/eql in the first place here

[eql is not only defined on numbers and chars, but also other objects, and is the same as eq in most cases
]
Pascal

This is verging on worrying about the color of the bikeshed but why should EQL not necessarily work with these objects. I can see EQ not working, by analogy with numbers and characters but EQL should perhaps do a value comparison. (Hmmm, are you assuming that these objects are immutable? Sort of seems like they'd better be.)
-Peter
Hi,
Here is a description of what I think is a feature missing in Common Lisp, both the standard and current implementations, namely a more complete way to ensure stack allocation of objects.
Based on some recent experience with translating some C++ benchmarks to Common Lisp - more specifically the fluid animate benchmark from the PARSEC benchmark suite - being able to allocate objects on the stack can be a major performance win. Unfortunately, this is harder than necessary to achieve in Common Lisp.
struct vec {
int x; int y; int z;
vec(int x, int y, int z): x(x), y(y), z(z) {}
};
vec vplus(vec v1, vec v2) {
vec v(v1.x+v2.x, v1.y+v2.y, v1.z+v2.z);
return vec;
}
vplus(v1, vmul(v2, v3));

and rest assured that all intermediate values are allocated on the stack as well. (C++ loses some performance in some cases because it can happen that it relies too much on copying of data structures, but this has been largely resolved in C++11, where move operations are supported really well.)
(let ((v (make-vec :x 1 :y 2 :z 3)))
(declare (dynamic-extent v))

)
This has the effect that (in Common Lisp that support this) the struct that v refers to is stack allocated. Unfortunately, Common Lisp implementations can only do this for data structure constructors that the implementation knows about - there is no way for users to add additional operations to the set of known dynamic extent 'allocators.'
(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
v))

you can be very sure that the resulting program will fail, because the reference to the stack allocated data structure is returned, but the data will be gone afterwards. This had the consequence that in our attempts at translating the fluid animate benchmark, we had to introduce all intermediate results explicitly in separate variables, and be very explicit about all the necessary computational steps. This was very tedious and the result is not nice to look at.
(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
(return-with-dynamic-extent v))
The idea is that now, the data that v refers to is returned by value on the stack. If the call site receives the value with a matching dynamic-extent declaration, then v can just stay on the stack. Same (hopefully) for intermediate results in more complex expressions.
Just like dynamic-extent declarations, an implementation should be allowed to ignore return-with-dynamic-extent and replace it with a mere return form.
To be able to support move operations on the stack, it may be interesting to specify that eq and eql are not reliable anymore for data that is return by return-with-dynamic-extent.
I presented the idea at ELS'12 in Zadar, and Christophe Rhodes commented that it may also be necessary to have some form of global declaim that states that a function will always return something with return-with-dynamic-extent, so it's easier for the compiler to know what to do with a return value.
I don't claim that I have completely thought this through, but I think this should be doable and shouldn't have too many negative consequences for the rest of a system that doesn't use dynamic extents.
I won't be able to implement this, but I just wanted to make sure that the idea is on the table, so someone who is interested may pick it up

Pascal
--
Pascal Costanza
The views expressed in this email are my own, and not those of my employer.
_______________________________________________
pro mailing list
http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
--
Peter Seibel
http://www.gigamonkeys.com/

--
Pascal Costanza
--
Peter Seibel
http://www.gigamonkeys.com/

[Pascal Costanza]

Hm, ok. That's an interesting view on this. You're basically suggesting to introduce what is called in some languages a "value" type (records/structs that can only be used by value, not by reference). That's more or less what structs in C/C++ are when passed to and returned from functions as values.

I guess that should be possible in principle. But I'm wondering if this would go too far in the direction of requiring support from the language. What I had in mind was more some form of optimization declaration, that might as well be safely ignored by the compiler (or disabled in debug mode)…

Pascal

Yes, I'm aware that EQL is defined for all objects. That's what I'm getting at. It's like EQ except in the case of numbers and chars because those are immutable objects that can be copied willy-nilly under the covers. EQL is an abstraction that hides those under the covers shenanigans making equivalently valued numbers and chars "the same" object (in the terminology of the spec). It seems to me that in your example since you only made one object it should be "the same" from the point of view of EQL even if the compiler has the latitude to make copies that render *x* and the return value of (foo) not EQ. Or to put it another way, it seems to me that what your proposing is a mechanism for users to define new types that have some of the efficiency advantages that currently only numbers and chars are allowed so I think they should be fit into the language in a similar way.
-Peter
Hi,
(defvar *x*)
(defun foo ()
(let ((x (make-bar …)))
(declare (dynamic-extent x))
(setq *x* x)
(return-with-dynamic-extent x)))
(defun test ()
(eql *x* (foo)))
If the result of test is not guaranteed to be t, implementations should have more freedom to move stack-allocated values up and down the stack, which could potentially simplify things internally. For users, I don't think this would be a great restriction, because it seems to me it's unlikely that would want to rely on eq/eql in the first place here…
[eql is not only defined on numbers and chars, but also other objects, and is the same as eq in most cases…]
Pascal

This is verging on worrying about the color of the bikeshed but why should EQL not necessarily work with these objects. I can see EQ not working, by analogy with numbers and characters but EQL should perhaps do a value comparison. (Hmmm, are you assuming that these objects are immutable? Sort of seems like they'd better be.)
-Peter
Hi,
Here is a description of what I think is a feature missing in Common Lisp, both the standard and current implementations, namely a more complete way to ensure stack allocation of objects.
Based on some recent experience with translating some C++ benchmarks to Common Lisp - more specifically the fluid animate benchmark from the PARSEC benchmark suite - being able to allocate objects on the stack can be a major performance win. Unfortunately, this is harder than necessary to achieve in Common Lisp.
struct vec {
int x; int y; int z;
vec(int x, int y, int z): x(x), y(y), z(z) {}
};
vec vplus(vec v1, vec v2) {
vec v(v1.x+v2.x, v1.y+v2.y, v1.z+v2.z);
return vec;
}
vplus(v1, vmul(v2, v3));
…and rest assured that all intermediate values are allocated on the stack as well. (C++ loses some performance in some cases because it can happen that it relies too much on copying of data structures, but this has been largely resolved in C++11, where move operations are supported really well.)
(let ((v (make-vec :x 1 :y 2 :z 3)))
(declare (dynamic-extent v))
…)
This has the effect that (in Common Lisp that support this) the struct that v refers to is stack allocated. Unfortunately, Common Lisp implementations can only do this for data structure constructors that the implementation knows about - there is no way for users to add additional operations to the set of known dynamic extent 'allocators.'
(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
v))
…you can be very sure that the resulting program will fail, because the reference to the stack allocated data structure is returned, but the data will be gone afterwards. This had the consequence that in our attempts at translating the fluid animate benchmark, we had to introduce all intermediate results explicitly in separate variables, and be very explicit about all the necessary computational steps. This was very tedious and the result is not nice to look at.
(defun vplus (v1 v2)
(let ((v (make-vec :x (+ (vec-x v1) (vec-x v2))
:y (+ (vec-y v1) (vec-y v2))
:z (+ (vec-z v1) (vec-z v2)))))
(declare (dynamic-extent v))
(return-with-dynamic-extent v))
The idea is that now, the data that v refers to is returned by value on the stack. If the call site receives the value with a matching dynamic-extent declaration, then v can just stay on the stack. Same (hopefully) for intermediate results in more complex expressions.
Just like dynamic-extent declarations, an implementation should be allowed to ignore return-with-dynamic-extent and replace it with a mere return form.
To be able to support move operations on the stack, it may be interesting to specify that eq and eql are not reliable anymore for data that is return by return-with-dynamic-extent.
I presented the idea at ELS'12 in Zadar, and Christophe Rhodes commented that it may also be necessary to have some form of global declaim that states that a function will always return something with return-with-dynamic-extent, so it's easier for the compiler to know what to do with a return value.
I don't claim that I have completely thought this through, but I think this should be doable and shouldn't have too many negative consequences for the rest of a system that doesn't use dynamic extents.
I won't be able to implement this, but I just wanted to make sure that the idea is on the table, so someone who is interested may pick it up…
Pascal
--
Pascal Costanza
The views expressed in this email are my own, and not those of my employer.
_______________________________________________
pro mailing list
http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
--
Peter Seibel
http://www.gigamonkeys.com/

--
Pascal Costanza
--
Peter Seibel
http://www.gigamonkeys.com/

--
Pascal Costanza