Jump to content

  • Log In with Google      Sign In   
  • Create Account


Like
11Likes
Dislike

Managing Decoupling Part 3: C++ Duck Typing

By Niklas Frykholm | Published Apr 19 2013 12:42 AM in Game Programming
Peer Reviewed by (Josh Vega, incertia, Nercury)

engine design decoupling program organization systems

Previous Articles
Some systems need to manipulate objects whose exact nature are not known. For example, a particle system has to manipulate particles that sometimes have mass, sometimes a full 3D rotation, sometimes only 2D rotation, etc. (A good particle system anyway, a bad particle system could use the same struct for all particles in all effects. And the struct could have some fields called custom_1, custom_2 used for different purposes in different effects. And it would be both inefficient, inflexible and messy.)

Another example is a networking system tasked with synchronizing game objects between clients and servers. A very general such system might want to treat the objects as open JSON-like structs, with arbitrary fields and values:

{
    "score" : 100,
    "name": "Player 1"
}

We want to be able to handle such “general” or “open” objects in C++ in a nice way. Since we care about structure we don’t want the system to be strongly coupled to the layout of the objects it manages. And since we are performance junkies, we would like to do it in a way that doesn’t completely kill performance. i.e., we don’t want everything to inherit from a base class Object and define our JSON-like objects as:

typedef std::map OpenStruct;

Generally speaking, there are three possible levels of flexibility with which we can work with objects and types in a programming language:

1. Exact typing - Only ducks are ducks


We require the object to be of a specific type. This is the typing method used in C and for classes without inheritance in C++.

2. Interface typing - If it says it’s a duck


We require the object to inherit from and implement a specific interface type. This is the typing method used by default in Java and C# and in C++ when inheritance and virtual methods are used. It is more flexible that the exact approach, but still introduces a coupling, because it forces the objects we manage to inherit a type defined by us.

Side rant: My general opinion is that while inheriting interfaces (abstract classes) is a valid and useful design tool, inheriting implementations is usually little more than a glorified “hack”, a way of patching parent classes by inserting custom code here and there. You almost always get a cleaner design when you build your objects with composition instead of with implementation inheritance.

3. Duck typing - If it quacks like a duck


We don’t care about the type of the object at all, as long as it has the fields and methods that we need. An example:

def integrate_position(o, dt):
	o.position = o.position + o.velocity * dt

This method integrates the position of the object o. It doesn’t care what the type of o is, as long as it has a “position” field and a “velocity” field.

Duck typing is the default in many “scripting” languages such as Ruby, Python, Lua and JavaScript. The reflection interface of Java and C# can also be used for duck typing, but unfortunately the code tends to become far less elegant than in the scripting languages:

o.GetType().GetProperty(ÃÃÃÃâPositionÃÃÃÃâ).SetValue(o, o.GetType().
	GetProperty(ÃÃÃÃâPositionÃÃÃÃâ).GetValue(o, null) + o.GetType().
	GetProperty(ÃÃÃÃâVelocityÃÃÃÃâ).GetValue(o, null) * dt, null)

What we want is some way of doing “duck typing” in C++.

Let’s look at inheritance and virtual functions first, since that is the standard way of “generalizing” code in C++. It is true that you could do general objects using the inheritance mechanism. You would create a class structure looking something like:

class Object {...};
class Int : public Object {...};
class Float : public Object{...};

and then use dynamic_cast or perhaps your own hand-rolled RTTI system to determine an object’s class.

But there are a number of drawbacks with this approach. It is quite verbose. The virtual inheritance model requires objects to be treated as pointers so they (probably) have to be heap allocated. This makes it tricky to get a good memory layout. And that hurts performance. Also, they are not PODs so we will have to do extra work if we want to move them to a co-processor or save them to disk.

So I prefer something much simpler. A generic object is just a type enum followed by the data for the object:


Attached Image: duck_typing_1-300x72.png


To pass the object you just pass its pointer. To make a copy, you make a copy of the memory block. You can also write it straight to disk and read it back, send it over network or to an SPU for off-core processing.

To extract the data from the object you would do something like:

