On object layout

[Matthew Tuck]

Hans-Dieter Dreier wrote:

>> Well there are a lot of difficulties with multiple objects, but it is
>> very important.  Heap allocation is very inefficient compared to
>> other forms of memory allocation.

> Are you sure? I think that's a case for optimisation. Maybe a
> stacklike regime is faster, but it is of limited usefulness, or at
> least more complicated: You'd have to take special measures to prevent
> a stack object from being deleted if there is a reference to it still
> surviving.

Erm, maybe you misunderstood, I was referring to multiple objects
through optimisation.  So you don't have to worry about them at the
language level.

> You would just save one (1) pointer and have to service two possible
> implementations everywhere where a reference is used (which is about
> every single line of code). Is that really worth the trouble?

The main benefit is in reducing the potentially expensive heap
allocation, and reducing GC walk time.

If there was a need for two implementations I probably wouldn't advocate
it.  I don't see one, basically it's just stored inline.  You would
ensure there were no GCable pointers to the partial objects.

> I view it as a means of simplification not optimisation. Generally
> speaking, memory management and objects (in the OOP sense) need not be
> implemented by the same device. I'll admit that. But it's just that
> IMHO I see so many benefits if you use the object header for memory
> management as well, that this seems to me to be the natural approach.

Off the top of my head I can't think of a reason why the VM would care
about this.  In many langauges integers are not proper objects, this
allows them to be stored inline.  However if you want real consistency,
they become objects.  The VM doesn't really care.  There's an integer
inline, there's an integer on the end of a pointer.

There can be a problem with generics, obvious if a class did it one way
all it's subclasses would need to.
 
> I think a memory block should host many objects tightly packed with no
> gaps, the object being the unit of our own suballocation scheme as
> well. Pointers only point to the beginning of an object; there are no
> objects within objects.

Yes, I don't think there's a terminology misunderstanding.  What I
advocate should not make the VMs job any more difficult, except maybe
for a pointer which doesn't get deallocated, since the partial object's
object gets deallocated.

The point about aggregating objects at the same time is that the memory
is allocated at the same time, hence there's a reduction in the number
of requests, even if it doesn't go to the OS.

But anyway, I need to look at this topic more before talking much more,
I might do a bit of Web scouring.

> Because we handle suballocation ourselves rather than bother the OS
> every time, it will be pretty fast. GC will be simple. The price to be
> paid is memory for headers, or course. But I think most of the info
> they contain serves a dual purpose: memory management and use by the
> class. So some of the header overhead will eventually be implemented
> nyway.

Have you written a memory allocation scheme before?  I haven't but I
gather though they might be simple, they're not necessarily fast. 
Nothing like the speed of a stack.  And GC is not quite so simple if
you're creating an incremental collector.  That is, one which collects a
little bit at a time at small periods rather than all at once when
memory is exhausted.  Long pauses are unacceptable for interactive
applications (Emacs is famous for this).

> All we have to do is try to pack as much into a single object as
> possible to keep the ratio of headers to contents at bay. For example,
> a whole stack frame or a whole compiled function body.

Putting stack frames as objects is certainly an interesting idea, I'm
not sure what you're really advocating though, I would have hid that
inside the implementation of the interpreter, so it's at least on a
lower level than UPPID (better name anyone?).
 
> Beg your pardon, but I think you need to explain "assignment > semantics".

Sorry.

a, b: Integer

b := new(3)
a := b
b := new(4)

what is the value of a?  In value semantics it is 3, it corresponds to a
shallow copy of the object.  In pointer semantics it is 4, it
corresponds to a pointer copy.  Pointer semantics have become the
default in object-oriented languages, while value semantics were
previously the usual.

>> I'm not entirely sure, but I think you're referring to multiple
>> objects in one memory object when you talk about nested layout.

> I meant multiple objects within an object. I never thought of treating
> memory blocks (as obtained from the OS) as objects in their own right.

When I said memory object I meant what was obtained from one allocation
(e.g. new), rather than a larger block from the OS.

> We could in fact use a linked list. But GC certainly would have to
> know about nested objects. Assume the outermost object would be GCed
> while some contained object still is alive. Without checking for
> nested objects, the whole memory block would turn to garbage. Figuring 
> out the actual memory layout would be easier for GC if it were a tree: 
> Tree layout could reflect nesting. But I really don't think nested
> objects are an idea worthwile to consider.

You wouldn't inline the object if you couldn't determine that this won't
happen.  You don't do the optimisation without the analysis.  Perhaps
it's more worthwhile for you to think of nested objects as a
transformation that occurs between the language and the VM, ideally,
neither would care, only the optimiser.

On the contrary to not being worthwhile, I think we can never get to C
level efficiency if we don't do it.
 
> How about strings? String manipulations can be more efficient if
> handled in-place.Maybe stacks as well (though I'll admit that their
> maximum length is often known beforehand).

OK, well strings are arrays, and maybe they would be common.  But
anyway, as I indicated, you wouldn't generally inline a dynamic array,
even in C (hmm, maybe if it's the last member of the object ...).  Think
of it as getting the implementation back to the way C would do it.
 
> Again, you would have to make sure such objects couldn't be GCed
> accidentally.If GC were able to move objects (say, to
> compactify before saving a whole image on disk for a fast reload),
> those references would have to be fixed up anyway.

That's true.  I'll get back to you on that issue.
 
-- 
     Matthew Tuck - Software Developer & All-Round Nice Guy
                              ***
       Check out the Ultra programming language project!
              http://www.box.net.au/~matty/ultra/