Categories: Programming

Introduction

Something I’ve been wondering about for ages: how exactly are objects in an oo-language represented in memory, and particularly what happens when casting is applied?

The following notes is a summary of my reading about this topic. Primarily, this information relates to code compiled from C++, although it is also useful for Java developers to know (and some notes on Java are present towards the end of this article).

Object Representations in Dynamic-Typed Languages

First, some comments about languages like Javascript/Python/Ruby/Perl6.

As these languages allow the definition of an object (its attributes and methods) to be modified at runtime, they need a representation which is much different than in compiled languages. In general, in such languages methods and attributes need to be looked up in a hashmap or similar when referenced. The language runtime may be able to perform “heuristic” optimisations such as tracing, but such optimisations are very interpreter-specific and far too complex/undocumented/often-modified to describe in this article.

In languages in which OO behaviour is determined at compile-time (eg c++), how objects are represented and methods are dispatched efficiently is easier to understand.

Simple Single Inheritance

Given a linear inheritance tree [BaseClass <- SubClass <- SubSubclass] the memory-layout for an instance of BaseClass can look like:

BaseClass-vptr (a pointer to a vtable structure; see later)
BaseClass-fields

and the memory-layout for an instance of SubSubClass looks like:

unified-vptr (a pointer to a vtable structure; see later)
BaseClass-fields
SubClass-fields
SubSubClass-fields

This allows casting to be implemented trivially. Given:

BaseClass myBaseObj = new BaseClass();

SubSubclass mySubSubObj = new SubSubClass();
BaseClass mySubSubObjAsBase = mySubSubObj; // upcast

then due to the chosen memory layout, mySubSubObjAsBase simply holds the same address as pointer mySubSubObj. All fields on the BaseClass can be accessed without problems via mySubSubObjAsBase; they are at exactly the same offsets as the same fields in myBaseObj. The fact that for mySubSubObjAsBase additional data follows the “known” fields is irrelevant.

The vptr actually points to a datastructure which contains:

• a “type descriptor” which identifies the real type of the object (ie the type specified in the “new” operation)
• an “offset to top of object” (relevant only in multiple-inheritance)
• an array of pointers to virtual methods for the type

This datastructure allows the correct determination of the concrete type of an object even after it has been cast to its base-type.

The order of method-pointers in the unified vtable for SubSubClass must be: baseclass-methods followed by SubClass-methods followed by SubSubClass-methods. This allows any vtable indexes valid for the base class to also be valid for the vtable of the subclasses, ie vtable.methods[0] points to the “same method”. When a subclass overrides a method in an ancestor, then the pointer at that index in the vtable simply points to the new implementation. The “this” pointer points to the start of the object (the primary vptr), so fields defined in the subclass can be found by such a method in the expected places.

This approach works to any depth of single-inheritance, and is relevant also for a hierarchy of “interfaces” (classes with no fields).

Multiple Inheritance

When a class has multiple parents then multiple vptrs are required: one for each ancestor and potentially one for the subclass too (if it has virtual methods). In effect, the subclass memory layout is simply a concatenation of each parent (including its vptr).

class Base1 {
  public:
   int field1;
   virtual void base1Do() {..}
   virtual void base1Do2() {..}
}

class Base2 {
  public:
   int field2;
   virtual void base2Do() {..}
   virtual void base2Do2() {..}
}

class Child : public Base1, public Base2 {
  public:
   int fields;
   virtual void base1Do() {..} // override
   virtual void base2Do() {..} // override
   virtual void childDo() {..} // implement own method
}

produces in a naive implementation:

unifiedvptr          // vptr for object as type Child (ie contains an entry for every method available in Child) 
  base1vptr_updated  // vptr for object as type Base1 - pointing to overridden impls in Child where they exist
  base1fields        // fields inherited from base1
  base2vptr_updated  // vptr for object as type Base2 (contains entries only for methods available in Base2)
  base2fields        // fields inherited from Base2
childfields          // fields defined in type Child

however the [Base1 <- Child] inheritance chain can be considered a case of “simple single inheritance” as described earlier, and thus the Base1vptr_updated can be omitted; its contents are identical to the first N entries of the unifiedvptr table. The Base2vptr_updated table cannot be omitted as its function#0 is not the same as function#0 in the unified table, ie the offsets need tweaking. This results in an “optimised” representation of:

unifiedvptr
Base1fields
Base2vptr_updated
Base2fields
Childfields

Casting an object between type Child and Base1 is trivial, as in “simple single inheritance” described above: the pointer remains identical. Casting between type Child and Base2 is more complex: the result is a pointer to the address of Base2vptr_updated.

Note that in this multiple-inheritance situation, one of the base types is considered the “primary” type and the “simple single inheritance” approach can be used for it (simplifying and optimising casting), while the others require a more complex implementation (embedding an extra vptr). While the c++ standard does not (AFAIK) describe how to decide which of the types in a multiple-inheritance situation is considered the “primary” type, the standard approach is to simply choose the first in the list of ancestor types.

