Optimize for Iteration Time

Our tools are not getting any faster. Linkers suck. Compilers bog down under loads of templates and inline functions. What can be done?

We can try to optimize for iteration time.  Separate compilation is the best iteration time tool we have in our arsenal when programming vanilla C/C++.

Take inline functions as an example. My advice: while developing a system, prefer to not make anything inline. Inlining functions forces you to expose your data structures in header files. Data structures change continually as you’re working on a system. Design away that iteration time pain from the beginning.

(If you’re now thinking – but my GetFoo() function will now be slower! – you’re probably worrying about the wrong thing. Do you really have just ONE Foo? Why don’t you have a function that works on all the Foos?)

Let’s take a look at the venerable “system singleton” design. We have some global system we need to expose to clients. There’s only one of these. A lot of engine code will expose that as a singleton class, with all its state in the class declaration, with a lot of related classes and structs with inline functions.

If you want to change your internal state, you have to change the header, and needlessly recompile all client code.

A better way:

  • One header file with opaque types and function declarations only.
  • One or more private header files that expose data type details to implementation files.
  • One or more implementation files that define data structures and transforms on them.

Here’s what that can look like:

// Header file
namespace FooSystem {
  struct Frob;

  void Init(size_t max_frobs, Allocator* alloc);
  void Shutdown();

  void CreateFrobs(
       Frob** out_array,
       size_t count,
       const void* data, ...);

  void DestroyFrobs(Frob** frobs, size_t count);

  void UpdateFrobs(float delta);
  void RenderFrobs();
}

// Implementation file
struct FooSystem::Frob {
  // Members go here
  // -or- you might chose to make Frob just an
  //      integer handle to SOA
  //      state stored in the system instead
};

// Static "singleton" state of the system,
// named "S" for less typing.
static struct {
  // Space for frobs
  Frob *m_Pool;
  size_t m_PoolSize;
  // Whatever else you need
} S

void FrobSystem::Init(size_t max_frobs, Allocator* alloc)
{
  S.m_PoolSize = max_frobs;
  S.m_Pool = alloc->Alloc(sizeof(Frob) * max_frobs);
  // And so on
}

What does this buy us over the traditional “singleton class”?

  • You can change the system’s internal data types without recompiling client code – optimizing for turnaround on data design
  • It enforces entirely opaque types which cannot easily be tampered with (accidentally or not)
  • It minimizes surface area between systems and so makes debugging and trouble-shooting easier
  • It leads to a “more than one” thinking which is good for efficiency
  • It’s easier to make into a DLL/shared object, because client code doesn’t have to worry about the storage of the “system object” – if they can call the functions, the data is there too.
  • It’s possible to write in pure C as well, which is nice for compile speeds!
Advertisements

5 thoughts on “Optimize for Iteration Time

  1. Nice article. I’m very interested in seeing large codebase which is written using this style. Doom3 uses something similar, but I don’t think they use a lot of opaque types.

    I have a couple of questions on your design.

    1. How would you write auto tests / unit tests / integration tests for such opaque types ?

    I assume unit test can include “private” headers, but then you end up with 2 headers and 1 implementation file, which just makes code harder to navigate and potentially slows down compilation.

    Also, if you need multiple implementation files, then it probably makes sense to extract functionality into separate classes/structs.

    2. How would you extend opaque types ?

    Let’s say Frob is an engine core primitive, and game code wants to extend it to modify behaviour. How would you do it ?

    3. What if at some point you realise that you need more than one FooSystem. How would you adjust design to accommodate it ? Another namespace FooSystemSystem or make FooSystem a class ?

    4. Wouldn’t it be easier just to avoid global state or at least encapsulate it in one container which we can pass in functions ? Or use dependency injection when it’s applicable.

  2. Thanks,

    For unit testing, I don’t think it’s any different from unit testing anything else. I’m no UT expert, but the test shouldn’t depend on the internals of types, right? So it seems to me nothing is lost (except sizeof) by hiding them.

    Extending types can be done in a number of ways, but it can also be avoided completely by composing together other functionality. E.g. instead of having a class Rocket that inherits Renderable and PhysicsObject you have three independent pieces of data that sit with the other data structures in those respective subsystems. The “rocket” is three indices. Of course, nothing prevents you from adding padding to the end of a struct and storing whatever you want in there. It would be an opaque block of data the system manages, but you’d cast to your extended data type later. But I challenge the assumption that inheritance is needed before we get to that point.

    It’s easy to add a level of direction and create a “system object” behind an opaque type, so that’s not a huge deal. If you’re worried about that you could adopt this style throughout, and just return an opaque pointer to your static struct. When you need more than one, set up a proper allocator/init path that initializes your system objects.

    >> 4. Wouldn’t it be easier just to avoid global state or at least encapsulate it in one container which we can pass in functions ? Or use dependency injection when it’s applicable.

    I don’t know what could be easier than a block of memory managed for you by the linker. It’s the most convenient thing I know of 🙂 Everything else sounds like more work for very little gain.

    Global state has the advantage of optimizing for iteration time in another very important way: debugging. If I get a post-mortem crash dump I can instantly access the state of every subsystem in the watch simply by typing in a few well-known symbols. I don’t have to hunt down random pointers/containers to recover data.

    I don’t know what “dependency injection” is or how it would help here.

  3. This approach sounds very appealing to me as well. I’m just wondering about several things.

    First, say, I’d like my “rocket” to have custom rendering code. In order to achieve this the “rocket” instance will have to register itself in a rendering subsystem, keep the returned opaque system id and using this id register some sort of callback where the custom rendering logic will happen, right?

    Second, “It’s easy to add a level of direction and create a “system object” behind an opaque type, so that’s not a huge deal.” Could you please elaborate on this a bit more? A couple of lines written in some pseudo code would be really helpful 🙂

    Thanks

    • Instead of registering rockets with the renderer, why not have separate arrays of rockets with different properties? That way you can iterate the rockets that share particular properties and execute their custom rendering code in one go, instead of dispatching on each one.

      Re indirection – it’s possible to make the system object be instantiable if you want, by applying the same transform recursively. Just imagine that “Frob” in my example is “FrobSystem” and change functions to fit.

      • Regarding arrays of different rockets, it sounds very promising from the optimization point of view but still I can’t wrap my “encapsulation oriented” mind around this idea yet 🙂 And I really want to try it still not sure on where to begin. What if I have 10+ types of rockets which differ in very subtle ways with a lot of shared parts, e.g collision handling, etc… I’m just scared of possible code duplication and tedious book keeping.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s