Thursday, September 16, 2010

Object-Oriented C (part 3)

In this exciting conclusion to the object-oriented C programming series, I will discuss a couple of drawbacks to my prior solution, as well as compare my implementation to those provided by OO compilers.

Drawback #1: Branch Prediction
It is important to remember that a branch is any instruction that changes the instruction pointer, which includes function calls.  Most functional calls are straightforward; however, some branches use a register (i.e., runtime value) for their destination, most commonly with function pointers and switch statements.  Ray tracers may already use oct-trees to reduce the set of intersection objects.  Further sorting a set of objects into their different types would present an easier to predict sequence of indirect function calls.

Drawback #2: Inheritance is Explicit
All of the OO inheritance is up to the programmer.  There is no assistance from the compiler to ensure that classes inherit correctly, nor for "constructors" or protection of fields.  This forces the programmer(s) to be quite disciplined in their usage.  Under particular circumstances, I'd not worry about this, but in general I would want the compiler to keep an eye on the usage of this model.

To reprise, for someone who has limited experience with C++ and its notation (like I did at the time), using the limited OO capabilities provided by this solution proved ideal.

All of this work hinged on an important "law of programming": If a compiler / run-time can do something implicitly, the programmer can do so explicitly.  (See More Rules).  Because a compiler for C++ is generating machine code to support OO, there must be a way to write code to give an equivalent compilation in C.  So then what does the C++ compiler generate?  (As someone who has not written a compiler and is not disassembling C++ programs, the following will remain speculation, though clarifying comments are appreciated).

I can conceive of three ways for a compiler to store an object's functional information:
1) Type field.  The type of an instance is always clearly known, but types must be globally unique.  Any code wishing to perform operations needs multiple levels of indirection to get from a "type" to the appropriate function.  Bleh.
2) Direct inlined fields.  This is effectively the solution in C.
3) Indirect fields.  Keep a single table of function pointers for this type in memory.  While this saves the memory for a couple of function pointers, there is an additional layer of indirection that must be traversed on every function call.

My remaining question is: "how does a compiler / run-time address 'diamond' inheritance"?  That is, classes that inherit from multiple distinct classes.

No comments: