Tips on writing code for Data-Oriented Design

(This article is a repost from my personal blog at https://marccgk.github.io)

I recently wrote about why I think Object Oriented Programming is not a good tool to write code.

In that post I wrote:

Object Oriented Programming is often taught and, therefore, learned, right after the basic programming constructs: variables, conditionals, loops, basic types and, in languages like C++, pointers and basic memory allocation / deallocation. Hence, most people have only approached medium to large codebases from an OOP lens. Although there are large codebases written in non OOP languages, e.g. the Linux Kernel, written in C, I’d argue most sizable codebases currently in development are built using Object Oriented Design (Not an empirical study, based on my experience working on C++ codebases).

In this blog post I’d like to present a different starting point to approach writing software. Obligatory caveat: this is not a one size fits all solution, nor it doesn’t pretend to be. Writing code is still a craft more than a science, so in my opinion, every “do this, don’t do that” advice should be paired with measurable pros and cons.

Having said that, I should also note that as a community, software developers don’t even agree on what characteristics make the list of advantages or disadvantages nor what priorities should be assigned to them.

Data-Oriented Design

I assume you’re familiar with Mike Acton’s Data-Oriented Design CppCon 2014 talk. If not, go watch it now, I’ll wait.

Data-Oriented Design (DOD) is a fundamental concept, understanding how the hardware works (at a high level) is a prerequisite to writing instructions for a computer to execute. However, DOD doesn’t tell you how to write code. In this conversation with Christer Ericson that Mike Acton made public, Christer explains why DOD is not a modeling approach:

What modeling approach should I follow, then?

I don’t know. I think different people will find that different modeling approaches work better or worse for them, and that is alright.

Personally, I just like to keep things simple, really simple, and build complexity only when 100% warranted. I’ve seen only too many clean up, refactor, simplify, and address technical debt tasks to understand that complex solutions in the name of some abstract goal (e.g. extensible, single responsibility principle, DRY, etc…) don’t work out in the end.

So, what does simple mean to me?

Simplicity

Simple means straightforward. Simple code is code that is easy to understand by itself, no knowledge of other code or foreign concepts needed.

This immediately rules out most of the C++ STL, like:

std::vector<int> v; // initialized somehow
int sum = std::accumulate(v.begin(), v.end(), 0);

This is not simple code, it’s just short. But short doesn’t make it simple. To understand this 2 line snippet you must be familiar with a lot of concepts: std::vector (more complex than arrays), iterators, STL algorithms, templates or generic metaprogamming, etc…

On the other hand, this is a lot easier to understand:

int* values; // initialized somehow
int valueCount;

int sum = 0;
for (int i = 0; i < valueCount; ++i) {
  sum += values[i];
}

This last snippet only requires basic programming concepts to be completely understood: variables, pointers, loops, etc…

Warranted complexity

There’s only so much that can be done with simple loops and accumulating values. With growing amounts of features and, therefore code, complexity will invariably materialize. However, striving for simplicity should always be on the front of your mind, fighting entropy and not giving in to the path of least resistance.

There are inherent complex problems, though, and they require complex solutions. One of such complex problems is extensibility, that is a way for the user to provide custom functionality to some software without modifying the source code. This problem justifies, and necessitates, a complex solution, e.g. a plugin architecture.

How do you translate that into a modeling approach?

As I said, this can adopt different forms for different people. I can only speak for myself, but what follows is what I’ve found to work for me and what I’ve learned from other people that take a similar approach to code.

Write straightforward code

Code is easier to understand when it’s written linearly, in a procedural way. That generally takes the form of long functions that do one thing conceptually, but might be composed of multiple sub-tasks to accomplish the main one. These sub-tasks are not extracted into their own standalone functions, though, until there’s a reason for it, that is, the code is already duplicated in 2 or 3 places and the commonality is large enough (i.e. 90%+) that the cognitive overhead of another function is superseded by its usefulness.

However, there’s also room for small functions. In contrast with large functions that implement main features, short functions tend to be helper functions that get called from the large ones and return immediately. Some examples of such functions are allocations (e.g. a temporary allocator might just bump a pointer), make/create functions, math libraries (e.g. vectors, matrices), etc…

Physically separating the code like this has several advantages both for the programmer and the compiler:

Solve the problems backwards

The purpose of all code is to transform data from one format to another (from Mike Acton’s Three Big Lies). Therefore, you know what the result of the transformation looks like. Working from the final format backwards, makes it easier to write the least amount of code to satisfy the transformation at every step.

For example, if you were to write a software rasterizer, you might want to start by allocating pixel memory for your window and clearing to a single pixel color. Then, change some areas of the image to the color you want, e.g. the corners. Then rasterize rectangles that are 100% within image bounds, later some rectangles that are not within bounds (clipping). After that, try rasterizing triangles. And only after rasterization in 2D works, start working on 3D geometry and projections, until you can load arbitrary 3D models and fully rasterize them.

This method will ensure you only write the solution to your immediate problem. The code will change a lot, but it will change as the problem itself evolves. The patterns and algorithms will emerge from the solution and not from some preconceived notion of what the solution should’ve been.

Simple memory allocation models

Memory management tends to get a very bad rap for being too hard for mere mortals, and programmers are recommended to stay away from it. That’s why one of the main features of high-level languages is automatic memory management by e.g. garbage collection, automatic reference counting or smart pointers.

Keeping in line with the simplicity principle, most memory allocations fall into simple models with just a small percentage being hard problems.

One such simple model are temporary allocations. A lot of algorithms need some sort of scratch memory to save intermediate results (e.g. merge sort). A temporary allocator is all that’s needed for these use cases:

struct Temp_Allocator {
  void *memory;
  U64 used, size;
};

struct Temp_Mem_Block {
  Temp_Allocator *allocator;
  U64 saved_used;
};

void *alloc(Temp_Allocator* allocator, U64 size, U64 alignment) {
  U8 *mem = ((U8 *)allocator->memory) + allocator->used;
  U8 *aligned = (U8 *)((((U64)mem) + alignment - 1) & ~(alignment - 1));
  U64 offset = aligned - mem;
  size += offset;

  assert(allocator->used + size <= allocator->size);
  allocator->used += size;

  return aligned;
}

Temp_Mem_Block begin_temp_alloc(Temp_Allocator* allocator) {
  struct Temp_Mem_Block result = { allocator, saved_used = allocator->used };
  return result;
}

void end_temp_alloc(Temp_Mem_Block block) {
  block.allocator->used = block.saved_used;
}

struct Temp_Allocator g_tmp;
void some_function(...) {
  struct Temp_Mem_Block tmp_mem = begin_temp_alloc(&g_tmp);
  // do work
  end_temp_alloc(tmp_mem);
}

Another very common use case is program state, for which a growing memory arena that allocates memory blocks would suffice. There are many different memory allocation strategies that can be applied to different problems but still, most allocations will fall into these simple patterns.

My advice would be to avoid new/delete and malloc/free for most allocations, and reserve them to allocate big memory blocks for the allocators/arenas to use.

The fact that memory management can be so much simpler than it is made up to be means that complex memory management strategies like smart pointers and garbage collection are rarely needed.

Avoid RAII

Resource Acquisition Is Initialization is widespread in most object-oriented code. It theoretically provides a lot of benefits to its users, but it also comes with a lot of complexity that spreads through the codebase.

Using RAII to acquire resources in class constructors and release them in class destructors in C++, forces another set of behaviors on the programmer on everything that interacts with that code:

Inheritance

I’ve found that there’s seldom need for inheritance the OOP way. There are 2 different simple solutions to inheritance that make the code easier to work with in several ways.

Discriminated unions

enum Command_Type {
  Command_Type_Add,
  Command_Type_Remove,
  // ...
};

struct Command_Add {
  // Add command data
}

struct Command_Remove {
  // Remove command data
}

struct Command {
  enum Command_Type type;
  // more common data

  union {
    Command_Add add;
    Command_Remove remove;
    // ...
  };
};

Some of the advantages of this method include:

Composition

Some times, though, it’s easier to use plain composition, e.g. different classes which have an explicit header as their first data member.

enum Command_Type {
  Command_Type_Add,
  Command_Type_Remove,
  // ...
};

struct Command_Header {
  enum Command_Type type;
  // more common data
};

struct Command_Add {
  struct Command_Header header;
  // Add command data
}

struct Command_Remove {
  struct Command_Header header;
  // Remove command data
}

The disadvantage of this approach is that it’s no longer possible to declare a plain array of Commands, so one needs to push the different commands to a raw memory buffer and later, when reading, grab the header, figure out the type and skip sizeof(Command_XYZ) to get to the next one. However, this works better when certain types need to be accompanied by a varying amount of data, e.g. a buffer of transforms, since the data can be stored immediately after the type itself and how many bytes to jump to the next type can be inferred from the data itself.

The trick here, is that because how memory layout works in C, we know that header in Command_Add will be at an offset of 0 bytes from the start of the struct:

U8 *cmd_mem; // filled somehow

Command_Header *header = cmd_mem;
while (header < /* array end */) {
  switch (header->type) {
    case Command_Type_Add: {
      Command_Add *cmd = (Command_Add *)header;
      header = (Command_Header *)(((U8 *)header) + sizeof(Command_Add)); // skip Command_Add
      // work with Command_Add
      break;
    }
    // more cases ...
  }
}

Arrays & Loops

Probably, the most common operation in software is to process lists of things. Keep data that is processed similarly together, i.e. in the same array, so critical code can have this form:

void transform(F32 *out, F32 *in, U64 count) {
  for (U64 idx = 0; idx < count; ++idx) {
    out[idx] = in[idx] * 3.f + 2.f;
  }
}

Multithreading

Multithreading is hard. As a general rule, I try to divide work in tasks that can operate as small single threaded programs, so the same function works in both single threaded and multithreaded cases. I also like keeping some data per thread, like a temporary memory allocator, which can be aggregated in a per-thread context.

struct Thread_Context {
  struct Temp_Allocator allocator;
  // other
};

void process_task(struct Thread_Context* ctx, U32* input, U32* output, U32 count) {
  struct Temp_Mem_Block tmp_mem = begin_temp_alloc(&ctx->allocator);
  U32* tmp = alloc(&ctx->allocator, sizeof(U32) * count, alignof(U32));
  sort_U32(input, tmp); // sort input using tmp as scratch memory

  // do some work
  for (U32 i = 0; i < count; ++i) {
    output[i] = operate(input[i]);
  }

  end_temp_alloc(tmp_mem);
}

// The job scheduler has a Thread_Context per thread, that passes to the task function

A more comprehensive view on multithreading is out of this article’s scope.

Be explicit

If there’s a common theme to all the ideas I’ve written about in this post it is be explicit. Being explicit is always preferable to being implicit.

I’m definitely not alone in making explicitness a priority, e.g. Our Machinery’s Guidebook Design Principles are also outlined along this same principle.

C++ and Language Features

All the code in this post, and previous posts is written in C, not in C++. The main reason is that C is a simpler language than C++, so I can focus on the basic building blocks.

Specially for beginners, I think it’s worth understanding the basic constructs, before jumping head first into language features that might derail your goals because of unforeseen trade-offs.

Closing

What I wrote in this post are guidelines for some modeling approaches that will generate code somewhat following a Data-Oriented Design. There is nothing new or revolutionary in this post, but I wanted to gather some thoughts and advice I’ve followed myself in a single place, for future reference. Take this as my drop in the ocean to try and make the path to better software easier for anyone who wants to try.

For a list of resources with similar ideas and more, please take a look at the end of my last post.