(simple-vector 20) vs (vector single-float 20) 
Author Message
 (simple-vector 20) vs (vector single-float 20)

Which is more efficient?
        (simple-array single-float (20))
        (vector single-float 20)
        (simple-vector 20)
I'd think that the first one would be the most efficient, but svref
works only with the latter. I'm running in Lucid 4.0.1 and Allegro 4.1.

--mark



Sat, 04 Nov 1995 04:13:12 GMT  
 (simple-vector 20) vs (vector single-float 20)
|> Which is more efficient?
|>   (simple-array single-float (20))
|>   (vector single-float 20)
|>   (simple-vector 20)
|> I'd think that the first one would be the most efficient, but svref
|> works only with the latter. I'm running in Lucid 4.0.1 and Allegro 4.1.
|>
|> --mark

The answer is heavily dependent on the underlying Lisp implementation,
so you probably need a answer from both Lucid and Franz.
It also on what you are trying to be efficient about.

A (simple-array single-float (20)) is probably identical to
the (vector single-float 20), as the compiler probably converts both
forms into the same thing.  The advantage of this form is that
the system has the option of putting the float-bits directly in the array, so you
save memory and indirection when accessing the floats, and hopefully
the compiler can recognize this and generate floating point arithmetic code
that operates on elements of the array directly.
So a (setf (aref float-array 10) (+ 1.0 (aref float-array 10)))
would compile into really efficient inline code like:
 (let ((float-bits-pointer "&"(aref float-array 10)))
    (float-add3 float-bits-pointer 1.0 float-bits-pointer))