unsigned type = *(unsigned *)o;
if (type == FLOAT_TYPE)
    float f = *(float *)(o + 4);

You don’t really need that many different object types: bool, int, float, vector3, quaternion, string, array and dictionary is usually enough. You can build more complicated types as aggregates of those, just as you do in JSON.

For a dictionary object we just store the name/key and type of each object:


Attached Image: duck_typing_2-1024x138.png


I tend to use a four byte value for the name/key and not care if it is an integer, float or a 32-bit string hash. As long as the data is queried with the same key that it was stored with, the right value will be returned. I only use this method for small structs, so the probability for a hash collision is close to zero and can be handled by “manual resolution”.

If we have many objects with the same “dictionary type” (i.e. the same set of fields, just different values) it makes sense to break out the definition of the type from the data itself to save space:


Attached Image: duck_typing_3-1024x312.png


Here the offset field stores the offset of each field in the data block. Now we can efficiently store an array of such data objects with just one copy of the dictionary type information:


Attached Image: duck_typing_4-1024x162.png


Note that the storage space (and thereby the cache and memory performance) is exactly the same as if we were using an array of regular C structs, even though we are using a completely open free form JSON-like struct. And extracting or changing data just requires a little pointer arithmetic and a cast.

This would be a good way of storing particles in a particle system. (Note: This is an array-of-structures approach, you can of course also use duck typing with a sturcture-of-arrays approach. I leave that as an exercise to the reader.)

If you are a graphics programmer all of this should look pretty familiar. The “dictionary type description” is very much like a “vertex data description” and the “dictionary data” is awfully similar to “vertex data”. This should come as no big surprise. Vertex data is generic flexible data that needs to be processed fast in parallel on in-order processing units. It is not strange that with the same design criterions we end up with a similar solution.

Morale and musings


It is OK to manipulate blocks of raw memory! Pointer arithmetic does not destroy your program! Type casts are not “dirty”! Let your freak flag fly!

Data-oriented-design and object-oriented design are not polar opposites. As this example shows a data-oriented design can in a sense be “more object-oriented” than a standard C++ virtual function design, i.e., more similar to how objects work in high level languages such as Ruby and Lua.

On the other hand, data-oriented-design and inheritance are enemies. Because designs based on base class pointers and virtual functions want objects to live individually allocated on the heap. Which means you cannot control the memory layout. Which is what DOD is all about. (Yes, you can probably do clever tricks with custom allocators and patching of vtables for moving or deserializing objects, but why bother, DOD is simpler.)

You could also store function pointers in these open structs. Then you would have something very similar to Ruby/Lua objects. This could probably be used for something great. This is left as an exercise to the reader.


Reprinted with permission from The Bitsquid blog.



About the Author(s)


Niklas is the system architect at Bitsquid. Prior to starting Bitsquid he worked together with Tobias as lead programmer and technical director at Grin for over six years, producing multiple titles for PC, X360 and PS3.

License


GDOL (Gamedev.net Open License)




Comments

I like some of your ideas but I can't help but to think that your idea of decoupling is making all functions take void* arguments and making all UDTs char buffers or possibly PODs that are easily castable to continuous memory blocks.

 

Also calling this solution Duck Typing is a big stretch to say the least. Duck Typing is about behavior not data. It should "walk" and "quack" like a duck and not be "memory access optimized map". std::map<> is not a DT representative nor is presented solution.

 

Also, it would be nice to see the code that shows how you could replace presented python snipped in C++ with 2 example "types" that share "interface" based on your proposed solution.

 

Please don't get me wrong. I like the article very much, in fact I try to read everything you write and I am now also thinking how to wrap your "dynamic type" in templates to make a nice interface to underlying buffer. Would kindof be similar to boost::flat_map i suppose in which key-value pairs are stored in a vector (instead of a node-based tree) for the best cache usage.

This is all fine until the "data" needs to include dynamically allocated data, i.e. variable length strings or arrays, then suddenly you have no way to safety copy the data by copying memory.

 

Qt's QVariant provides a pretty clever example of a truly type-safe and copy-safe multiple-type container as does, I assume, boost::any. Mangling raw memory is not an extensible solution.

