Using an idea from Carl and some code from Lynn Quam that he sent many years ago, I have checked in support for static arrays. These look like Lisp arrays in just about every way except that GC will not move them. GC will clean them up if they become garbage. This is done be creating the array storage by malloc'ing space. To create a static array, use make-array with :allocation :static. Limitations: * Since arrays are malloc'ed, the size and number of static arrays is limited to the size of the C heap, which is relatively small. * You are currently prevented from using adjust-array to change the size of the array. (If the array grows, new malloc'ed space would be needed, and then the address would change, so this is disabled.) * Only certain unboxed element types are allowed: strings; 8, 16, and 32 bit integers (signed and unsigned); single and double floats; and complex single and double floats. * You cannot dump a static array. Well, you can, but the reloaded array is no longer static. No warning or error is currently issued. * You cannot make a displaced, static array. * You cannot make an adjustable static array. The interface and implementation are still open. Suggestions welcome on the appropriate interface and behavior. The next snapshot will have this feature. Ray
Sounds good to me. I have been using foreign code to accomplish this for many years. The only problem with this implementation is that the static arrays must be explicitly reclaimed. Allegro Common Lisp supports garbage collectable static arrays (and some other structures) using the :allocation :lispstatic-reclaimable keyword to make-array. Raymond Toy wrote:
Using an idea from Carl and some code from Lynn Quam that he sent many years ago, I have checked in support for static arrays. These look like Lisp arrays in just about every way except that GC will not move them. GC will clean them up if they become garbage. This is done be creating the array storage by malloc'ing space.
To create a static array, use make-array with :allocation :static.
Limitations:
* Since arrays are malloc'ed, the size and number of static arrays is limited to the size of the C heap, which is relatively small. * You are currently prevented from using adjust-array to change the size of the array. (If the array grows, new malloc'ed space would be needed, and then the address would change, so this is disabled.) * Only certain unboxed element types are allowed: strings; 8, 16, and 32 bit integers (signed and unsigned); single and double floats; and complex single and double floats. * You cannot dump a static array. Well, you can, but the reloaded array is no longer static. No warning or error is currently issued. * You cannot make a displaced, static array. * You cannot make an adjustable static array.
The interface and implementation are still open. Suggestions welcome on the appropriate interface and behavior. The next snapshot will have this feature.
Ray
On Mon, Nov 30, 2009 at 10:08 AM, Lynn Quam <quam@ai.sri.com> wrote:
Sounds good to me. I have been using foreign code to accomplish this for many years. The only problem with this implementation is that the static arrays must be explicitly reclaimed.
A finalizer is attached to the array header but not to the data array. Come to think of it, it is not clear that it should not just be the other way around. This may require some work around the weak pointer code.
Carl Shapiro wrote:
On Mon, Nov 30, 2009 at 10:08 AM, Lynn Quam <quam@ai.sri.com> wrote:
Sounds good to me. I have been using foreign code to accomplish this for many years. The only problem with this implementation is that the static arrays must be explicitly reclaimed.
A finalizer is attached to the array header but not to the data array. Come to think of it, it is not clear that it should not just be the other way around. This may require some work around the weak pointer code.
It's done this way because the data array is never really seen by GC since it's not in the from space (or even to space). Without the array header, I don't know how to tell that the array is garbage. I think Lynn and I did some experiments long ago with weak pointers and static arrays (lisp heap) but couldn't figure out how to break the weak pointer so that the object could be reclaimed. And this reminds of one more limitation: Don't grab a hold of the data vector of the array and drop all references to the array itself. The data vector will be GCed out from underneath you. But the only way to grab the data vector is to use CMUCL-specific functions, so if you do this, you're on your own. This limitation would go away if we could figure out how to make Carl's suggestion work. (I think his idea is a better implementation.) Ray
On Mon, Nov 30, 2009 at 7:04 AM, Raymond Toy <toy.raymond@gmail.com> wrote:
To create a static array, use make-array with :allocation :static.
It would be great if the name :static could be reserved for the static part of the Lisp heap. The name :malloc is more descriptive and less ambiguous.
* Only certain unboxed element types are allowed: strings; 8, 16, and 32 bit integers (signed and unsigned); single and double floats; and complex single and double floats.
Can we invert the test and have an exclusion for arrays of type T and include everything else?
Carl Shapiro wrote:
On Mon, Nov 30, 2009 at 7:04 AM, Raymond Toy <toy.raymond@gmail.com> wrote:
To create a static array, use make-array with :allocation :static.
It would be great if the name :static could be reserved for the static part of the Lisp heap. The name :malloc is more descriptive and less ambiguous.
Works for me.
* Only certain unboxed element types are allowed: strings; 8, 16, and 32 bit integers (signed and unsigned); single and double floats; and complex single and double floats.
Can we invert the test and have an exclusion for arrays of type T and include everything else?
Yes, except that we probably also want to exclude (signed-byte 30), which are boxed fixnums. Ray
On Dec 1, 2009, at 24:16 , Raymond Toy wrote:
Carl Shapiro wrote:
On Mon, Nov 30, 2009 at 7:04 AM, Raymond Toy <toy.raymond@gmail.com> wrote:
To create a static array, use make-array with :allocation :static.
It would be great if the name :static could be reserved for the static part of the Lisp heap. The name :malloc is more descriptive and less ambiguous.
Works for me.
What about :pinned? (Just suggesting) Cheers -- Marco
Marco Antoniotti wrote:
On Dec 1, 2009, at 24:16 , Raymond Toy wrote:
Carl Shapiro wrote:
On Mon, Nov 30, 2009 at 7:04 AM, Raymond Toy <toy.raymond@gmail.com> wrote:
To create a static array, use make-array with :allocation :static.
It would be great if the name :static could be reserved for the static part of the Lisp heap. The name :malloc is more descriptive and less ambiguous.
Works for me.
What about :pinned? (Just suggesting)
Perhaps we can follow Allegro's lead? <http://www.franz.com/support/documentation/current/doc/implementation.htm#cl-make-array-2> (No particular reason, other than to be somewhat compatible.) So, our :static/:malloc is the same as Allegro's :static-reclaimable. We could add make our :static/:malloc the same as Allegro's :static/:malloc since Allegro requires you to explicitly free such objects. These objects are the malloc'ed foreign arrays that we now create. The main difference is that we can't reload such arrays (currently). I've already updated the code to use :malloc, but we have plenty of time before the snapshot to change behavior. Ray
There are a number of subtleties in implementing the "static" arrays. The Allegro :ALLOCATION keyword argument to MAKE-ARRAY is interpreted as follows (taken from the Allegro 7.0 documentation): |:static| or |:malloc| || Allocate the new array in malloc (foreign) space. The array will never be touched by the garbage collector and must be deallocated explicitly. Only a restricted number of element types are supported for static arrays. They are listed below. :malloc and :static are synonyms. |:static-reclaimable| Allocate the new array data in malloc (foreign) space and the header in Lisp space. The data will never be touched by the garbage collector but it will be deallocated when there are no pointers from Lisp (using a finalization). Only a restricted number of element types are supported for static arrays. They are listed below. || || |:lispstatic-reclaimable| Allocate the new array in malloc (foreign) space. The array will never be touched by the garbage collector until there are no pointers from Lisp, at which point the whole array will be deallocated explicitly. Any Lisp type can be contained in the array. It is important to note the difference between |:static-reclaimable| and |:lispstatic-reclaimable|. I think that |:lispstatic-reclaimable is what needs to be implemented for CMUCL. |An array allocated as |:static-reclaimable| cannot be a simple-array in CMUCL since the array data does not immediately follow the header. Therefore, it is difficult to compile inline array accesses unless KERNEL::%WITH-ARRAY-DATA or kernel::%array-data-vector is used to get the actual data-vector. || Raymond Toy wrote:
Marco Antoniotti wrote:
On Dec 1, 2009, at 24:16 , Raymond Toy wrote:
Carl Shapiro wrote:
On Mon, Nov 30, 2009 at 7:04 AM, Raymond Toy <toy.raymond@gmail.com> wrote:
To create a static array, use make-array with :allocation :static.
It would be great if the name :static could be reserved for the static part of the Lisp heap. The name :malloc is more descriptive and less ambiguous.
Works for me.
What about :pinned? (Just suggesting)
Perhaps we can follow Allegro's lead? <http://www.franz.com/support/documentation/current/doc/implementation.htm#cl-make-array-2> (No particular reason, other than to be somewhat compatible.)
So, our :static/:malloc is the same as Allegro's :static-reclaimable. We could add make our :static/:malloc the same as Allegro's :static/:malloc since Allegro requires you to explicitly free such objects. These objects are the malloc'ed foreign arrays that we now create. The main difference is that we can't reload such arrays (currently).
I've already updated the code to use :malloc, but we have plenty of time before the snapshot to change behavior.
Ray
Lynn Quam wrote:
There are a number of subtleties in implementing the "static" arrays. The Allegro :ALLOCATION keyword argument to MAKE-ARRAY is interpreted as follows (taken from the Allegro 7.0 documentation):
|:static| or |:malloc| ||
Allocate the new array in malloc (foreign) space. The array will never be touched by the garbage collector and must be deallocated explicitly. Only a restricted number of element types are supported for static arrays. They are listed below. :malloc and :static are synonyms.
I believe this is what the is currently implemented using your foreign vectors. (Except there's no function to deallocate such vectors currently.) And they are vectors, not n-dimensional arrays. These are also no currently exported but could be if desired.
|:static-reclaimable|
Allocate the new array data in malloc (foreign) space and the header in Lisp space. The data will never be touched by the garbage collector but it will be deallocated when there are no pointers from Lisp (using a finalization). Only a restricted number of element types are supported for static arrays. They are listed below.
This is how the static vectors are implemented. A complex array header is allocated, and the data vector slot is the foreign vector (static/malloc vector above). We use a finalizer to free the foreign vector when the complex array header becomes garbage.
|| ||
|:lispstatic-reclaimable|
Allocate the new array in malloc (foreign) space. The array will never be touched by the garbage collector until there are no pointers from Lisp, at which point the whole array will be deallocated explicitly. Any Lisp type can be contained in the array.
This is not currently implemented. If any Lisp type can be contained in the array, we'll have to teach GC to scan the array elements in case a lisp object moves. And I'm not sure how to tell when such an array becomes garbage.
It is important to note the difference between |:static-reclaimable| and |:lispstatic-reclaimable|. I think that |:lispstatic-reclaimable is what needs to be implemented for CMUCL. |An array allocated as |:static-reclaimable| cannot be a simple-array in CMUCL since the array data does not immediately follow the header. Therefore, it is difficult to compile inline array accesses unless KERNEL::%WITH-ARRAY-DATA or kernel::%array-data-vector is used to get the actual data-vector. ||
Yes, the current static arrays are not simple-arrays. And n-dimensional arrays always have array headers, so inline access is never done in that case But some time ago I measured the difference between arrays with and without the array header and there was only a 10-25% (?) difference. (I think I compared 2D arrays, so perhaps that's not a good test.) Ray
Many years back, Jon L White at Lucid Inc considered a new array declaration which would allow the inlining of non-simple arrays. The declaration form was (declare (type (non-simple-array <element-type> <bounds>) . <vars> )) The compiled code would always assume that the array was non-simple, and indirect thru the array header to find underlying array. I do not remember all of the details and limitations, except that the underling simple-vector could always be found with only one indirection. Raymond Toy wrote:
Lynn Quam wrote:
There are a number of subtleties in implementing the "static" arrays. The Allegro :ALLOCATION keyword argument to MAKE-ARRAY is interpreted as follows (taken from the Allegro 7.0 documentation):
|:static| or |:malloc| ||
Allocate the new array in malloc (foreign) space. The array will never be touched by the garbage collector and must be deallocated explicitly. Only a restricted number of element types are supported for static arrays. They are listed below. :malloc and :static are synonyms.
I believe this is what the is currently implemented using your foreign vectors. (Except there's no function to deallocate such vectors currently.) And they are vectors, not n-dimensional arrays.
These are also no currently exported but could be if desired.
|:static-reclaimable|
Allocate the new array data in malloc (foreign) space and the header in Lisp space. The data will never be touched by the garbage collector but it will be deallocated when there are no pointers from Lisp (using a finalization). Only a restricted number of element types are supported for static arrays. They are listed below.
This is how the static vectors are implemented. A complex array header is allocated, and the data vector slot is the foreign vector (static/malloc vector above). We use a finalizer to free the foreign vector when the complex array header becomes garbage.
|| ||
|:lispstatic-reclaimable|
Allocate the new array in malloc (foreign) space. The array will never be touched by the garbage collector until there are no pointers from Lisp, at which point the whole array will be deallocated explicitly. Any Lisp type can be contained in the array.
This is not currently implemented. If any Lisp type can be contained in the array, we'll have to teach GC to scan the array elements in case a lisp object moves. And I'm not sure how to tell when such an array becomes garbage.
It is important to note the difference between |:static-reclaimable| and |:lispstatic-reclaimable|. I think that |:lispstatic-reclaimable is what needs to be implemented for CMUCL. |An array allocated as |:static-reclaimable| cannot be a simple-array in CMUCL since the array data does not immediately follow the header. Therefore, it is difficult to compile inline array accesses unless KERNEL::%WITH-ARRAY-DATA or kernel::%array-data-vector is used to get the actual data-vector. ||
Yes, the current static arrays are not simple-arrays. And n-dimensional arrays always have array headers, so inline access is never done in that case But some time ago I measured the difference between arrays with and without the array header and there was only a 10-25% (?) difference. (I think I compared 2D arrays, so perhaps that's not a good test.)
Ray
On Tue, Dec 1, 2009 at 4:49 PM, Lynn Quam <quam@ai.sri.com> wrote:
The compiled code would always assume that the array was non-simple, and indirect thru the array header to find underlying array. I do not remember all of the details and limitations, except that the underling simple-vector could always be found with only one indirection.
If an array is not simple it may be displaced. In this case, one has to chase the through all of underlying arrays until a terminal simple array is found. It would be nice if there was a way to never pay for a displaced array if you never use them.
* Carl Shapiro Wrote on Tue, 1 Dec 2009 18:36:56 -0800: |> The compiled code would always assume that the array was non-simple, |> and indirect thru the array header to find underlying array. I do |> not remember all of the details and limitations, except that the |> underling simple-vector could always be found with only one |> indirection. | | If an array is not simple it may be displaced. In this case, one has | to chase the through all of underlying arrays until a terminal simple | array is found. It would be nice if there was a way to never pay for | a displaced array if you never use them. Is there really a cost here if the array is simple and you are chasing only one level? I thought your arguments in advocating the costs of multi-byte encodings would apply to this case. -- Madhu
How do you make a declaration to get good inline compiled references to the proposed static-array that are non-simple arrays indirected thru a header? Am I missing something? Madhu wrote:
* Carl Shapiro Wrote on Tue, 1 Dec 2009 18:36:56 -0800:
|> The compiled code would always assume that the array was non-simple, |> and indirect thru the array header to find underlying array. I do |> not remember all of the details and limitations, except that the |> underling simple-vector could always be found with only one |> indirection. | | If an array is not simple it may be displaced. In this case, one has | to chase the through all of underlying arrays until a terminal simple | array is found. It would be nice if there was a way to never pay for | a displaced array if you never use them.
Is there really a cost here if the array is simple and you are chasing only one level? I thought your arguments in advocating the costs of multi-byte encodings would apply to this case.
-- Madhu
On Tue, Dec 1, 2009 at 7:30 PM, Madhu <enometh@meer.net> wrote:
Is there really a cost here if the array is simple and you are chasing only one level? I thought your arguments in advocating the costs of multi-byte encodings would apply to this case.
I do not see how these are related, can you elaborate?
* Carl Shapiro <Wrote on Tue, 1 Dec 2009 21:55:30 -0800> | On Tue, Dec 1, 2009 at 7:30 PM, Madhu <enometh@meer.net> wrote: |> Is there really a cost here if the array is simple and you are chasing |> only one level? I thought your arguments in advocating the costs of |> multi-byte encodings would apply to this case. | | I do not see how these are related, can you elaborate? Perhaps it would be clearer if you explained your idea first, I don't think it has been disclosed on this list. My objection was to your hypothesising upthread, regarding costs. -- Madhu
Lynn Quam wrote:
Many years back, Jon L White at Lucid Inc considered a new array declaration which would allow the inlining of non-simple arrays. The declaration form was
(declare (type (non-simple-array <element-type> <bounds>) . <vars> ))
The compiled code would always assume that the array was non-simple, and indirect thru the array header to find underlying array. I do not remember all of the details and limitations, except that the underling simple-vector could always be found with only one indirection. Ok. We don't have to have any special declaration or deal with the cost of indirection. I've checked in some changes that will properly GC static arrays. Nothing fancy and it seems to work with some simple tests, and CMUCL builds itself just fine.
Ray
I have checked out the lastest CVS sources, containing make-static-array, and have built for x86-linux. I will run some tests using FREEDIUS, which makes extensive uses of foreign-vectors. I have examined the sources and the implementation looks like it should work well. Raymond Toy wrote:
Lynn Quam wrote:
Many years back, Jon L White at Lucid Inc considered a new array declaration which would allow the inlining of non-simple arrays. The declaration form was
(declare (type (non-simple-array <element-type> <bounds>) . <vars> ))
The compiled code would always assume that the array was non-simple, and indirect thru the array header to find underlying array. I do not remember all of the details and limitations, except that the underling simple-vector could always be found with only one indirection.
Ok. We don't have to have any special declaration or deal with the cost of indirection. I've checked in some changes that will properly GC static arrays. Nothing fancy and it seems to work with some simple tests, and CMUCL builds itself just fine.
Ray
I have checked out the lastest CVS sources, containing make-static-array, and have built for x86-linux. I will run some tests using FREEDIUS, which makes extensive uses of foreign-vectors. I have examined the sources and the implementation looks like it should work well. I appreciate your testing of this. You may want to turn off the debugging prints I left in gencgc.c and code/array.lisp. But it would be interesting to see what other kinds of strange pointer objects are in
Lynn Quam wrote: the heap. On Linux, I see 0xffffffe9. Ray
participants (5)
-
Carl Shapiro -
Lynn Quam -
Madhu -
Marco Antoniotti -
Raymond Toy