Data Structures Part 1: Bulk Data

Any programmer can benefit from some understanding of different data structures and how to analyze their performance. But in practice, I’ve never found any use for AVL treesred-black trees, tries, skip lists, etc. Some data structures I just use for one particular algorithm, and nothing else (e.g., heaps to implement the priority queue for A* search).

In most of my day-to-day work, I get by with surprisingly few data structures. What I mostly need is:

In the next few blog posts, I’ll show how I implement these things. Let’s start with the simplest and most useful one — bulk data.

Bulk Data

There is no good term for it that I’m aware of, but I use bulk data to mean any large collection of similar objects. It might be things like:

Or, if you are writing your code at a higher abstraction level, it might be things like:

Typically each system (rendering, sound, animation, physics, …) in the game has a couple of different types of objects that it needs to keep track of. For example, for a sound system it might be:

For the bulk data, I will assume that:

It is certainly possible to think of cases where order does matter. For example, if the objects represent renderable items we might want to sort them front-to-back before rendering to reduce overdraw.

However, in most cases, I think it is preferable to sort the data as it is being used, rather than storing the data in a sorted container, such as a red-black tree or B-tree. For example, we can sort our renderable objects front-to-back before passing them down to the renderer, or sort our files alphabetically before showing them in a list. It might seem expensive to sort the data every frame, but in many cases, we can do it in O(n) with a radix sort.

As for only using POD-structs, I prefer plain C structs to C++ objects, because it is easier to see what is going on in memory and reason about the performance implications. However, there are situations where you might want to store something in the bulk data that doesn’t have a fixed size, like a name or a list of child objects. I will discuss this in a future post when I talk about “arrays of arrays”. For now, let’s just assume that all objects are fixed-size PODs.

As an example, here’s what the bulk data structures for our hypothetical sound system might look like:

typedef struct {
    resource_t *resource;       // Resource manager data
    uint64_t bytes;             // Size of data
    uint64_t format;            // Data format identifier
} sound_resource_t;

typedef struct {
    sound_resource_t *resource; // Resource that's playing
    uint64_t samples_played;    // Number of samples played
    float volume;               // Volume of playing sound
} playing_sound_t;

typedef struct {
    playing_sound_t *sound;     // Faded sound
    float fade_from;            // Volume to fade from
    float fade_to;              // Volume to fade to
    double fade_from_ts;        // Time to start fade
    double fade_to_ts;          // Time to end fade
} playing_fade_t;

When thinking about how to store bulk data, we have a couple of goals: