On object layout

Hans-Dieter Dreier Ursula.Dreier@ruhr-uni-bochum.de
Tue, 08 Dec 1998 04:07:21 +0100




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

If you meant it to be an optimisation to be added later on: That's OK with me.
Won't be easy, though.

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

Should be OK then, I think

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

Sure it's more a matter of memory management, but the two are working
together.If you just access them by method calls, it could be done right from
the start. Because you couldn't have references to them at the language level,
those methods would have to be built-in ones. Actually, I think there should be
a built-in VM call which has two parameters: An object reference and an offset,
and which would get/set the reference (or integer, or other inline object
specific to that VM call) found at this offset. But that would be for internal
use of the compiler only! Otherwise it would seriously compromise safety.

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

True; it's the compiler who cares.

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

If it can be achieved as a means of optimisation that's OK, but I would suggest
not to implement support for this in the beginning.

> Have you written a memory allocation scheme before?

Yes I have. It wasn't difficult. But the trick will be to optimise it, which
will involve a lot of trial and error, statistics, profiling and the like. So I
better be pretty good insulated to that different versions can be checked out
easily.

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

There's a pretty simple scheme involving blank, grey and white tags mentioned in
your GC reference, which is derived from the standard mark/sweep algorithm; it
can be further enhanced if it keeps a list of the "grey" objects so they can be
found faster than by searching the memory sequentially. I imagine that should be
pretty easy and pretty fast.

Additionally, we could use that 1-bit use count also mentioned in the GC
reference. This might perhaps speed up reclaiming stack objects.

> 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?).

It can be a base class of an user-accessible stack class.

> > 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 talking of value semantics, then. I don't like pointer semantics as far as
simple objects (numbers, strings) are involved, because it's exactly what a
normal programmer wouldn't expect.

But it would still be a pointer copy: The address of that 3 is bound to b, and
to a as well. b is then bound to 4, while a remains the same (pointing to 3). If
you got the following case, however:

a, b: Integer

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

the value of a would be 3, as well, because the following would happen:
The address of that 3 is bound to b, and to a as well. That second bind involves
copying the pointer. Two references to that 3 exist now. This will be recorded
in the object containing that 3 (the 1-bit reference count is set during the
copy), to denote that this object has to be copied if changed. When it comes to
incrementing, it is copied first; that copy is incremented and bound to b, while
a remains the same.

This is just a proposal, but I think it combines the benefits of both appraoches
while imposing a comparatively low overhead.


> On the contrary to not being worthwhile, I think we can never get to C
> level efficiency if we don't do it.

Sure, we should try. But don't expect too much: If your program uses a GUI, that
will use up half of the time anyhow, and that limits what you can get. Even if
your program runs in zero time, the overall improvement will be just 50%: Barely
noticeable. And he who puts in more memory and a slightly faster CPU into his
machine will have the same improvement.

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

I'd rather say strings are simple objects (at least at the language level). But
never mind...

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

I got something special in mind concerning the last item in an object: It is the
natural place to put an arbitrary number of items of equal length(usually, but
not limited to, references) into an object. The drawback is, of course, that can
only have one of those in your class, and you cannot easily derive subclasses
with instance variables from that class.