If the compiler wasn't smart enough, it could end up being less efficient
to operate on the elements, since the system would "box" or cons new
lisp floats on all array accesses to operate on the values.
So you get something like:
  (let ((lisp-float-object (cons-float "&"(aref float-array 10)))
    (setf (aref float-array 10) (uncons-float (+ 1.0 lisp-float-object))))

A (simple-vector 20) and SVREF will always hold "boxed" floats, so
you don't need to cons them up on access, or uncons them when storing them.
But then the compiler does not have the option of generating real efficient
inline code. However, if the values are mostly read-only, then this may
actually be more efficient, since it is faster to access the boxed values
and move them around (i.e. pass as parameters, store in other places).

The only true way to find out is to write test programs and experiment.
If you look at disassembled compiler output, you can likely determine whether
the floats get boxed up or not.

-Kelly



Sun, 05 Nov 1995 00:32:12 GMT  
 (simple-vector 20) vs (vector single-float 20)

Quote:

> Which is more efficient?
>         (simple-array single-float (20))
>         (vector single-float 20)
>         (simple-vector 20)
> I'd think that the first one would be the most efficient, but svref
> works only with the latter. I'm running in Lucid 4.0.1 and Allegro 4.1.

> --mark

SVREF is a special flavor of AREF that only works with SIMPLE-VECTORs.
It is not necessarily faster or slower then AREF on other kinds of
arrays.  In fact, in CMUCL, (svref v x) is converted into (aref (the
simple-vector v) x) by the compiler.

Your three type declarations all indicate a different kind of vector.
Which is more effecient depends on what kind of vector your
implementation of common lisp does best.

Quote:
>         (simple-array single-float (20))

This indicates that you have a simple array of single floats, with one
dimension of 20.  The one dimension means that it is a vector (the
definition of vector).  The simple means that it is not necessarily
adjustable, does not have a fill pointer, and is not displaced.  The
single-float means that you will only ever put single floats in it, so
if the implementation supports a special kind of array for
single-floats it can use it.

Quote:
>         (vector single-float 20)

This is just shorthand for (array single-float (20)), which is the
same as the first, except for the simple.  As this is not necessarily
simple, each time the array is accessed, it will have to be checked
for displacement, fill pointers, etc.

Quote:
>         (simple-vector 20)

This is shorthand for (simple-array t (20)).  The difference between
this and the first one is that it says that the array has to be able
to hold anything, so the compiler cannot use a specialized array type.

Note: simple-vector does not mean ``a vector that is simple.''  It
means ``a vector of T that is simple.''  Even though simple-array just
means ``an array that is simple'' and indicates nothing about the
element type.  [Can you say ``Common Lisp is consistent''?  If so, you
lie.]

Anyway, in CMUCL the first is the most effecient, then the third, then
the second.  Specifically, if you were to say:

        (+ (the single-float (aref v 0)) 1.0)

with v declared with each of these types, the resultant code would be:

For (simple-array single-float (20)):
        load 32 bits directly from the vector into the fp unit
        [the single-float check can be optimized away]
        load the constant 1.0 into the fp unit
        do the add

For (vector single-float 20):
        call the out-of-line aref routine
                (can only inline accesses to simple arrays)
        unbox the heap allocated result
        [the single-float check can be optimized away]
        load the constant 1.0 into the fp unit
        do the add

The out-of-line aref routine has to:
        check the type, notice that it really is simple.
        do the access
        copy the value into the heap
        return a pointer to the heap allocated float

For (simple-vector 20):
        load the 32-bit descriptor from the vector
        check to make sure it really is a single-float
                [not done if safety=0]
        load the 32-bit single-float from the heap into the fp unit
        load 1.0 as a constant
        do the add.

So the ``simple'' saves you a lot, and the ``single-float'' saves you
some consing and an extra indirection.

I would assume most other lisps are the same way.

-William Lott
CMU Common Lisp Group



Sun, 05 Nov 1995 01:07:56 GMT  
 (simple-vector 20) vs (vector single-float 20)

Quote:

> A (simple-array single-float (20)) is probably identical to the (vector
> single-float 20), as the compiler probably converts both forms into the same
> thing.  The advantage of this form is that the system has the option of
> putting the float-bits directly in the array, so you save memory and
> indirection when accessing the floats, and hopefully the compiler can
> recognize this and generate floating point arithmetic code that operates on
> elements of the array directly.

Can anyone comment on which major LISP implementations perform optimizations
like this?  How about folding structures directly into vectors?  How about
floats or structures into structures?  Etc.

Thanks!

Bruce Krulwich



Sun, 05 Nov 1995 17:40:00 GMT  
 (simple-vector 20) vs (vector single-float 20)

Quote:

>> A (simple-array single-float (20)) is probably identical to the (vector
>> single-float 20), as the compiler probably converts both forms into the same
>> thing.  The advantage of this form is that the system has the option of
>> putting the float-bits directly in the array, so you save memory and
>> indirection when accessing the floats, and hopefully the compiler can
>> recognize this and generate floating point arithmetic code that operates on
>> elements of the array directly.

>Can anyone comment on which major LISP implementations perform optimizations
>like this?

Lucid implements floating point arrays using immediate data rather than
boxed floats.

Quote:
>         How about folding structures directly into vectors?  How about
>floats or structures into structures?  Etc.

Most Common Lisps implement non-:TYPEd structures as vectors, with a flag
so that they structures can be distinguished from other types of vectors.
Are you asking whether they optimize the case where all the slots specify
:TYPE SINGLE-FLOAT and generate a vector with unboxed single floats?  I
haven't heard of implementations that do that.

Or are you asking about optimizing (vector structure-type) so that the
structure elements are laid out in the vector (as in conventional languages
like PL/I, Pascal, and C) rather than generating a vector of pointers to
separate heap-allocated structures?  I don't think this would be valid,
because Lisp structures have first-class status as objects.  If the program
contains:

        (setq foo (aref vector 0))
        (setf (aref vector 0) bar)

The second assignment must not affect the object that FOO references.

The same is true about structure elements that are other structures.  The
:INCLUDE option provides a limited form of this, though.
--
Barry Margolin
System Manager, Thinking Machines Corp.




Wed, 08 Nov 1995 00:12:42 GMT  
 (simple-vector 20) vs (vector single-float 20)

Quote:

> Most Common Lisps implement non-:TYPEd structures as vectors, with a flag
> so that they structures can be distinguished from other types of vectors.
> Are you asking whether they optimize the case where all the slots specify
> :TYPE SINGLE-FLOAT and generate a vector with unboxed single floats?  I
> haven't heard of implementations that do that.

The current alpha version of CMUCL (not yet available, sorry) does
something sorta like that.  When DEFSTRUCT sees any slot types that
would benifit by being stored in memory unboxed, it allocates one slot
in the structure that holds a vector of raw data, and then allocates
all these non-descriptor slots in this sub-vector.

Despite the extra indirection, the cost is better.  This is because
there is an extra indirection no matter what.  If heap allocated
objects were stored directly in slots in the main structure they would
each have to be indirected to get at the real bits anyway.  The main
advantage comes from not having to keep boxing results before putting
them in the vector, and the overall amount of same used is reduced
because there is only one header for all the non-descriptor stuff
instead of a header per object.

In other words:

        (defstruct ship
          name
          (x 0.0 :type single-float)
          (y 0.0 :type single-float))
        (make-ship :name 'o-fools :x 1.0 :y 2.0)

results in the following in memory:

    ship:
        +------------------------------+
        | structure header, w/ length  |
        +------------------------------+
        | pointer to class info        |
        +------------------------------+
        | pointer to o-fools symbol    |
        +------------------------------+
        | pointer to raw vector below  |
        +------------------------------+

    ivec:  [really a (simple-array (unsigned-byte 32) (*))]
        +------------------------------+
        | header                       |
        +------------------------------+
        | length (2 in this case)      |
        +------------------------------+
        | bits for 1.0                 |
        +------------------------------+
        | bits for 2.0                 |
        +------------------------------+

If the structure is :INCLUDEd, then additional slots are added to the
end of either the main structure or the non-descriptor vector
according to type.

-William Lott
CMU Common Lisp Group



Sat, 11 Nov 1995 03:25:56 GMT  
 (simple-vector 20) vs (vector single-float 20)

|> > Most Common Lisps implement non-:TYPEd structures as vectors, with a flag
|> > so that they structures can be distinguished from other types of vectors.
|> > Are you asking whether they optimize the case where all the slots specify
|> > :TYPE SINGLE-FLOAT and generate a vector with unboxed single floats?  I
|> > haven't heard of implementations that do that.
|>
|> The current alpha version of CMUCL (not yet available, sorry) does
|> something sorta like that.  When DEFSTRUCT sees any slot types that
|> would benifit by being stored in memory unboxed, it allocates one slot
|> in the structure that holds a vector of raw data, and then allocates
|> all these non-descriptor slots in this sub-vector.
|>
|> Despite the extra indirection, the cost is better.  This is because
|> there is an extra indirection no matter what.  If heap allocated
|> objects were stored directly in slots in the main structure they would
|> each have to be indirected to get at the real bits anyway.  The main
|> advantage comes from not having to keep boxing results before putting
|> them in the vector, and the overall amount of same used is reduced
|> because there is only one header for all the non-descriptor stuff
|> instead of a header per object.

The "result boxing" saving can be defeated by "intermediate boxing" cost
if the compiled code is not always operating on the indirect array of
float bits directly.

I'm sure the reason for having the indirection of the float bits is so the
garbage collector doesn't need to be aware of the non-lisp objects
in the structure.  The float-bit array is just another lisp object to the GC.

A better approach that would waste an additional word per float,
but should give better speed, would be to embed the float objects into the structure directly.
So you would get:

        (defstruct ship
          name
          (x 0.0 :type single-float)
          (y 0.0 :type single-float))
        (make-ship :name 'o-fools :x 1.0 :y 2.0)

 results in the following in memory:

     ship:
        +------------------------------+
        | structure header, w/ length  |
        +------------------------------+
        | pointer to class info        |
        +------------------------------+
        | pointer to o-fools symbol    |
 1.0    +------------------------------+
 -----> | float header                      |
 obj    +------------------------------+
        | bits for 1.0                 |
        +------------------------------+
 -----> | float header                 |
        +------------------------------+
        | bits for 2.0                 |
        +------------------------------+

Thus, you can access the float bits directly in the structure, but at the
same time, you can get a real lisp-float object without actually consing
by constructing a pointer into the structure.

This would require the garbage collector to be aware of this type of
embedding.  The easy fix for scanning purposes would be to add a slot
to the class info that identifies where the "lisp" slots end, with the rest
of the slots being "bits".  Thus, you store all the lisp objects in
the top of the structure, and put all the raw bits at the end.
So for the above example, the ship-class-info would have a field with
the value 1, indicating that only the first 32bit slot in the structure
is a lisp object, the rest the GC can ignore.

The hard fix to having the GC know when it finds a float object that
actually points inside of a structure.  This fix would be highly dependant
on the underlying implementation.  There is a good chance that float objects
are allocating in different regions of memory than structures (this is so
GC doesn't have to scan through floats bit areas looking for pointers).
Then you have to figure out where the beginning of the structure is so
you can determine whether it has been copying to newspace already, and if
not, copy the structure before updating the float pointer.  

Again this depends on the implementation, but it is probably a good bet
that only a structure header has structure header bits followed by a class-info
object.

Who said hacking Lisp implementations isn't fun?

-Kelly Murray



Sun, 12 Nov 1995 01:25:50 GMT  
 (simple-vector 20) vs (vector single-float 20)

Quote:


>> Which is more efficient?
>>         (simple-array single-float (20))
>>         (vector single-float 20)
>>         (simple-vector 20)

It on what you're doing and on what Lisp you're using.

Quote:
>>         (simple-array single-float (20))

>This indicates that you have a simple array of single floats, with one
>dimension of 20.  [...]   The
>single-float means that you will only ever put single floats in it, so
>if the implementation supports a special kind of array for
>single-floats it can use it.
>>         (simple-vector 20)

>This is shorthand for (simple-array t (20)).  The difference between
>this and the first one is that it says that the array has to be able
>to hold anything, so the compiler cannot use a specialized array type.

>Anyway, in CMUCL the first is the most effecient, then the third, then
>the second.  Specifically, if you were to say:

>    (+ (the single-float (aref v 0)) 1.0)
> [...]
>So the ``simple'' saves you a lot, and the ``single-float'' saves you
>some consing and an extra indirection.

>I would assume most other lisps are the same way.

I have one disagreement with this excellent explanation.  In many
cases, it is better to use an array type that can store numbers
directly rather than as pointers to the heap (as suggested above);
but there are some cases where it is not better.  If what you're doing
is extracting values from the array and passing them to various
functions, then a heap value may have to be allocated each time you
access a given array element if the value comes from a specialized
array.  In a case like that an ordinary simple array that contained
pointers to heap-allocated values would be better, because the
pointers could be used and re-used directly.

Single-float might be a special case in some Lisps.  If single-floats
are not ever heap allocated, that is if they are immediate values,
then this problem with repeated heap allocations cannot arise.

-- jd



Mon, 13 Nov 1995 04:53:25 GMT  
 (simple-vector 20) vs (vector single-float 20)
   Single-float might be a special case in some Lisps.  If single-floats
   are not ever heap allocated, that is if they are immediate values,
   then this problem with repeated heap allocations cannot arise.

Page 22 of CLtL2 suggests to implementors that SHORT-FLOATs be
immediate values (not allocated on the heap), and that SINGLE-FLOAT
and DOUBLE-FLOAT employ or approximate the IEEE standards.  Harlequin
LispWorks (and also CLISP) appear to take this approach.

--
        Lawrence G. Mayka
        AT&T Bell Laboratories

Standard disclaimer.



Mon, 13 Nov 1995 22:18:46 GMT  
 (simple-vector 20) vs (vector single-float 20)

Quote:


> [talks about float slots in structures in CMUCL]

> The "result boxing" saving can be defeated by "intermediate boxing" cost
> if the compiled code is not always operating on the indirect array of
> float bits directly.

True.  But in a generational-GC system, it is faster to allocate new
float objects and then throw them away, it is is unclear with is
better in general.

Quote:
> I'm sure the reason for having the indirection of the float bits is so the
> garbage collector doesn't need to be aware of the non-lisp objects
> in the structure.  The float-bit array is just another lisp object to the GC.

Yup.  Additionally, we were able to implement this without making any
changes to the garbage collector because the float-bit array is just a
(simple-array (unsigned-byte 32) (*)), which gc support already
existed for.

Quote:
> A better approach that would waste an additional word per float,
> but should give better speed, would be to embed the float objects
> into the structure directly.
> So you would get:

>         (defstruct ship
>           name
>           (x 0.0 :type single-float)
>           (y 0.0 :type single-float))
>         (make-ship :name 'o-fools :x 1.0 :y 2.0)

>  results in the following in memory:

>      ship:
>         +------------------------------+
>         | structure header, w/ length  |
>         +------------------------------+
>         | pointer to class info        |
>         +------------------------------+
>         | pointer to o-fools symbol    |
>  1.0    +------------------------------+
>  -----> | float header                 |
>  obj    +------------------------------+
>         | bits for 1.0                 |
>         +------------------------------+
>  -----> | float header                 |
>         +------------------------------+
>         | bits for 2.0                 |
>         +------------------------------+

> Thus, you can access the float bits directly in the structure, but at the
> same time, you can get a real lisp-float object without actually consing
> by constructing a pointer into the structure.

But then if you said:

        (let ((orig-x (ship-x ship)))
          (setf (ship-x ship) (+ ship-x-speed orig-x))
          orig-x)

Then the returned value would be incorrect because orig-x would still
point at the structure slot which just got modified.  I guess you
could do it for read-only slots, but the benifits would be
sufficiently minimal to not be worth the effort.

Quote:
> This would require the garbage collector to be aware of this type of
> embedding.  The easy fix for scanning purposes would be to add a slot
> to the class info that identifies where the "lisp" slots end, with the rest
> of the slots being "bits".  Thus, you store all the lisp objects in
> the top of the structure, and put all the raw bits at the end.
> So for the above example, the ship-class-info would have a field with
> the value 1, indicating that only the first 32bit slot in the structure
> is a lisp object, the rest the GC can ignore.

Moving all the non-descriptor slot to the end breaks down in light of
:include.  If the including structure defines additional descriptor
slots, then you couldn't line up the shared slots and keep all the
non-descriptor slots at the end.

But you don't really need this information.  The garbage collector has
to scan each slot anyway, so it just checks for embedded-float
headers, and if it finds one, it skips the next slot.

Quote:
> The hard fix to having the GC know when it finds a float object that
> actually points inside of a structure.  This fix would be highly dependant
> on the underlying implementation.  There is a good chance that float objects
> are allocating in different regions of memory than structures (this is so
> GC doesn't have to scan through floats bit areas looking for pointers).
> Then you have to figure out where the beginning of the structure is so
> you can determine whether it has been copying to newspace already, and if
> not, copy the structure before updating the float pointer.  

> Again this depends on the implementation, but it is probably a good bet
> that only a structure header has structure header bits followed by a
> class-info object.

One thing you could do would be is to have the float-header imbedded
in the struct contain the offset from the start of the structure.
Then when the garbage collector comes across a pointer to an embedded
float, it could just subtract off the delta to get a pointer to the
containing structure object.

We effectivly do this to embed functions inside ``code-components.''
A code component contains all the constants and one or more function
objects.  You can have multiple functions in the same code component
when you ``block compile'' several functions together.  Whenever the
garbage collector goes to transport a function pointer, it first
computes a pointer to the code-component, transports that, and then
computes what the new function pointer should be by adding the
original displacment to the new code-component.

Quote:
> Who said hacking Lisp implementations isn't fun?

Not me.

-William Lott
CMU Common Lisp Group



Tue, 14 Nov 1995 07:35:59 GMT  
 (simple-vector 20) vs (vector single-float 20)


|> > [talks about float slots in structures in CMUCL]


|> > A better approach that would waste an additional word per float,
|> > but should give better speed, would be to embed the float objects
|> > into the structure directly.
|> > So you would get:
|> >
|> >         (defstruct ship
|> >           name
|> >           (x 0.0 :type single-float)
|> >           (y 0.0 :type single-float))
|> >         (make-ship :name 'o-fools :x 1.0 :y 2.0)
|> >
|> >  results in the following in memory:
|> >  
|> >      ship:
|> >         +------------------------------+
|> >         | structure header, w/ length  |
|> >         +------------------------------+
|> >         | pointer to class info        |
|> >         +------------------------------+
|> >         | pointer to o-fools symbol    |
|> >  1.0    +------------------------------+
|> >  -----> | float header                 |
|> >  obj    +------------------------------+
|> >         | bits for 1.0                 |
|> >         +------------------------------+
|> >  -----> | float header                 |
|> >         +------------------------------+
|> >         | bits for 2.0                 |
|> >         +------------------------------+
|> >
|> > Thus, you can access the float bits directly in the structure, but at the
|> > same time, you can get a real lisp-float object without actually consing
|> > by constructing a pointer into the structure.
|>
|> But then if you said:
|>
|>   (let ((orig-x (ship-x ship)))
|>     (setf (ship-x ship) (+ ship-x-speed orig-x))
|>     orig-x)
|>
|> Then the returned value would be incorrect because orig-x would still
|> point at the structure slot which just got modified.  I guess you
|> could do it for read-only slots, but the benifits would be
|> sufficiently minimal to not be worth the effort.
|>

I realized this was a problem after I posted.  I was wondering if someone
would catch it.  It is a fatal flaw in the design.  
And as you pointed out, with generational-gc, the intermediate value consing
may not be that expensive.

|> > This would require the garbage collector to be aware of this type of
|> > embedding.  The easy fix for scanning purposes would be to add a slot
|> > to the class info that identifies where the "lisp" slots end, with the rest
|> > of the slots being "bits".  Thus, you store all the lisp objects in
|> > the top of the structure, and put all the raw bits at the end.
|> > So for the above example, the ship-class-info would have a field with
|> > the value 1, indicating that only the first 32bit slot in the structure
|> > is a lisp object, the rest the GC can ignore.
|>
|> Moving all the non-descriptor slot to the end breaks down in light of
|> :include.  If the including structure defines additional descriptor
|> slots, then you couldn't line up the shared slots and keep all the
|> non-descriptor slots at the end.

Yes, this is also a problem.

|>
|> But you don't really need this information.  The garbage collector has
|> to scan each slot anyway, so it just checks for embedded-float
|> headers, and if it finds one, it skips the next slot.

This is only true if the float-header bits can be distinguished from normal
lisp objects, which is not true for my lisp.  If this is true for CMULisp,
then there is no need store floats at the end of the instance, or for that
matter, in a seperate indirect array, to avoid GC confusion.
The embedded design does add another word to each float storage, though.

Let me suggest another alternative.  Have a bit mask for each slot in the
structure, identifying whether the slot is a lisp-object, or raw bits.
You didn't mention it, but let me point out that both seperate array design and
this one would also allow more than just floats to be stored directly,
such as 8bit-sized slots, etc.
The seperate array design could pack things in better, since this bitmask
design would require a more rigid 32bit alignment.

         (defstruct (plane (:include ship))
           (pilot :type symbol)
           (z 0.0 :type single-float)
           (a 0   :type (unsigned-byte 16))
           (b 0   :type (unsigned-byte 16))
          )
 plane:
        +------------------------------+
        | structure header, w/ length  |
        +------------------------------+
        | pointer to class info        | -->  class has a slot-bitmap 011011
        +------------------------------+
        | pointer to o-fools symbol    | lisp object
        +------------------------------+
        | bits for 1.0                 | nonlisp object (no more header)
        +------------------------------+
        | bits for 2.0                 | nonlisp
        +------------------------------+
        | pilot slot                   | lisp object
        +------------------------------+
        | z slot 0.0                   | nonlisp
        +------------------------------+
        | a slot       |   b slot      | nonlisp
        +------------------------------+

GC now has to consult the class bitmap to do a scan of the object.
This might be a problem for GC overhead,
and it might be better to allocate a header slot in the instance with a
one-word bitmap for instances with less than 32 slots, or actually use
some upper bits on the length field of the structure header.

Did I forget anything William? :)

-Kelly



Wed, 15 Nov 1995 01:47:06 GMT  
 (simple-vector 20) vs (vector single-float 20)

Quote:


> |> But you don't really need this information.  The garbage collector has
> |> to scan each slot anyway, so it just checks for embedded-float
> |> headers, and if it finds one, it skips the next slot.

> This is only true if the float-header bits can be distinguished from normal
> lisp objects, which is not true for my lisp.  If this is true for CMULisp,
> then there is no need store floats at the end of the instance, or for that
> matter, in a seperate indirect array, to avoid GC confusion.
> The embedded design does add another word to each float storage, though.

All the header ``types'' we use are disjoint from regular types, so
all we need to know about any particular word is whether it is a lisp
object (i.e. has a type tag) or a raw 32-bit value.

But the extra header word per non-descriptor slot would be rather
expensive, espically when there are alternate solutions, as you point
out:

Quote:
> Let me suggest another alternative.  Have a bit mask for each slot in the
> structure, identifying whether the slot is a lisp-object, or raw bits.
> You didn't mention it, but let me point out that both seperate array
> design and this one would also allow more than just floats to be
> stored directly, such as 8bit-sized slots, etc.

We currently use allocate single-float, double-float, and
(unsigned-byte 32) types in the indirect array.  It would be trivial
to add support for other non-descriptor objects.

For types that fit inside a fixnum (e.g. 8-bit bytes) we just leave
them in as regular slots because they don't have to be boxed.

Quote:
> The seperate array design could pack things in better, since this bitmask
> design would require a more rigid 32bit alignment.

Actually, the bitmap idea can work along with packing.  Just interpret
each bit to indicate whether or not a word (not slot) is a descriptor
object or raw bits.  Then if you have two adjacent (unsigned-byte 16)
slots, you could allocate them in the same word and just mark that
whole word as raw.

Quote:
> GC now has to consult the class bitmap to do a scan of the object.
> This might be a problem for GC overhead,

Yes, the extra processing overhead at collection time is the main cost
of this method.

Quote:
> and it might be better to allocate a header slot in the instance with a
> one-word bitmap for instances with less than 32 slots, or actually use
> some upper bits on the length field of the structure header.

Actually, it probably would be better just to stay consistent.  Each
structure needs the pointer to the class info, so tucking the bitmap
in there would only impose a small size overhead to each class
description.  Having a special short-structure representation could
easily cause problems for :include if the included structure was
short and the including structure ended up too big.

Another related idea that is commonly used in static langauges, is to
generate a class specific scavenger function for each structure type
that has information about which slots need to be scavenged hard wired
into it.  Then the garbage collector just needs to extract the pointer
to this routine from the class-info and call it.  If there are lots of
non-descriptor slots, then this can be a big win because there is *no*
cost for them, unlike with the bitmap where you have to scan the
bitmap checking each bit.

-William Lott
CMU Common Lisp Group



Wed, 15 Nov 1995 17:19:56 GMT  
 
 [ 12 post ] 

 Relevant Pages 

1. SoftSentry by 20/20 software

2. 3DYear 2000 Solutions - [20/20]

3. 3DYear 2000 Solutions - [20/20]

4. Public Tcl/Tk training, July 16-20 and August 20-24

5. Machine Forth vs ANS : 20 bits vs 32 bits

6. no vector = vector*vector in BLAS?

7. Withdrawn SRFI 20: Simple object system

8. Draft SRFI 20: Simple object system

9. Joke: 20/20 hindsite: Something I wish I had when I left my last job...

10. Vector set!, void vector problem

11. matrix as vector of vectors

12. Inserting a vector slice into another vector

 

 
Powered by phpBB® Forum Software