Skip to content

Explaining Data Oriented Design


yin-yang-skyOne of the most common questions asked, upon first reading about Data Oriented Design, is “I don’t get it – how is this different from just Structures Of Arrays?”

I think it may help to draw a parallel with garbage collection, another fiercely debated topic. Sometimes programmers used to more abstract languages will complain about “having” to manually manage memory in non-garbage collected languages, implying the goal is writing code and managing memory is a chore which gets in the way of that.

They’re not wrong to think that, but you have to recognize that it’s not the only valid viewpoint.

You see, people working in games often see it the other way around. In some programs, managing memory is the goal, and the code is the chore which gets in the way.

Underneath all the high-level concepts we apply onto programming, all computers really do is move memory around. It’s not hard to see though how one could forget that. If you have a good debugger, you can see the memory underneath; a good memory window or disassembly view can show you things the way the computer sees them. Many languages and platforms though don’t have that luxury. The user, presented only with the user-facing inputs/outputs (the source code and an expression-based debugger), will be pushed towards the code-first viewpoint without realizing it, because they can’t see things the way the computer does.

Code and memory are like two sides of the same coin – the Yin and the Yang, perhaps. You need both.

Code-driven design is about trying to express in source-code form what you wish the computer to do – it’s a forward-based planning method. The motivation behind data-oriented design is to consider what the ultimate result you want is, and then work backwards to discover the best way to get those bytes in that place.

In OOP the code is king – everything is designed around your core ideas in a way that showcases them neatly. In DOD the code is simply an unfortunate artifact which we have to suffer while we tend to the real business of managing memory.

  • The OOP code will be cleaner, simpler. It’ll make more sense to read, and there might be less of it. It exists to encapsulate an idea in a way that both the human and computer can understand. The goal in OOP is to write good code.
  • The DOD code will be longer, messier, with odd little edges cases and weird intrinsics everywhere, because it wasn’t written to be code – it exists secondarily to the real goal. In DOD, the goal of writing code is not itself writing code – the code exists only as a byproduct of an underlying process.

Structures Of Arrays are simply a means to an end, but someone trained only to work with code sees them as just that – a means – because they only see it as another form of code, rather than the ‘end’. They’re comparing one house to another house, when what we’re really concerned with is bricks, not houses at all.

  • Given a particle system to write, the code-first designer think “Right, I need the idea of a particle, let’s make a class for that. Now what do I need to do to each particle? I need to first update its physics, then update its color, then render it. And I guess I need to then repeat all that for each particle, so I’ll store my particles in a list.”
  • The data-first designer thinks “Right, I need to fill this vertex buffer with the updated particles. Where should I pull that information from? I guess I need an array to store all the particles in, I can read everything from there. They’ll need position and color. Hmm, maybe those would be better split into two arrays.”

Jonction du tunnel sous la MancheIt’s the same process, just starting from different ends. One expresses the idea better, one gets it done better. Which of those is most important to you at any given time depends very much on what you’re working on.

Of course, like any large construction project, the best way to do it is often to work neither forwards nor backwards, but instead to work from both ends and hope to meet in the middle.



Learning, And Unlearning


I came across something that intrigued me while reading Eugene Wallingford’s excellent blog, Knowing And Doing. Eugene is an associate professor at the University of Northern Iowa, teaching Computer Science.

I’m Behind on Blogging About My Courses…
“Reflections on teaching Python in the intro for the first course for the first time. Short version: On balance, there are many positives, but wow, there is a lot of language there, and way too many resources.”

Now it’s often th… wait, what? Too many resources? That doesn’t seem right, does it? Surely the more resources students have to learn from, the easier it’ll be for them? Not necessarily, he explains:

“Thoughts on teaching Python stand out as especially trenchant even many months later. The intro course is so important, because it creates habits and mindsets in students that often long outlive the course. Teaching a large, powerful, popular programming language to beginners in the era of Google, Bing, and DuckDuckGo is a Sisyphean task. No matter how we try to guide the students’ introduction to language features, the Almighty Search Engine sits ever at the ready, delivering size and complexity when they really need simple answers.”

It’s certainly an interesting point. I’d always assumed that more equals better. Perhaps I was wrong.

minecraft_programmingWhen I browse the computing section of a bookstore now, every shelf seems to be filled with endless titles like “How To Make Minecraft Apps In Objective Swift For Dummies”. Shelf after shelf of every book saying the same thing, with any book daring to be different getting diminishing shelf space every year.

How much do beginners have to un-learn after going down these branches, before they can move forward again? The things you teach first stick for years later, and when the current in-vogue platform has long gone, the specific knowledge learnt for it will become useless. The principles however, carry forward.

Are we teaching specifics without principles?

I can’t help wonder how much damage we’re doing.


Leaving The Nest


usrWhen I was a kid, every home computer came with BASIC. You’d turn it on and there it would be, staring back at you – a BASIC prompt. It’d flash at you until you learnt how to answer it.

This wasn’t just some optional toy you could investigate if you wanted. In order to even do anything with your computer, you had to at least know the BASIC commands to load a program off tape and run it.

Those days are gone of course, no more than a dream remembered. Today’s computers come with a modern day BASIC: JavaScript.

The push for JavaScript as the universal platform worries me. Learning programming via BASIC was like learning to ride a bike. It was a set of training wheels, to prevent you from messing up whilst you got the hang of it.

As you gained experience, you’d start to feel the limitations of the language. It wasn’t fast enough, it wasn’t powerful enough, it wasn’t expressive enough. At which point it was time for the training wheels to come off.

All 8-bit BASICs let you escape them once you’d learnt enough. You could start to learn assembly language, and outgrow the sandbox that had been made for you. One call to a special command would release your machine code free from its BASIC cradle, and the full power of the computer became yours.

Computers don’t come with BASIC any more, the only language likely to be preinstalled is JavaScript. It’s ubiquitous, elegant, safe, and accessible. But unlike BASIC, the training wheels never come off.

We’re teaching the next generation in a way that prevents them from ever creating things we have not already created for them. You could never created Linux or WebGL in JavaScript, if it were not provided for you. You can write these things in languages like C++ or Go, but we have built no path leading there; no route from apprentice to master.

We hold in our hands the most important software platform ever made, yet we clip it’s wings to stop it leaving the nest. We need a better web platform to guide the next generation – not one that keeps you in, but one that lets you out.


ADDENDUM: Two days later(!) WebAssembly was announced. It certainly looks like a step in the right direction. Let’s hope it succeeds.


Latest Version Doesn’t Mean Best Version


iphoneI don’t like automatic updates. There’s this weird idea that an update is always better than what came before. And that if you don’t want the update, you’re some kind of crazy heretic. Surely you want the latest patches? You should update to the latest version! A̧ ̕new v̡e̸r͞sio͘n̨ ̀i̶s͘ r̢e̛l͠eas͠ed!̧ ̸You should͡ ͘upda͘te͝ ͜yo̕u҉ M̨͎͔̱̼̞U͏͓͉̹S̱͈̻T̴͕̮̗ ̙̮̀h̸̫̪a̵̺V̻̭̹͎E͔̘̝̩̤̲ ́T̼h̲̖͉̩̳̩̟E̝̤͎̻̱ͅ ̬͔̣̪̙̱̝Ṷ͖̹̝́p̹̺̝̭͖͓ͅz̛̗̟d̶A̷Te̗͇!͡!̴ ͔̣̙U͈̣̝P̨̖̺̩̦͓̠̭D̹͉̱̪͇̼̯A͍͇̪̦̟̥͚T͏̼͕͖E̠͇̲͖̪͓͡