In either case, after casting the referenced vptr points to a datastructure whose “type descriptor” points to a structure describing type Child, ie it is possible to know the “real original” type of the object. And in either case, this is followed by a table of function-pointers for the virtual methods on the type.

In the unified vptr method table:

• For methods defined in Base1 and overridden in Child, the corresponding entry simply points to the implementation from Child.
• For methods defined in Base1 and not overridden in Child, the corresponding entry simply points to the implementation from Base1.
• For methods defined in Base2 and overridden in Child, the corresponding entry simply points to the implementation from Child.
• However for methods defined in Base2 and not overridden in Child, the entry needs to point to a thunk.

The “thunk” is some code that adds a constant to the “this” pointer before invoking the implementation from Base2. This is necessary because the compiled code from Base2 expects that field “field2” can be found at a fixed offset from the “this” pointer, but the offset in a Child instance is larger (due to the presence of other inherited fields before it). In effect, an implicit cast to type Base2 needs to be inserted before invoking the original implementation from type Base2. The offset for “Base2 within Child” can be found in the datastructure pointed to by Base2vptr (the “offset to top of object” mentioned earlier), making it possible to downcast again from Base2 to Child.

The method table pointed to by Base2vptr has similar behaviour. It is used only after a cast has earlier been applied, ie the “this” pointer is pointing at Base2vptr, so:

• For methods defined in Base2 and not overridden in Child, the corresponding entry simply points to the implementation from Base2; the “this” pointer is already appropriate for that code.
• For methods defined in Base2 and overridden in Child, the corresponding entry points to a thunk which adjusts the “this” pointer back to point to the unifiedvptr (ie the real base of the Child instance) before invoking the implementation from Child. The relevant offset to appy to the “this” pointer can be found in the “offset to top of object” field. In effect, an implicit upcast to type Child needs to be inserted before calling the implementation from type Child.

Code that invokes virtual methods on Child compiles to instructions that load the appropriate method via the unifiedvptr. The Base2vptr is only used after casting has been applied.

This approach to representing objects means that each additional base class increases the size of an object by a pointer - a class with 20 direct base classes and a single int field will have 19*sizeof(void*) bytes of overhead in each instance just to support the ability to cast it to its various base types. However a deep hierarchy (many indirect ancestors, ie an ancestor who has an ancestor who has an ancestor etc) is not a problem and requires only one pointer per direct ancestor; it is wide hierarchies (many direct ancestors) which has more impact on memory usage.

Some OO languages use a different approach called “dictionary passing”, in which a reference to an abstract type is actually a (typedescriptor, objectdata) pair of pointers. In the C++ “vtable” approach, a reference to an abstract type is instead a single pointer to an address holding a pointer to a typedescriptor (aka vtable) followed by the objectdata. The negative side of the vtable approach is that objects must have multiple vtables embedded in them, ie are larger than they need to be even when never cast to their base types. The dictionary-passing approach only pays the cost of the extra storage (vptr,value) for variables holding a reference to abstract type (including function parameters). On the other hand, in dictionary-passing languages, a “reference” will then be sizeof(void*)x1 for concrete types and sizeof(void*)x2 for abstract types which doesn’t work well when detailed control over memory layout is desired.

An interesting issue arises in garbage-collected languages using the vtable approach: if an object is created and then cast to an ancestor type (ie a pointer into the middle of the object), and then the original reference is thrown away, the garbage-collector must not garbage-collect the instance. This means that the garbage-collector must recognise during its mark-and-sweep pass when a reference points into the middle of an object, and not throw that object away. Because that object is live, the garbage-collector must also follow references in members of the whole original object, even though it sees only a reference to a base type.

Inheritance of Interfaces

C++ does not directly have anything corresponding to a Java interface type (a pure definition of methods with no data-fields). However a standard abstract class definition in which no fields are defined is effectively the same thing.

However the difference between “interfaces” (abstract classes with no fields) and other types makes little difference to the memory layout: they still require the “multiple inheritance” structure where all base classes except the “primary” one cause an extra vptr to be embedded in the object data.

Destructors

As mentioned here, it is important in C++ for all base type definitions to have virtual destructors. Without this, casting a reference to its base type then calling delete on it will not call the destructor in the concrete type.

The “freeing memory” step that is triggered by delete after invocation of any custom destructors always looks in the current vtable (which may not be the primary vtable for the object), and retrieves the “offset to start of object” from it. This is then subtracted from the current this-pointer to find the correct address to pass to free().

The “primary” (unified) vtable for the object will always have an “offset to start of object” value of zero.

In the simple single inheritance case, there is at most one vtable and casting doesn’t ever actually change the value of the “this” pointer. Deleting the object can therefore call free directly on the “this” pointer.

