In my previous article I described the basic layout of a C++ object in Metrowerks CodeWarrior, with a pointer in the object to a static table of function pointers and a class description structure. Now we can look at how single inheritance is implemented.
Simple inheritance is, well, simple: the derived class simply contains the first class at the beginning and new data later in memory. The same thing is true for the vtable - new entries are tacked on the end.
(Please note that this is not true for virtual base classes - I'll get to that later.)
This meets our rule: a pointer to X must be laid out the same. Since derived class Y contains X at its beginning, the first bytes of Y look like an X.
Here's subclassing from the last post...
class bar : public foo {
virtual void b(float); // ovrrride
virtual void new_method(int);
char * new_member;
};
virtual base class - only one copy of the base no matter how we derive. How?
struct bar_vtable {
foo_vtable parent;
void (* new_method_func)(int);
};
void bar_b(float);
void bar_new_method(int);
static type_id bar_type_id = { ... };
static bar_vtable sbar_vtable = { &bar_type_id, 0, foo_a, bar_b, bar_new_method };
struct bar {
foo parent; /* superclass goes first. */
char * new_member; /* then new members. */
};
Note that a new vtable is made for the derived class, which may contain a mix of functions - here we have the "a" virtual function from the superclass, an overridden "b" function (bar_b, an override, goes into a slot in foo's vtable), and then a new virtual function in the end.
In fact, bar_b in a slot in a foo_vtable is where the "magic" of overrides happen. This is what lets us call a method from a foo * and get a method from a bar object. Because an object points to its classes vtable, we get that class's behavior.
Saturday, February 24, 2007
Friday, February 23, 2007
C++ Objects Part 1: Basic Object Memory Layout
I spent a few minutes dissecting the C++ internal runtime structure for objects within Metrowerks CodeWarrior. There's some internal guts that C++ generates when you make objects; the format is not standardized between compilers, but looking at one implementation reveals some of the costs and implications of C++ objects and inheritance.
C++ breaks objects with methods down into data structures and functions, with function pointers used for virtual functions. Polymorphism depends on our ability to apply fixed unchanging code to diverse data structures and get meaningful execution. Therefore we can immediately postulate one rule that applies to all objects, no matter what C++ feature is used (inheritance, multiple inheritance, virtual base classes, etc): the in-memory layout of a pointer to class X must have a fixed layout no matter what real derived type the object has.
I'm only going to describe the case where objects have virtual functions and run-time type information. Based on the actual code and compiler settings, the compiler may sometimes eliminate these features, changing the in-memory structure, but that's a topic for another blog entry.
CodeWarrior (like virtually all C++ compilers, no pun intended) implements virtual methods via virtual function tables (vtables), which are static structures containing one function pointer for each virtual function. An object has a pointer to its class's vtable before any other object data; there is only one copy of the vtable per class - it's immutable and shared. (This makes objects smaller than having pointers to each virtual function in the actual object.)
The virtual function table actually contains two more entries before the function pointers: a pointer to a "type ID" structure, a separate structure that describes the class itself, and a memory offset whose use we'll look at later. So if we have this C++ code:
class foo {
virtual void a(int);
virtual void b(float);
int c;
float d;
};
The equivalent C code would look something like this:
struct foo_vtable {
typeid * type_id_ptr;
int offset;
void (* ptr_to_a)(int);
void (* ptr_to_b)(float);
};
void foo_a(int) { }
void foo_b(float) { }
static type_id foo_type_id = { ... };
static foo_vtable sfoo_vtable = { &foo_type_id, 0, foo_a, foo_b };
struct foo {
foo_vtable * vtable; // gets inited to &sfoo_vtable
int c;
float d;
};
Class type is stored separately - first ptr in the v-table. Motivation for this will be clear later.
Vtable has an offset - also understood later.
C++ breaks objects with methods down into data structures and functions, with function pointers used for virtual functions. Polymorphism depends on our ability to apply fixed unchanging code to diverse data structures and get meaningful execution. Therefore we can immediately postulate one rule that applies to all objects, no matter what C++ feature is used (inheritance, multiple inheritance, virtual base classes, etc): the in-memory layout of a pointer to class X must have a fixed layout no matter what real derived type the object has.
I'm only going to describe the case where objects have virtual functions and run-time type information. Based on the actual code and compiler settings, the compiler may sometimes eliminate these features, changing the in-memory structure, but that's a topic for another blog entry.
CodeWarrior (like virtually all C++ compilers, no pun intended) implements virtual methods via virtual function tables (vtables), which are static structures containing one function pointer for each virtual function. An object has a pointer to its class's vtable before any other object data; there is only one copy of the vtable per class - it's immutable and shared. (This makes objects smaller than having pointers to each virtual function in the actual object.)
The virtual function table actually contains two more entries before the function pointers: a pointer to a "type ID" structure, a separate structure that describes the class itself, and a memory offset whose use we'll look at later. So if we have this C++ code:
class foo {
virtual void a(int);
virtual void b(float);
int c;
float d;
};
The equivalent C code would look something like this:
struct foo_vtable {
typeid * type_id_ptr;
int offset;
void (* ptr_to_a)(int);
void (* ptr_to_b)(float);
};
void foo_a(int) { }
void foo_b(float) { }
static type_id foo_type_id = { ... };
static foo_vtable sfoo_vtable = { &foo_type_id, 0, foo_a, foo_b };
struct foo {
foo_vtable * vtable; // gets inited to &sfoo_vtable
int c;
float d;
};
Class type is stored separately - first ptr in the v-table. Motivation for this will be clear later.
Vtable has an offset - also understood later.
Virtual Base Class - Not Needed for Interfaces
I was going to argue that virtual base classes are logical for interfaces, because we really only need each interface once. E.g.:
class IDeletable {
public:
virtual void delete()=0;
};
class IDrawable : public virtual IDeletable {
public:
virtual void Draw()=0;
};
class ISerializable : public virtual IDeletable {
public:
virtual void Serialize()=0;
};
void PersistentDrawing : public virtual IDrawable, public virtual ISerializable {
};
Turns out we don't need to virtualize the base classes. Virtualizing the base class is used when we have multiple copies of the base class inherited from different objects and we don't want actual copies of the base class.
But Don Box points out in "Essential COM" that this isn't necessary. In particular because the interfaces are truly empty - only a virtual function table, there is no harm in having multiple copies of them in an object. The virtual functions will be overriden correctly even if that base is represented multiple times. (The memory layout for this is moderately surprising, but I'll comment on this some other time.)
class IDeletable {
public:
virtual void delete()=0;
};
class IDrawable : public virtual IDeletable {
public:
virtual void Draw()=0;
};
class ISerializable : public virtual IDeletable {
public:
virtual void Serialize()=0;
};
void PersistentDrawing : public virtual IDrawable, public virtual ISerializable {
};
Turns out we don't need to virtualize the base classes. Virtualizing the base class is used when we have multiple copies of the base class inherited from different objects and we don't want actual copies of the base class.
But Don Box points out in "Essential COM" that this isn't necessary. In particular because the interfaces are truly empty - only a virtual function table, there is no harm in having multiple copies of them in an object. The virtual functions will be overriden correctly even if that base is represented multiple times. (The memory layout for this is moderately surprising, but I'll comment on this some other time.)
Tuesday, February 20, 2007
Inherit the Wind
Usually I post here after concluding something, usually after a discussion. But this post is the part that comes first - groping with the underlying issues.
Unfortunately a number of my software engineering books are temporarily inaccessible. We packed our (unsorted) library when we moved a few months ago, and because we are redoing a large chunk of the house, everything is still in boxes. As if having to search linearly for any book wasn't demoralizing enough to a programmer, some of the boxes are on top of each other, making whole ranges very difficult to get to. My spirit is broken by O(N).
Anyway, the issue is: given a series of interfaces to a conceptual hierarchy and an implementation hierarchy, how do you implement this in C++? The following gets very ugly very fast:
class IPoint {
virtual Point2 Get()=0;
};
class IBezierPoint : public IPoint {
virtual Vector2 GetCtl()=0;
};
class WED_Point : public IPoint {
virtual Point2 Get()=0;
Point2 internal_pt;
};
If you've done this kind of design before, you can see how we're about to go straight off the clifff...
class WED_BezierPoint : public, um, um.
The problem is that if I inherit from my base implementation (WED_Point) and my full supported interface (IBezierPoint) I pick up two instances of the interface IPoint. This will not make C++ happy and is almost surely not what we want. (The result will be a bunch of "method not overridden" warnings and probably a lot of incorrect polymorphic behavior.)
There are only three ways to solve this in C++ and they all suck in different ways:
1. Don't inherit implementation. This is what I would tell anyone else - inheriting implementation is evil, bla bla bla. In otherwords, WED_BezierPoint derives only from IBezierPoint and reimplements storage for its base point. Because WED_BezierPoint supports the IPoint interface (by way of IBezierPoint) clients still get the appearance of polymorphism via the interface, which is what we really care about.
The only problem with this is that we end up recoding a lot of implementation. Inheritence of implementation is almost always a lousy idea, but in this case I can't help but think that it's giving us something similar to database normalization. Still, one could definitely argue that all algoirthm code should be working with IBezierPoint or IPoint and thus the repeat-implementation is really a non-issue. So breaking the implementation hierarchy might be the least-skanky thing to do.
1a. It should be noted that we can make an implementation hierarchy and contain it in classes derived from the interfaces but not each other. This is a "bridge" pattern and will get us out of trouble in a lot of different design cases.
2. Don't inherit interface. In otherwords, IBezierPoint doesn't derive from IPoint. This solves the problem, but with a rather weird result: IBezierPoints might not be points at all.
You can argue that since these interfaces are meant to be run-time cast and checked anyway, that this is okay, but I think we lose something here. It would be nice to require that all bezier points be points - that is what we mean, so having the compiler require it is nice. I'd have to catagorize this fix as skanky.
(It should be noted that having independent interfaces is a good thing a lot of the time. Just maybe not when a very clear IS-A relationship exists.)
3. Make the interfaces virtual base classes. Do two C++ wrongs make a right? Probably not, but for the sake of argument, if all interfaces are virtual base classes then we can have the IPoint interface from two places at once.
One warning about this: if you make your interfaces virtual you need to subclass from them virtually in two places - both when one interface is derived from another and when a base implementation class derives from an interface. (The implementation derivation can be non-virtual - as long as all but one relationship is virtual, C++ will figure out what we mean, at least in CodeWarrior where I tested this.)
I suppose it should be noted that, as gross as using virtual base classes is, if you derive your C++ interfaces from some kind of common casting base (read: IUnknown) it has to be a virtual base class anyway.
Unfortunately a number of my software engineering books are temporarily inaccessible. We packed our (unsorted) library when we moved a few months ago, and because we are redoing a large chunk of the house, everything is still in boxes. As if having to search linearly for any book wasn't demoralizing enough to a programmer, some of the boxes are on top of each other, making whole ranges very difficult to get to. My spirit is broken by O(N).
Anyway, the issue is: given a series of interfaces to a conceptual hierarchy and an implementation hierarchy, how do you implement this in C++? The following gets very ugly very fast:
class IPoint {
virtual Point2 Get()=0;
};
class IBezierPoint : public IPoint {
virtual Vector2 GetCtl()=0;
};
class WED_Point : public IPoint {
virtual Point2 Get()=0;
Point2 internal_pt;
};
If you've done this kind of design before, you can see how we're about to go straight off the clifff...
class WED_BezierPoint : public, um, um.
The problem is that if I inherit from my base implementation (WED_Point) and my full supported interface (IBezierPoint) I pick up two instances of the interface IPoint. This will not make C++ happy and is almost surely not what we want. (The result will be a bunch of "method not overridden" warnings and probably a lot of incorrect polymorphic behavior.)
There are only three ways to solve this in C++ and they all suck in different ways:
1. Don't inherit implementation. This is what I would tell anyone else - inheriting implementation is evil, bla bla bla. In otherwords, WED_BezierPoint derives only from IBezierPoint and reimplements storage for its base point. Because WED_BezierPoint supports the IPoint interface (by way of IBezierPoint) clients still get the appearance of polymorphism via the interface, which is what we really care about.
The only problem with this is that we end up recoding a lot of implementation. Inheritence of implementation is almost always a lousy idea, but in this case I can't help but think that it's giving us something similar to database normalization. Still, one could definitely argue that all algoirthm code should be working with IBezierPoint or IPoint and thus the repeat-implementation is really a non-issue. So breaking the implementation hierarchy might be the least-skanky thing to do.
1a. It should be noted that we can make an implementation hierarchy and contain it in classes derived from the interfaces but not each other. This is a "bridge" pattern and will get us out of trouble in a lot of different design cases.
2. Don't inherit interface. In otherwords, IBezierPoint doesn't derive from IPoint. This solves the problem, but with a rather weird result: IBezierPoints might not be points at all.
You can argue that since these interfaces are meant to be run-time cast and checked anyway, that this is okay, but I think we lose something here. It would be nice to require that all bezier points be points - that is what we mean, so having the compiler require it is nice. I'd have to catagorize this fix as skanky.
(It should be noted that having independent interfaces is a good thing a lot of the time. Just maybe not when a very clear IS-A relationship exists.)
3. Make the interfaces virtual base classes. Do two C++ wrongs make a right? Probably not, but for the sake of argument, if all interfaces are virtual base classes then we can have the IPoint interface from two places at once.
One warning about this: if you make your interfaces virtual you need to subclass from them virtually in two places - both when one interface is derived from another and when a base implementation class derives from an interface. (The implementation derivation can be non-virtual - as long as all but one relationship is virtual, C++ will figure out what we mean, at least in CodeWarrior where I tested this.)
I suppose it should be noted that, as gross as using virtual base classes is, if you derive your C++ interfaces from some kind of common casting base (read: IUnknown) it has to be a virtual base class anyway.
Saturday, February 17, 2007
Prototypes - Your Annoying Friend
Depending on your C++ compiler, when you start a project, C++ may require a prototype declaration for functions or not.
You really want prototypes! Here's why:
According to some byzantine aspect of C/C++, if you use a function that isn't defined and you don't have C++ requiring prototypes, then C++ will assume that the function (a) exists and (b) takes arguments that are exactly like what you are passing!
Now if the function doens't exist, you don't need prototypes to help you - you'll get a link error later on saying "we never found this function". Prototypes are better because it doesn't take a full compile to find out.
But where things really get ugly is if the function does exist, but the calling conventions you passed in assume an implicit conversion. For example, imagine if your function goes like this:
void some_happy_func(float n);
Now you call it like this:
some_happy_func(2.0);
Without prototypes, this probably will cause a lot of pain. Why? Well, 2.0 is a double-precision argument! If some_happy_func's prototype exists, the compiler will create an implicit conversion. But if it doesn't, the compiler will assume some_happy_func takes doubles, and generate an incorrect stack (with a double on it). When some_happy_func actually runs, it will interpret the low 32 bits of that double as a float and all hell will break loose.
In my experience, when prototypes reuqirements are off it's really easy to lose track of whether you've included a needed header or not, causing possibly subtle bugs where functions fail sometimes based on the calling code's headers. If the failure causes a hard-to-detect bug it can take a while to unravel this.
You really want prototypes! Here's why:
According to some byzantine aspect of C/C++, if you use a function that isn't defined and you don't have C++ requiring prototypes, then C++ will assume that the function (a) exists and (b) takes arguments that are exactly like what you are passing!
Now if the function doens't exist, you don't need prototypes to help you - you'll get a link error later on saying "we never found this function". Prototypes are better because it doesn't take a full compile to find out.
But where things really get ugly is if the function does exist, but the calling conventions you passed in assume an implicit conversion. For example, imagine if your function goes like this:
void some_happy_func(float n);
Now you call it like this:
some_happy_func(2.0);
Without prototypes, this probably will cause a lot of pain. Why? Well, 2.0 is a double-precision argument! If some_happy_func's prototype exists, the compiler will create an implicit conversion. But if it doesn't, the compiler will assume some_happy_func takes doubles, and generate an incorrect stack (with a double on it). When some_happy_func actually runs, it will interpret the low 32 bits of that double as a float and all hell will break loose.
In my experience, when prototypes reuqirements are off it's really easy to lose track of whether you've included a needed header or not, causing possibly subtle bugs where functions fail sometimes based on the calling code's headers. If the failure causes a hard-to-detect bug it can take a while to unravel this.
Monday, January 29, 2007
Why Not Binary Blobs?
I am working on the data model for WorldEditor, the X-Plane graphical scenery editor. At risk of "life blogging" the development, the design decisions for WED illustrate some design ideas.
WED uses C++ objects to represent the user's data in memory (the "internal data model"). I'll comment at another time on why I made this decision. On disk, however, WED uses an SQLite database file. That's another blog post too.
So one must ask the question, why do we need an on-disk data-model at all? Why not just dump out the C++ object contents to a file?
One might say "because you can't write STL classes to disk verbatim due to their internal pointers and private structure." But...WED uses an object-based undo system that requires each object to know how to serialize itself to a buffer...this means that we've already written serialization code for all of those STL structures.
It would make development faster to just reuse the object serialization code, but the result would be a file format that is a side-effect of the implementation code. This isn't good if:
In the short term you save time on writing file I/O code, but as soon as you change the object format you must write new code to read the old file format, so you pay the "cost" of that code eventually -- but you must write this code against a file format that wasn't really "designed" at all.
In particular with WED, we want the file format to be stable and low-change over a long period of time, because the kind of data that might be in a WED file can be useful over a relatively long lifetime.
Given this, I am writing an explicit file format up-front rather than use the object serialization mechanism.
WED uses C++ objects to represent the user's data in memory (the "internal data model"). I'll comment at another time on why I made this decision. On disk, however, WED uses an SQLite database file. That's another blog post too.
So one must ask the question, why do we need an on-disk data-model at all? Why not just dump out the C++ object contents to a file?
One might say "because you can't write STL classes to disk verbatim due to their internal pointers and private structure." But...WED uses an object-based undo system that requires each object to know how to serialize itself to a buffer...this means that we've already written serialization code for all of those STL structures.
It would make development faster to just reuse the object serialization code, but the result would be a file format that is a side-effect of the implementation code. This isn't good if:
- You want to edit the data from another application without having code interdendencies or
- You want to refactor the code (which would cause object layout to change) or
- You want to read a subset of the data. (The in-memory structure is, well, in-memory, so it assumes you have access to everything.
In the short term you save time on writing file I/O code, but as soon as you change the object format you must write new code to read the old file format, so you pay the "cost" of that code eventually -- but you must write this code against a file format that wasn't really "designed" at all.
In particular with WED, we want the file format to be stable and low-change over a long period of time, because the kind of data that might be in a WED file can be useful over a relatively long lifetime.
Given this, I am writing an explicit file format up-front rather than use the object serialization mechanism.
Thursday, January 25, 2007
Windows Vista - Stable API
I'm not a huge fan of Microsoft or Windows Vista, and I do all my primary development on a Mac. But...
The same X-Plane code that runs on Windows Vista will run on Windows 98 SE.
In that time Apple has changed the API (introducing Carbon), the ABI twice (moving from CFM to Mach-O, and GCC3 to 4*) and the instruction set (PPC to Intel), as well as the compiler twice (MPW to X-Code, or more likely Metrowerks to X-Code, and GCC 3 to 4).
I love Apple dearly, but if I write an app and burn the source code, I wouldn't be surprisde if the binaries run on Windows 5 years from now. I wouldn't make that prediction for the Mac.
*Is it fair to call the upgrade from GCC 3 to 4 an ABI change or compiler change? Not really, they're not full ones, but besides the usual slight changes, the real problem is that GCC 4 generates run-time dependencies on shared libraries that were not available in older Mac Operating Systems. This is why X-Plane is not alone in requiring OS X 10.3.9 or higher - 10.3.9 is the oldest operating system that has the runtime for GCC 4. Applications that can run all the way back to OS X 10.2 are actually building their PowerPC executable code against a different deployment target, which requires extra makefile gymnastics.
The same X-Plane code that runs on Windows Vista will run on Windows 98 SE.
In that time Apple has changed the API (introducing Carbon), the ABI twice (moving from CFM to Mach-O, and GCC3 to 4*) and the instruction set (PPC to Intel), as well as the compiler twice (MPW to X-Code, or more likely Metrowerks to X-Code, and GCC 3 to 4).
I love Apple dearly, but if I write an app and burn the source code, I wouldn't be surprisde if the binaries run on Windows 5 years from now. I wouldn't make that prediction for the Mac.
*Is it fair to call the upgrade from GCC 3 to 4 an ABI change or compiler change? Not really, they're not full ones, but besides the usual slight changes, the real problem is that GCC 4 generates run-time dependencies on shared libraries that were not available in older Mac Operating Systems. This is why X-Plane is not alone in requiring OS X 10.3.9 or higher - 10.3.9 is the oldest operating system that has the runtime for GCC 4. Applications that can run all the way back to OS X 10.2 are actually building their PowerPC executable code against a different deployment target, which requires extra makefile gymnastics.
Subscribe to:
Posts (Atom)