Statistically incorrect

I have finally started dabbling with Go to the point where I’m fairly close to taking my first project live in a heavy duty production environment. The first post on the language happens to be on the language internals i.e. something that is not visible to the programmers for the most part.

The C programming language was when I was first introduced to pointers and the concept there was fairly simply; the only the a pointer was expected to do was to point to a memory address. Given that simple expectation, it made no difference between primitive types and higher order types such as structs & unions. Things started becoming a little complex once object oriented languages started appearing on the scene.

Dynamic dispatch

Polymorphic method invocation is a common on well understood feature found in most object oriented languages. Here is an example (in C++ syntax) of polymorphic usage. The code has been stripped off all elements that is unnecessary to illustrate dynamic dispatching.

class Shape { public: virtual void draw(); }
 
class Rectangle: public Shape {
  int length, breadth;
public:
  void draw(){}
}
class Circle: public Shape {
  int radius, x, y;
public:
  void draw()  {}
  virtual void dance() {}
  void run() {}
}
 
void f() {
  Shape *s[2];
  s[0] = new Rectangle;
  s[1] = new Circle;
  for(int i = 0; i < 2; i++) {
    s[i]->draw();
  }
  s[1]->dance(); // will not compile
}
 
void g(Circle *c) {}

The reason why C style pointers falls short here is the pointer dereferencing operation now needs to understand the actual type of the element whose memory address it holds as opposed to the statically declared type. Line #21 is one such situation.

C++ specifically as a language aimed for the highest levels of compatibility with C and hence the choice seems to have to not change the underlying implementation of pointers. So, the implementation of a pointer continues to be no more than a reference to the memory address of the value being pointed to. Dynamic dispatch was implemented using what is commonly known as vtables. The example shown above would look as follows:

Each object instance contains a pointer to the vtable (henceforth known as vtpr). Given that structs & classes were functionally interchangeable in C++ and the fact that the object layout of structs as defined in C did not have vtables; this hack seems acceptable. The trick here is that types that do no need dynamic dispatch (i.e. no virtual functions defined in the inheritance hierarchy) do not contain the vptr. Thus a C style struct compiled in C has binary compatibility with the same struct defined in C for a given compiler & target platform.

Our good friend Java has pretty much the same implementation with the difference being that the vptr is always present for all objects. This decision can be rationalized using the C++ rules given the following aspects of Java

• All methods are polymorphic
• The “Object” type has methods
• All classes as implicitly derived from the Object type

Typesafe downcasting

One of the shortcomings of C was that it was possible to interpret bytes any memory address as representation of any type. This would result in all sorts of unexpected behaviour is now considered a fairly dangerous operation. Going to our example above, the for loop did not care about the specific shape and performed a polymorphic operation over the array. Let us assume that we now wish to call the function g() with the second element of the array. A C style cast would permit both the first and the second element of the array to be cast to a Circle when only the second operation happens to be correct in reality.

Trying to cast s[0] to a Circle would result in a runtime exception in Java. A similar effect can also be achieved in C++ if we were to use the dynamic_cast feature. Dynamic casts however was not universally available in C++ initially. It required either enabling RTTI explicity or that the type in question have a virtual function or both. The reason why this was conditional in C++ & always available in Java is not hard to guess: the underlying implementation relies on the presence of the vptr in each object.

Runtime implementations do not look at the type of the pointer i.e. s[0], s[1], etc. etc. to figure out the actual type of the object being pointed but instead rely on the vptr pointing to the actual type’s vtable (or more generally, type specific information). Downcast operations can now check against this actual type and requested type (in the cast) to check if they are assignable based on static rules and thus provide the necessary type safety.

Objects with headers

One of the more subtle problems with this design is that it makes it near impossible to safely dump & restore the entire area of memory representing an object across any two running instances of a program. This stems from the fact that the address at which the vtable for a given type resides is not fixed across two runs of even the same program on the same machine. This problem is trivially true of any type that contains a pointer to practically anything. A completely pointer free type hard to imagine in Java (reference = pointers for you Java folks in case you are wondering) given that fact that only primitives are expected to be held inline (barring escape analysis magic). This is not true in the case of C++. Another area besides the dump/restore (a.k.a. serialization) pattern where embedded pointers becomes an issue is in the case of shared memory across process boundaries.

Given go’s aspiration to be a system level language while providing some OOP features, the language designers chose to rethink pointer implementations from the grounds up. Interestingly, Java 8 has plans to support headerless types to deal with such situations. These would however be closer to C structs as they would not have any methods.

Go’s way of looking at pointers

A pointer in go contains two memory addresses as opposed to just one. One of them points to the object and the other to the vtable. Here is a pictorial representation of what the memory layout in an equivalent go program would look like:

This is unlike what most language’s runtimes choose to do. One of the biggest advantage of this mechanism is that primitive types no longer need a boxed variant for them to work with code that expects objects. Both Java & C# lack this option; thus forcing developers to make a tradeoff between runtime performance and ease of programming. The other problems caused by object with headers also is a non-issue in this case.

It is easy to see that both dynamic dispatch & typesafe casts can be implemented with the same level of fidelity using this technique as in the case of vptrs being embedded inside object instances.

The drawback however is that pointers in go are conceptually have twice the memory footprint when compared to any other language. It isn’t hard to imagine a world wherein the number of live pointers exceeds the number of live objects; hence the overhead is highly likely. The only special case that I could think of where this could be optimized away if we are dealing with arrays of objects. In such cases, the vptr needs to be held just once (in the pointer to the array) and not once per element of the array.

Overall, this seems to be a good innovation that can make the code run faster and also reducing the tradeoff decisions that developers have to make.