in my case, I actually hide the object-type (for allocated object) in the memory-allocator, and often use predicate functions to check for types (for plain structs, this is more convenient than using an explicit type within the struct itself). this means though that the passed object pointer points to just after the object header.

 

another related strategy is to use the type to fetch a vtable, and then use the vtable for operations.

 

for example:

if(fooParticleP(obj)) { ... }

fooParticleGetVT(obj)->Update(obj, dt);

fooParticleGetVT(obj)->Draw(obj);

...

 

in many cases (such as for very frequent operations), this can be a lot faster than using if/else chains. (like, you don't want a long set of if/else chains in the middle of a particle drawing or update loop...).

 

 

for primitive types, much more preferable IMO is to use a tagged-value.

the tagged value could be, for example, a 64-bit value held as a single value in a struct, with 4 bits or so being used as a type-tag.

 

operations can then mostly be wrapped, for example like:

if(fooIntP(val))
    { i=fooIntvF(val)*251; val2=fooInt(i); }
else if(fooFloatP(val))
    { f=fooFloatvF(val)*3.14159; val2=fooFloat(f); }
else ...

 

where, for example:

static inline bool fooIntP(fooVal val)
   { return((bool)((0x6006>>((int)((val.v>>60)&15)))&1)); }
static inline int fooIntvF(fooVal val)
   { return((int)(val.v)); }
static inline fooVal fooInt(int val)
{
    fooVal t;
    t.v=(uint64_t)(((int64_t)val)^0x1000000000000000LL);
    return(tmp);
}

static inline void *fooPtrvF(fooVal a)
    { return((void *)((intptr_t)(a.v))); }
static inline fooVal fooPtrF(void *p)
{
    fooVal l;
    l.v=(uint64_t)((intptr_t)p);
    return(l);
}
static bool fooPtrP(fooVal a)
    { return((bool)((0x8001>>((int)((a.v>>60)&15)))&1)); }

 

well, sort of, it may get a little more involved than this (for example, the above actually has 4 tag values for 'int', whereas one may notice that this would actually be for a 62-bit value, just the logic for 62-bit values is less concise...).

 

this avoids the need to provide allocated storage for the tagged value, it is simply copied around by value, and also helps abstract over the exact representation of the value.

 

granted, this does come at a cost of needing to wrap/unwrap pointers (so it is more of a hassle in this sense). while this wastes space on 32-bit targets for storing pointers, this can be outweighed by its ability to avoid needing to box doubles (or be stuck with the relatively poor precision that is "a float with several bits cut off").

I accidentally downvoted you, I meant to up vote you but my laptop's mousepad is super sensitive.  Anyway, thank you for these articles, they came at a perfect time in the development of my engine.

I like your articles and find the interesting, but again I have no clue why you are even using C++ instead of plain old C. 

Hmm, aren't templates the way to achieve duck typing in C++ ?
 
I mean your Python example:
 

def integrate_position(o, dt):
    o.position = o.position + o.velocity * dt

 
could be written in C++ as following:

template <class Movable, class Period>
void integrate_position(Movable o, Period dt)
{
 o.position = o.position + o.velocity * dt;
}

You can use it simply: integrate_position(objectOfMyType, whateverAmount) and the compiler will generate the code for appropriate types.

I'll start at a criticism but end with a question.

 

I have to disagree that inheritance is generally a bad thing.  Simply put, some code should not be replicated, because you've simply created multiple points of failure where there should be only one.  And some times, composition doesn't cover what is needed, because it can lead to nasty practices like deeply nested proxy methods that turn one method call into many, which is bad for performance and maintainability.  Building function call stack entries is not, as is commonly believed, free.  Sometimes, inheritance is just the right answer, and I think that a greater effort should be placed on illuminating the situations in which it is non-optimal rather than simply blasting the entire mechanic without providing some basis for the argument.

 

Disagreements aside, the article is more than a little interesting, and I was wondering if you might in the future present some article which shows how to use this data structuring methodology to implement something more complicated like a tree structure or something in terms of code rather than just diagrams and textual descriptions.  Even though you give very good descriptions, I feel like a little more code would help show how composing these types together would happen.

 

Thanks for the article series.


Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS