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
[email protected]
http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
