Step-by-step: Programming incrementally

One thing that has really benefited my productivity (and also my general sanity), has been learning how to take a big task and break it down into smaller, more manageable steps. Big tasks can be frightening and overwhelming, but if I just keep working on the list of smaller tasks, then somehow, as if by magic, the big task gets completed.

Adding value

When programming, I take a very specific approach to this breakdown. I make sure that each step is something that compiles, runs, passes all the tests, and adds value to the codebase.Exactly what “adds value” means is purposefully left vague, but it can be things like adding a small feature, fixing a bug, or taking a step towards refactoring the code into better shape (i.e., reducing technical debt).

An example of not adding value is adding a new feature, but also introducing ten new bugs. It’s not clear that the value of the feature outweighs the cost of the bugs, so it might be a net loss.

Another example of not adding value is making the UI prettier, but also make the app run ten times slower. Again, it’s not clear that the prettier look is worth the performance hit, so it might be a net loss.

Of course, I can’t always be sure that I’m not introducing bugs, and “value” is inherently subjective (how much performance is a new feature worth). The important part is the intention. My intention is to always add value with every single commit.

Basically, what I want to avoid is the “It has to get worse before it gets better”-attitude. Also known as: “The new system is the modern way to do it. Sure, it has some bugs and runs kind of slow right now, but once we’ve fixed that, it’s going to be way better than what we had before.” I’ve seen too many cases where these supposed fixes never happen and the new system, which was supposed to be better, just made things worse.

Plus, you know, it feels good to add value. If every day I can make a commit and that commit makes the engine better in some way, that makes me happy.

Pushing to master

In addition to implementing changes through a series of small commits, I also push every one of those small commits back to the master branch.

Note that this is the exact opposite of a feature branch workflow, instead, it is a form of trunk-based development:

Trunk-based vs feature branch development.

Proponents of the feature branch approach claim that it is a safer way to work since changes to the feature branch don’t disrupt the master and cause bugs. Personally, I think this safety is illusory. Bugs in the feature branch just get hidden until it’s merged back to master when we suddenly get all the bugs.

Feature branches also go against my philosophy that every commit should add value. The whole idea behind a feature branch is: “we’re going to break a bunch of shit over here, but don’t worry, we’ll fix it before we merge back to master”. Better not to break stuff in the first place.

Here are some other advantages I see with the trunk-based approach:

The main challenge of the trunk-based approach is how to break a big task down into individual pieces. Especially, with the requirement that each piece should compile, run, add value, and be ready to be pushed into master. How can we push partial work without exposing users to half-baked, not yet fully working features?

Let’s look at some problems and how to solve them.

Problem #1: New features

An approach that works well for new features is to use a flag to control whether a feature is visible to end-users or not.

Let’s look at an example. A feature that I recently added to the engine was a Download tab that lets the users download new engine versions and sample projects from within the engine itself:

Download tab.

There are lots of different ways this could be broken down into smaller steps. Here’s an example:

Normally, I don’t do a full breakdown like this upfront. Instead, I just kind of figure out the next logical step as I go along. I only sit down and do a serious planning session if the task is particularly tricky and incremental steps like this don’t come naturally.

To prevent end-users from seeing the tab before it’s actually working, I hide it behind a flag. This can be as simple as:

const bool download_tab_enabled = false;

// ...

if (download_tab_enabled) {
    add_menu_item(tabs, "Download", open_download_tab);
}

To get the menu option to show the Download tab, you have to change the download_tab_enabled flag to true and recompile.

We call these flags feature flags since they selectively enable or disable individual features of the application. Once the feature is complete, we can remove the flag and just leave the true code path.

There are three main ways of implementing a feature flag:

Out of these options, I think the third one is the best. You want to expose your new code to as many people as possible. That way, they can find bugs in your code, if they refactor the codebase, they take your code into account, etc.

If you use a #define flag, other people on your team won’t even compile your code. Thus, one of their changes could easily end up breaking your code. A const flag is better, because your code will still be compiled, but since people can’t try the new feature without recompiling your code, most people won’t bother.

With a dynamic flag, artists, producers, or end-users who don’t want to be bothered with rebuilding the application can just modify the config file and then give your new feature a test run.