But are updates always better? You only have to look at what happened to uTorrent to know that’s not true. For years uTorrent was one of the most popular BitTorrent clients, due to its elegance, simplicity and general no-bullshit attitude. The one day the software’s author sold it to another company, and ever since it got a little bit worse with every version. In-program adverts were added, and most hilariously it even started using your computer for a while to mine Bitcoins on.

This isn’t necessarily the end of the world though – after all, if you don’t like it, you can just re-install the older version instead, right? What worries me about the current trend of automatic drip-feed updates is that it’s becoming more common not to support the idea of picking what version you want to run. Newer has become implicitly better.


I think the biggest problem here is one of names. The world works better when things have a name. If you’ve ever read Design Patterns, one of the things they talk about is the importance of giving something a name:

Gamma, Helm, Johnson, Vlissides – Design Patterns
“The pattern name is a handle we can use to describe a design problem, its solutions, and consequences in a word or two. Naming a pattern immediately increases our design vocabulary. It lets us design at a higher level of abstraction. Having a vocabulary for patterns lets us talk about them with our colleagues, in our documentation, and even to ourselves. It makes it easier to think about designs and to communicate them and their trade-offs to others. Finding good names has been one of the hardest parts of developing our catalog.”

Naming something gives you power over it – this is a fairly common superstition historically, but there’s a ring of truth to it, and it applies here. If you ask “should I install KB234762784”, it doesn’t mean much. But if you ask “should I upgrade to Service Pack 2”, it gives you a term to work with; something you can share with others and use as a handle to grasp the subject.

Things need names, so you can assign praise and blame. Upgrading to “Build 9926” doesn’t mean much, but upgrading to “Windows 10” suddenly does.

With a name, the intangible becomes tangible.

Free-market updates

But why, you cry, would you ever want to not install the latest version? Surely if there’s something that broke in the latest version, the developer will fix it and issue an even newer version?

No, they won’t always. At least, not without pressure.

image7The best pressure we can apply is the free-market economy. A way to stand up and say no, I’m not upgrading to your new version because it sucks. Without that pressure, companies will sail onwards with their broken new version. But if people refuse to upgrade, they’re forced to rethink.

Here’s a case study for you. Everyone likes WinAmp, right? It’s probably one of the most downloaded programs of all time. The 2.95 release was for many the gold-standard of MP3 players.

In 2002 they rewrote large portions of the program and released a shiny new version, WinAmp 3. Everyone hated it. The lean, thin program everyone was used to suddenly found itself slow, bloated, with some previously working features removed entirely.

The backlash was strong, and users complained vocally. But complaining does no good. Instead they voted with their feet, as it were. Many people stayed on WinAmp 2.95, refusing to “upgrade” to the new version.

And it worked. A year later, NullSoft released WinAmp 5 – by going back to the 2.95 codebase and finding ways to merge the newer 3.0 features in, creating the best of both worlds. If it hadn’t been for the power of the users to choose, this may never have happened. And yet the result created a better product.

Then there’s our old friend, Windows 8. I’m not going to bitch about Windows 8 here, because it’s been done to death, so let’s just summarize with “a lot of people don’t like it”. So much so that many people, myself included, just decided to stick with Windows 7 instead until something better came along.

Microsoft even realized how much they messed up by needing to offer a free upgrade to Windows 10. I wonder how much of this was due to people voting with their wallet?

The power to choose which version of a program you run is just as important as choosing the program itself.


I’m not entirely sure revertability is a word, but screw it, it is now. Even if the latest version is generally an all-round improvement, are there reasons you might want to take a look at older versions? Steam is one of the worst offenders for updates. Once an update gets on your system, there’s no way back.

Remember Portal? Voted Game Of The Year 2008? Widely praised for its compelling storyline? voted it “Best Narrative 2007”. Everyone liked the ending.

Except now, if you play it on Steam, you’ll find you get a different ending than you did originally. Wait, what? Yep that’s right, Valve issued an update that replaced the old ending with a slightly different one to tie into Portal 2.