Pointer Comparisons

Interesting issue: A pointer to a Child instance and a pointer to the same object after casting to a base type should compare “equal” - ie the tweaking that a cast to “non-primary base type” does should be invisible. This can be achieved by the compiler by ensuring both sides of a pointer-comparison are the same type:

#include <iostream>
using namespace std;

// insert class defs from earlier

extern int main() {
  Child* c = new Child();
  Base2 *i = (Base2*) c;

  // Demonstrate that variable i really does have a different value
  void* vc = (void*) c;
  void* vi = (void*) i;
  if (vc != vi) {
    cout << "expected: void pointers are different\n";
  } else {
    cout << "unexpected: void pointers are equal\n";
  }

  // This comparison should be true for obvious reasons
  if (((Base2*) c) == i) {
    cout << "expected: explicit cast compared equal\n";
  } else {
    cout << "unexpected: explicit cast comparison failed\n";
  }

  // Compiler must treat this comparison as if an implicit cast was present (the case above) rather
  // than comparing the raw values as if they were void-pointers.
  if (c == i) {
    cout << "expected: uncast pointers compared equal\n";
  } else {
    cout << "unexpected: uncast pointer comparison failed\n";
  }

  return 0;
}

vptr-after-fields

Some older variants of c++ compilers put the vptr after the fields. This had the advantage that an object’s layout is identical to a C struct with the same members. An object pointer can therefore be passed directly to a “c” function.

With this approach, laying out fields “base class first” would result in the offset from the start of an object to the vtable varies depending on concrete type. A real instance of the base type would look like:

base-class-fields
vptr

where the vptr is N bytes from the start of the object, while an instance of the subclass cast to the base type would look like:

base-class-fields
subclass-fields
vptr

where the vptr is N+M bytes from the start of the object. A function taking a base type as parameter and then invoking a virtual method would therefore be unable to find the vtable.

I can only guess that the field layouts are reversed when such a strategy is used:

subclass-fields
base-class-fields
vptr

and that invoking a method defined in the base class passes a “this” pointer that points at the base-class-fields address.

One disadvantage of the “vptr after fields” layout is that loading any function address from the vtable requires an extra add-operation (base + vptr-offset) to find the location of the vtable. With the “vptr first” approach described earlier, the offset between pointer-to-object and the vptr location is zero so the add is not needed.

In any case, this approach appears to have fallen out of favour; current versions of g++ always place the vptr at the start of an object.

Diamond Inheritance (Virtual Inheritance)

In C++, it is possible for multiple base classes to have fields. It is also possible for the same base class to be inherited indirectly multiple times. This causes problems that are solved via the “virtual inheritance” mechanism. Java doesn’t have these problems as multiple-inheritance is restricted to interfaces only.

The solution to this C++ issue is more complexity with multiple vtables. I’m not really motivated to understand that, as it doesn’t apply to other programming languages, and won’t discuss it here.

Interface Dispatch in Java

Java bytecode has several instructions for invoking methods: invokestatic, invokevirtual, invokeinterface, invokespecial, invokedynamic.

• invokestatic is simply a direct call to a non-virtual method on a target object.
• invokevirtual is the “simple single inheritance” approach, where the method to invoke is on an ancestor class of the target object.
• invokeinterface is for when the method to invoke is on an ancestor interface (the multiple-inheritance case).

While a JVM can choose which concrete ways to perform such dispatching, it is expected that invokevirtual uses the same vtable approach that C++ does for “single simple inheritance”. The implementation of invokeinterface is far less clear - there are several possible ways of doing this; see the following publications for example:

• Interface Dispatch in Java
• InvokeInterface Considered Harmless

From the above information, it is quite likely that in JVMs, hash-table-driven approaches are used for dispatching invokeinterface calls rather than multiple vptrs. In other words the same “simple single inheritance” used by c++ is also used by Java for extending from non-interfaces, while inheritance from interfaces is instead handled via a hashmap-lookup at runtime (like dynamic-typed languages do) instead of the traditional c++ multiple-vptrs-with-thunks approach.

References

• Informit: c++ reference guide
• Wikipedia: virtual method table - describes multiple inheritance case
• Triana: polymorphism back to school
• PHC: Virtual Inheritance
• Stackoverflow/Rodriguez: Memory Layout of Derived and Base Object
• MentorEmbedded: CXX ABI for Itanium: Virtual Table Layout
• LearnCPP: The Virtual Table
• comp.compilers newsgroup: Memory Layouts of C++ classes
• Anton Ertl: reading list for OO dispatch

The folling book is a good reference for c++ compiler design:

• Design and Evolution of C++ - Stroustrup

The following have been recommended by the above sites, though I don’t have access to any of these:

• Inside the C++ object model - Lippmann
• Compiler Design - Wilhelm and Maurer