When the time comes to release a feature, you simply flip the default value of the feature flag from false to true and everybody will see the new feature. If there are issues and you need to revert, you simply flip the flag back. Later, when the feature seems stable, you can get rid of the flag and just keep the true path in the code.

You can even do a partial, staged rollout. E.g., you could set the flag to true for 1 % of the users and then slowly ramp that up while monitoring the crash logs and the forums for any issues. That way, if a problem is encountered, it will only affect a small number of users and you can quickly revert.

Problem #2: Rewrites

The above approach works well for new features, but what should you do if you are doing a major rewrite of an existing system?

In this case, it might be trickier to find an incremental step-by-step approach, because you might want to rip out large parts of the old system and it will take a while until the replacement code reaches feature parity.

It might be tempting to reach for the feature branch approach in this case, but again, I don’t think it’s the right strategy. A big problem is you will have two conflicting goals. On the one hand, you want to merge early so that people see the improved code and you get some testing on the rewrites. On the other hand, you want to delay it as long as possible, so that you can reach feature parity and iron out all the bugs. What usually happens is an unsatisfying mix of the two.

A better approach is to make a parallel implementation and let the engine have two copies of the same system.

If you are doing a major overhaul, you could start by just copying the entire system code to a new folder. If you are rewriting from the ground up, you could start with an empty folder.

Depending on the nature of the system you are replacing, you could either have both systems (the old and the new one) running in parallel, or you could have a feature flag that selects which of the systems should be the default. For example, if you are rewriting the physics simulation, you probably need a flag to select if you are using the old or the new one since you want all physics objects to live in the same simulation (otherwise they won’t interact). On the other hand, if you are rewriting the particle effect system, you could potentially have both systems running and just select for each played effect whether it should play in the old or the new system.

Having parallel implementations lets you do a much smoother transition from the old to the new system. Everyone on the team can easily test out the new system. You can compare it to the old one for feature completeness, stability, performance, etc. If applicable, you could even run automated tests to verify that the new system produces the exact same output as the old one. Once the new system has been thoroughly verified, you can change the flag and start using it as the default.

The parallel implementations also provide a much gentler upgrade path for end-users. Instead of tying everyone to the same “merge date”, you can just expose the system selection flag to the end-users. Users who are eager to try out the improved features in the new system can turn the flag on early, while users who favor stability or depend on certain quirks in the old system can decide to stay on it, even after the new one has become the default.

And there is no immediate rush to retire the old system once the new one has become the default, you can eventually deprecate and phase it out once the burden of maintaining it outweighs the value of having it around.

Problem #3: Refactoring

For our final problem, let’s consider something even trickier — making a big refactoring change to the entire codebase. It could be things like:

The challenge with refactors like this is that:

In some cases, it can be pretty straightforward how to approach the problem incrementally. For example, when we add a new warning such as -Wshadow, the fixes we do in order to make the code compile with the warning do not cause any problems when compiling the code without the warning. So we can simply turn on the warning, fix a bunch of the errors we get (however many makes a suitably sized commit), turn the warning off again, and then commit the result. Rinse and repeat until all the warnings are fixed and then do a final commit that turns the -Wshadow flag on for everybody.

In other cases, we can employ the parallel implementation strategy. Suppose we have a function that is used all over the code to allocate memory:

void *mem_alloc(uint64_t bytes);

Now we want to add a system parameter so that all memory allocations can be tagged as belonging to a particular system (gameplay, graphics, sound, animation, etc):

void *mem_alloc(uint64_t bytes, enum system sys);

If we just added the parameter like this, the code wouldn’t compile until we fixed all the call sites. I.e., the incremental approach would not work.

What we can do instead is introduce a new parallel function:

void *mem_alloc(uint64_t bytes);
void *mem_alloc_new(uint64_t bytes, enum system sys);

Now we can incrementally transition all of the code to use mem_alloc_new() instead of mem_alloc(). Once we have transitioned all of the code, we can remove mem_alloc() and then do a global search-and-replace that renames mem_alloc_new() → mem_alloc().

The final challenge is the trickiest one of them all — changing one of the fundamental types in the codebase.

