From C to C++ and back again.

in #gamedev7 years ago (edited)

As a kid I learned to program. Mainly in Basic and Z80 machine language. In university, I learned a wide range of new languages, of which the C programming language stuck the most.

After university, C++ started to become mainstream, and I jumped on that bandwagon. Embracing first Object Oriented Programming followed by fully embracing the Standard Template Library as well. Because doing O(1) hashmap look ups seemed so powerful. I did not fully appreciate the fact that it only makes sense for large N. And frankly, when programming games e.g, N is typically pretty small.

Creating a zoo of objects, all pointing to eachother is a surefire way of ending up with unmaintainable code. When I read Noel Llopis' article in Game Developer Magazine on Data Oriented Design, it resonated with me. As did Mike Acton's writings on these matters.

Ever since, I've been moving away from OO, away from C++, and back to C again.

I still use a C++ compiler so that I have my operators for vector math. But if the code does not require vector math, I always try to write it in straight C with plain old data types. It is amazing how clean your code ends up when you do that.

Because I use a C coding style, and also a Data Oriented style, I see myself repeating the following pattern in a lot of the code I write.

  • As Mike Actons says, if you have one of type X, there are often more of them. So group them.
  • I completely do away with all dynamic allocations.
  • Instead I ask myself: what is the worst case for the number of instances of that particular type.
  • Then I statically allocate for worst case, as Structure-of-Arrays data.

An example.

Let's say I am writing code (a module) for simulating spaceships. And my guestimate is that I will not be exceeding 1024 rockets. Then I will be defining my data like this:

#define MAXROCKETS 1024

static int numrockets;

static float rockets_mass[ MAXROCKETS ];
static float rockets_fuel[ MAXROCKETS ];
static float rockets_throttle[ MAXROCKETS ];
static mat44 rockets_transform[ MAXROCKETS ];
static vec3 rockets_vel[ MAXROCKETS ];


Then adding a rocket to the world would do something like this:

void rockets_add( mat44 m)
{
    assert( numrockets < MAXROCKETS );
    int i = numrockets++;
    rockets_mass[i] = 10.0f;
    rockets_fuel[i] = 500.0f;
    rockets_throttle[i] = 0.0f;
    rockets_transform[i] = m;
    rockets_vel[i] = vec3(0,0,0);
}


After calling rockets_add() there will be one additional rocket in the world.

When simulating the rockets, every step of the simulation loops over all rockets. So instead of "for-each-rocket, do all steps" we get: "for-each-step do for all rockets."

void rockets_simulate( float dt )
{
    // STEP1: burn fuel
    const float burnrate = 0.4f;
    for ( int i=0; i<numrockets; ++i )
        rockets_fuel[i] -= burnrate * rockets_throttle[i] * dt;

    // STEP2: accelerate rockets
    for ( int i=0; i<numrockets; ++i )
        ....
}


Because all of our code steps are iterating over the rockets, the SIMD units get a better chance on processing the rockets in parallel.

Now, if the module I am writing is a hot-spot in the profiler, and constitutes the bulk of the computation time, then I take the Structure-of-Arrays one step further.

I will no longer use C++ classes for vectors, but instead store positions as 1024 floats for x-coordinate, followed by 1024 floats for y-coordinate, followed by 1024 floats for z-coordinate.

E.g. particle simulation code will typically end up in this form.

static float rocket_posx[ MAXROCKETS ];
static float rocket_posy[ MAXROCKETS ];
static float rocket_posz[ MAXROCKETS ];

static float rocket_velx[ MAXROCKETS ];
static float rocket_vely[ MAXROCKETS ];
static float rocket_velz[ MAXROCKETS ];


Then if, for instance, I need to update the positions based on velocities, I would do:

void update_pos( float dt )
{
    for ( int i=0; i<numrockets; ++i )
        rockets_posx[ i ] += rockets_velx[ i ] * dt;
    for ( int i=0; i<numrockets; ++i )
        rockets_posy[ i ] += rockets_vely[ i ] * dt;
    for ( int i=0; i<numrockets; ++i )
        rockets_posz[ i ] += rockets_velz[ i ] * dt;
}

So yeah, I think it's not a bad idea to let go of all those C++ bells and whistles. Take a step back, and write SoA C style code.

Oh, and if you are afraid of those "dangerous" C pitfalls of unsafe memory: there is a fix for that. Just run your code through valgrind to catch those. Using fancy allocations, or worse, garbage collectors is just not worth it. In my code style there never is any garbage. No dynamic allocations, means no need for de-allocations. Removing a rocket from the world is just a numrockets-- statement.

The last thing I want to point out: note that I call it Structure-of-Arrays. Yet, there are no structures in my code. Only Arrays. In my coding style, I find that I can just statically declare all the arrays, and have no need to group them in a structure. You could, if you wanted too, of course. I just typically don't need it.

Sort:  

interesting story. i'm a follower now.