Why is there no heap overhead for the base reference?

Question

From Stroustrup's Foundations of C++, he offers a pure object-oriented language (on Page 4).

class complex { double re, im; /* … */ };
complex a[ ] = { {1,2}, {3,4} };

He assumes a in the pure object-oriented language is allocated on the heap, and a's memory layout looks like:

The likely size is 3*sizeof(reference)+3*sizeof(heap_overhead)+4*sizeof(double). Assuming a reference to be one word and the heap overhead to be two words, we get a likely size of 19 words to compare to C++’s 8 words. This memory overhead comes with a run-time overhead from allocation and indirect access to elements. That indirect access to memory typically causes problems with cache utilization and limits ROMability.

I noticed that the uppermost reference has no heap overhead (white rectangle).

I guess it is a general phenomenon rather than specified for the pure OO example language.

But I cannot find any reference (I do admit this is not a search-engine-friendly question).

Update

Thanks for your answers. However, I forgot to post my original guess. (Apologies, it is my fault.)

Actually, I also thought because a itself may be allocated on the stack or somewhere else, it will not have heap overhead itself. But later, I noted BS also says:

Compare this with a more typical layout from a “pure object-oriented language” where each user-defined object is allocated separately on the heap and accessed through a reference...

on Page 4.

So, I think that he has limited the implementation to heap-only (or stack-less).

(Of course, maybe I'm reading too much into this sentence.)

Answer 1

The top-level reference lives wherever it lives. Here are a few options:

1. It can live on the stack. a in the code could be represented like that.
2. It is embedded into an existing object.
3. Memory is allocated to just hold the handle. In this case it would have a memory overhead.
4. It lives as a global entity.
5. A reference can live in a register. a in the code could also be represented like that in which case it kind of has neither a heap overhead nor a memory overhead: instead it "only" requires the use of a register.

The main realisation in this context is that these references are not actual objects, i.e., you can't have a reference to a reference. As a result there is no need to keep the position of the reference fixed. They can be (and they are when they are actually represented) actual values. The value of a reference in a typical implementation is the address of the object.

The other entities are objects:

• Class complex is used to create an object which actually embeds to odd double "objects" which are also values rather than actual objects.
• a is an array object in this model referencing two complex objects.

Answer 2

You get heap overhead when you store something on the heap. The two complex values are stored on the heap, so they get overhead. The array of references is also stored on the heap, so it gets overhead.

However, the reference to the array is not stored on the heap. Usually, this reference will be either placed on the stack as a local variable, or that stack storage might be optimized away by using a CPU register instead. In either case, the reference itself is just a local pointer variable which does not have heap allocation overhead itself.

Answer 3

The idea here is that the top level reference is either a local/parameter on the stack/in a register (where there's no heap overhead) or as a part of some bigger structure (that in turn may be allocated on the heap, but we don't count its overhead here, as it's not specific to this particular reference, but it's shared between the other data members).

Actually, I also thought because a itself may be allocated on stack or any else, so itself will not have heap overhead. But later, I noted BS also says:

Compare this with a more typical layout from a “pure object-oriented language” where each user-defined object is allocated separately on the heap and accessed through a reference...

in Page 4.

So, I think that he has limited the implementation to heap-only(or stack-less).

(Of course, maybe I read too much into this sentence)

I think that you are reading too much into it. The real-world languages Stroustroup is referring to (such as Python, Java or C# - if we limit ourselves to boxed types) do have a "regular" stack containing a plain array of references.

Answer 4

complex a[ ] = { {1,2}, {3,4} };

Let's break this - bottom-up approach.

1. You have two complex objects that are list initialized: Complex{1,2} and Complex{3,4}.

Complex{ double, double }

Each complex object has the address of the heap (white) and the space occupied (blue) by the double values.

2. Next is the outer { brace which is to list-initialize an array of Complex objects.

array { Complex1, Complex2 }

This has the address of the array object (white), and the two references (blue) to the two Complex objects.

3. Lastly, there's no overhead for complex a for this is just a local variable that lives in the stack.