In fact, I recently had a run-in with this, which is what prompted me to write this whole blog post. In my case, I wanted to refactor our codebase to introduce a new type to represent the IDs of objects in The Truth. The Truth is our main data store in The Machinery. All the data that the editor works on is stored in The Truth, and every object in The Truth is referenced by its ID.

We used to represent Truth IDs with just an uint64_t, but since we have lots of other values that are also represented by uint64_ts this was causing increasing confusion. In order to provide better documentation of where a Truth ID is expected and some type-safety against passing other uint64_t values, we decided to switch from using a plain uint64_t to wrapping it in a struct:

typedef struct tm_tt_id_t {
    uint64_t u64;
} tm_id_tt_t;

Note that since Truth IDs are used everywhere, this change impacts thousands of lines in the code.

Somewhat arrogantly, I still set out to do this refactor as a single concentrated push. I know I should do things incrementally, that’s what this whole blog post is about, but sometimes I mess up.

As I worked on it, I realized this change was a lot bigger than I had originally thought and there was no way I was going to be able to finish it in a single sitting. I started to get that sinking feeling that things were spiraling out of control. I was changing thousands of lines of code. Was I really sure that I wasn’t introducing typos anywhere?

A lot of the changes were changing things like:

if (!object_a) {

into:

if (!object_a.u64) {

Was I really 100 % sure that I wasn’t sometimes typing:

if (object_a.u64) {

instead? Running some tests would have increased my confidence, but since the code wouldn’t compile until I had fixed everything, I couldn’t run any tests.

Then I started to get merge conflicts with other people’s changes which I had to resolve by hand, hoping that I understood their code well enough not to break anything. It became harder and harder to picture the consequences of all the changes. How many bugs was I introducing?

In the past, I’ve often tried to deal with these “panicky” feelings by “powering through”. Starting to pull long late-night coding sessions to try to wrestle this thing that is slipping away from me back under control. Get all my changes in before someone else has a chance to push anything so that I don’t have to deal with the merge conflicts. (Which of course just means that they have to deal with the merge conflicts instead. Ha ha!)

But these days I’m maybe a little bit wiser? I realize that these feelings are a sign that I have bitten off more than I could chew and that the right response is not to push forward, but instead take a step back, reflect and try to reformulate the problem so it can be approached in a series of smaller steps instead. Depending on how much trouble I’ve gotten myself into, I might be able to salvage some of the changes or I might just throw it all away and start over with an iterative approach. Even when I’ve had to throw everything away, I’ve never regretted it. In the end, working in a series of small, controlled steps is so much more productive that I feel like I always gained back the time I “lost”.

Back to the problem at hand. I knew I wanted to change the type incrementally. I.e., change it in some files, but not in others, and still be able to compile and test the code. But how could I possibly do that, when everything depends on everything else? Once I change some parameters to use tm_tt_id_t, anything that calls it with uint64_t will produce an error.

My key insight was that this situation is very similar to the one of enabling -Wshadow. That transition was easy to do because we changed the code from compiling just under -Wno-shadow so that it compiles under both -Wshadow and -Wno-shadow. We can do this change incrementally until we’re finally ready to turn on -Wshadow.

Let’s do the same thing here. We’ll call the type of the ID objects ID_TYPE. Right now, our code compiles when ID_TYPE is uint64_t. Our goal is to rewrite that code so that it compiles both when ID_TYPE is uint64_t and when it is tm_tt_id_t. If we can incrementally transition to that state, then once all the code compiles when ID_TYPE is tm_tt_id_t we can make that the default.

Here’s a simple example to show how this works:

uint64_t get_data(uint64_t asset)
{
    const tm_the_truth_object_o *asset_r = tm_tt_read(tt, asset);
    uint64_t data = api->get_subobject(tt, asset_r, TM_TT_PROP__ASSET__OBJECT);
    return data;
}

To make this independent of the value of ID_TYPE, we can rewrite it as:

ID_TYPE get_data(ID_TYPE asset)
{
    const tm_the_truth_object_o *asset_r = tm_tt_read(tt, asset);
    ID_TYPE data = api->get_subobject(tt, asset_r, TM_TT_PROP__ASSET__OBJECT);
    return data;
}

This works regardless of whether ID_TYPE is uint64_t or tm_tt_id_t. In our header file, we put something like this:

typedef struct tm_tt_id_t {
    uint64_t u64;
} tm_tt_id_t;

#define TM_NEW_ID_TYPE 0

#if TM_NEW_ID_TYPE
    typedef tm_tt_id_t ID_TYPE;
#else
    typedef uint64_t ID_TYPE;
#endif

We can now commit and push our get_data() function without needing to change anything else in the code. Everything will still compile because ID_TYPE is by default defined as uint64_t, so all the places that call get_data() with an uint64_t will still work. We’ve taken a small, incremental step towards switching out the ID type.

To take another step, just as we did with -Wshadow, we set TM_NEW_ID_TYPE=1 locally. This will produce thousands of errors, but we don’t have to fix them all at once. We just fix a few (whatever is a suitable commit chunk) by modifying the code just as we did with get_data(). Then we change TM_NEW_ID_TYPE back to 0 and check that everything still compiles and runs OK. If it does, we can commit those changes. Rinse and repeat until the whole codebase is fixed.

There might be some situations where just changing uint64_t to ID_TYPE doesn’t work. For example, there is some code in the codebase that looks like this:

bool objects_equal(uint64_t a, uint64_t b)
{
    return a == b;
}

Since we are writing strict C code, we can’t implement operator== for tm_tt_id_t. We need to compare the objects with:

return a.u64 == b.u64;

(Side note: I often wish that == would work on C structs. The compiler should determine whether the struct contains any padding bytes. If not, == should be implemented as memcmp, otherwise, as a member-by-member comparison.)

Again, our goal is to replace the old code with new code that compiles for both possible values of ID_TYPE. This means we can’t just write a.u64, because that won’t compile when a is an uint64_t. But we can make use of the preprocessor once again and write something like this:

#if TM_NEW_ID_TYPE
    #define TO_U64(x) ((x).u64)
#else
    #define TO_U64(x) (x)
#endif

Here, the TO_U64 macro will produce an uint64_t from an ID_TYPE object, regardless of whether the ID_TYPE is wrapped or not. Now, we can rewrite the objects_equal() function as:

bool objects_equal(ID_TYPE a, ID_TYPE b)
{
    return TO_U64(a) == TO_U64(b);
}

And the code will compile with both the new ID type and the old one.

There are other ways of doing this too. For example, instead of TO_U64(x), we could have created an ID_EQUAL(a,b) macro.

The main point is that by making use of the preprocessor, it should be possible to take whatever code we have and rewrite it in such a way that it compiles with both possible values for TM_NEW_ID_TYPE. Once we can do that, we can incrementally transition more and more code to the new type.

Once the whole code is converted we can disable the TM_NEW_ID_TYPE=0 code path and then (incrementally, if we so desire) remove all the transitional macros, ID_TYPE, TO_U64, etc by replacing them with their TM_NEW_ID_TYPE=1 values.

Using this approach, I was able to completely transition over from uint64_t to tm_tt_id_t with 10-15 incremental commits over a couple of days, while all the time compiling and testing to make sure nothing was broken by the changes. Commits from other team members didn’t cause many merge issues, because my commits were all short-lived (an hour or so of work) and didn’t touch that many files. This big and scary change was suddenly very manageable.

Conclusions

I think the incremental pattern can be applied everywhere. It just requires a little bit of ingenuity to reformulate the problem in an incremental way and this is something that you get better at with practice.

Doing things incrementally has a bit more overhead. For example, we weren’t able to change object to object.u64 in one go, we had to transition via TO_U64(object). However, I think that extra time is soon earned back. By working incrementally you can make calm, steady, confident progress towards your goal, and in the end that allows you to work a lot faster. For example, with the ID type change, I was able to make a lot of changes using global search-and-replace with regular expressions. If I hadn’t been able to regularly compile and test my code, it would have been a lot harder to trust that the search-and-replace was doing the right thing.

Also, the C preprocessor is kind of a weird thing to have in the language, but sometimes it’s really neat that it’s there, when you need to do stuff like this.