[pro] return-with-dynamic-extent...

[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.

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.