Now I’m not saying the new ending is bad, but if you want to play the version with the original ending, you can’t. That’s gone forever; there’s no way to select which build you want to play on Steam.

Get Windows 10

Now there’s a strong argument that hot-fix updates are essential for security, and I agree with that. Of course, while that’s true for someone running a server, for the user at home it may not be as important, but let’s skip over that for now.

So it makes sense that security fixes or critical bugfixes should maybe drip-feed directly. But it does assume you trust your provider to not abuse that privilege. Surely no-one would ever use the automatic update system to push non-critical fixes to you? Hah, right.

I can’t help notice as I write this the little “Get Windows 10” icon that greets me every morning. It just popped up on my desktop one day. I haven’t figured out how to get rid of it yet, I can try and hide it but it just comes back the next day.

I’m not saying we should get rid of the idea of drip-feed, always-latest updates, but we sure as hell shouldn’t be trying to use that model for everything. And yet that is where most distribution platforms are going.

  • Updates need to be named.
    You need to provide accountability, and give the user the power of discussion. Consider batching smaller improvements together into larger packs to get a better name for them.
  • Latest is not the same as best.
    If your users can’t go back to old versions, then you don’t allow them to vote. The best way to understand what your users really want is to let them show you, not tell you.

It can be scary to give users power to show you what they want, but if you let them do it you may end up with a better product as a result.


Warnock Subdivision for Deferred Lighting


I wanna talk about Warnock’s Algorithm today. Despite something that used to be fairly well-known, it seems to have fallen by the wayside a little nowadays. The algorithm was first described in 1969 by John Warnock. (In case you haven’t heard of him, he went on to start a small graphics company called Adobe).

The algorithm originally was designed for hidden-surface removal, which at the time was a big problem. Nowadays people tend to just use Z-buffers, and while that’s probably a good thing in terms of the original application, sometimes old things can be repurposed for newer problems.

It turns out the actual algorithm itself is much more interesting than simply sorting polygons – it’s a general-purpose technique for any situation where you have lots of 2D things and you want to either group or simplify them for processing.

So in order to demonstrate the algorithm, let’s pick a more modern use-case to look at.

Deferred Lighting

lighting_groupsIf you’re writing a deferred renderer, you get to a point where you need to draw your lights on-screen. Let’s assume we’ve already worked out the 2D screen bounding box of each light. All we need to do then is draw a quad which will then rasterize the light into the lighting buffer.

However, there’s a problem here. Each light has a certain amount of overhead – your shader has to read the Z-buffer value and reconstruct the 3D position. Then once you’ve done the actual lighting, you need to write and blend the color onto the lighting framebuffer.

All this overhead adds up, so what you really want to do is find a way to get a list of the lights that overlap on-screen, and group those together into batches. That way you only need to read the Z-buffer and reconstruct the position once for each screen pixel, and then share that cost across multiple lighting calculations.

Naughty Dog's tile-based approach

Naughty Dog’s tile-based approach

One way to do this is described by Naughty Dog, as part of their PS3 Uncharted engine. They split the screen into fixed-size tiles, and for each light they work out which tiles it overlaps. Each tile gets a list of all the lights that affect it, and can then process many of them at a time.

Now to be honest, that’s a pretty reasonable way to do it. It does have the disadvantage that you end up lighting more pixels than necessary, because your light will probably fall somewhere that isn’t aligned to tile boundaries. So you light a few more pixels than necessary.

Warnock subdivision can instead get a pixel-accurate list of the lights needed at any point. Depending on how many lights you have, and how big they are on-screen, one approach may be better than the other. You may find the Naughty Dog method works better for your game. Or perhaps the other way around. You could even find it’s better to not use rectangles for your lights.

I’m not claiming subdivision is the absolute best way to solve this problem for all use-cases.
But wouldn’t the world be a terribly boring place if there was only one way to do everything?

