[pro] return-with-dynamic-extent...
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.
On 6 May 2012 22:27, Pascal Costanza <pc@p-cos.net> wrote:
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.
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
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 On Sun, May 6, 2012 at 12:27 PM, Pascal Costanza <pc@p-cos.net> wrote:
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.
_______________________________________________ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
-- Peter Seibel http://www.gigamonkeys.com/
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 On 7 May 2012, at 01:41, Peter Seibel wrote:
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
On Sun, May 6, 2012 at 12:27 PM, Pascal Costanza <pc@p-cos.net> wrote: 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.
_______________________________________________ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
-- Peter Seibel http://www.gigamonkeys.com/
-- Pascal Costanza
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 On Sun, May 6, 2012 at 11:25 PM, Pascal Costanza <pc@p-cos.net> wrote:
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
On 7 May 2012, at 01:41, Peter Seibel wrote:
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
On Sun, May 6, 2012 at 12:27 PM, Pascal Costanza <pc@p-cos.net> wrote:
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.
_______________________________________________ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
-- Peter Seibel http://www.gigamonkeys.com/
-- Pascal Costanza
-- Peter Seibel http://www.gigamonkeys.com/
Ah, that's an interesting idea. I have to think about that. Thanks, Pascal Sent from my iPad On 7 May 2012, at 14:28, Peter Seibel <peter@gigamonkeys.com> wrote:
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
On Sun, May 6, 2012 at 11:25 PM, Pascal Costanza <pc@p-cos.net> wrote: 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
On 7 May 2012, at 01:41, Peter Seibel wrote:
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
On Sun, May 6, 2012 at 12:27 PM, Pascal Costanza <pc@p-cos.net> wrote: 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.
_______________________________________________ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
-- Peter Seibel http://www.gigamonkeys.com/
-- Pascal Costanza
-- Peter Seibel http://www.gigamonkeys.com/
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 On 7 May 2012, at 14:28, Peter Seibel wrote:
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
On Sun, May 6, 2012 at 11:25 PM, Pascal Costanza <pc@p-cos.net> wrote: 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
On 7 May 2012, at 01:41, Peter Seibel wrote:
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
On Sun, May 6, 2012 at 12:27 PM, Pascal Costanza <pc@p-cos.net> wrote: 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.
_______________________________________________ pro mailing list pro@common-lisp.net 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
participants (3)
-
Nikodemus Siivola -
Pascal Costanza -
Peter Seibel