Warnock Subdivision

To explain the motivation I’ll quote from Warnock’s original paper, because it’s really quite interesting:

Warnock , 1969 – A hidden surface algorithm for computer-generated halftone pictures
The description of the philosophy is best given by describing the motivation behind it. Suppose I examine a picture of a table with pencils on it. I quickly determine that large areas on top of the table are open and therefore have little information content.

I scan over these areas searching out complex features such as a pencil. I dwell on a complex portion until I assimilate the information associated with it. From there I scan to other areas of the picture looking for additional complexity. In scanning the picture in this way I seem to spend little or no time on simple areas.

Complex areas seem to present themselves to me as subproblems requiring a solution. I seem to reduce these problems into further subproblems until I either solve the subproblem or don’t care anymore.

The 3 categories we need to consider.

The 3 categories we need to consider.

The idea of Warnock’s algorithm is, given a 2D rectangular window, and a list of things, to classify each thing into one of three categories:

  1. Things entirely outside the window.
  2. Things that are simple enough to deal with right here.
  3. Things that are complex enough that we can’t deal with them yet.

The things outside the window are obviously the easiest to handle – we just ignore them. For things that are simple, the exact meaning of “simple” depends on your particular application. In the original application (polygon rendering), simple meant “this polygon covers the entire window”. So in that case you could just fill the whole window with that polygon’s color.

The third case is the trickiest. The way Warnock’s algorithm deals with complex things is to recurse – we throw out the things outside the window, and try again with a smaller window. Eventually we’re guaranteed to get down to the level of a single pixel, at which point everything will fall into case 1 or 2 anyway.

Grouping Lights

So how do we apply this to deferred lighting? What we want is to split the screen into regions, where each region is assigned a list of lights that need to be rendered there. Once we have that list, we can render each region as a batch.

To get optimal results, we want to make sure that each output region does not have any light-edges within it. i.e. All lights in a region must fully cover that region.

So here’s the three classifications we need:

  1. The light’s rectangle is entirely outside the current window. (ignore)
  2. The light’s rectangle fully covers the current window. (simple)
  3. The light’s rectangle partially covers the current window. (complex)

We process each incoming rectangle in turn, and classify it into one of those three categories. After we’re done, we see if there are any partially-overlapping lights. If there are, we need to recurse with four smaller windows, and a smaller list that has the “outside” items removed. Otherwise, we now have a 2D window on screen and a list of all the lights that are relevant for that window, and we can do the rendering right there.

The only remaining question is when we recurse with a smaller window, how do we know where to split the window at? One option is to split the window exactly in half. This works fine, but isn’t optimal. We can do better by using one of the light’s edges to split along. So as we perform our classification, we keep an eye out for possible good edges to use later.

A note on storage

This algorithm runs entirely in-place on the list that’s passed in. There’s no need to call new or delete during the operation of it, which makes it very fast.

Although we need to track 3 different lists as we classify each rectangle, we don’t need to allocate any new lists. We can simple re-use the original storage, and swap items around within that storage. We track where the start and end of each list are as we classify them.

In his classic book “Dirty Pixels”, Jim Blinn refers to this technique as being a “triage table”, and describes how it can be used for many kinds of recursive algorithms. It’s well worth a read if you’re at all interested in graphics algorithms. (in fact, Blinn uses Warnock subdivision as a prime example, which is where I first read about it).

This does mean that the source list of rectangles gets rearranged during the course of the algorithm. This isn’t usually a problem as the list gets regenerated every frame by the game anyway.


There should be an interactive demo here. If you can’t see it… uh.. sorry. Browsers and all that.
Draw new rectangles out with the mouse. Hover over 2D regions to see which rectangles are needed for that region.

Your browser does not support the canvas tag.

Source code

You can download the entire C++ source code for the above demo here. If you find it useful, please let me know! I’ve listed the relevant core function below as well.