Data Oriented Programming And Why it Matters (100x Speedup)

Programming
1

Consider the following scenario:

You have an array of several thousand objects in a game and only need to process the visible ones. Since visibility states update every frame, performance is crucial. What’s the fastest way to filter out invisible objects from your array?

First, let’s examine the naive implementation: You store all of the game objects in a vector, then iterate over it and remove the invisible ones. This may work; however, the runtime complexity is O(n2), as removing an element in a vector requires all elements in the array to shift over, which is, on average, linear time complexity, and you are iterating over the array n times.

Let’s look at our data and see if there’s a more efficient data structure for our needs:

struct Object {
    uint32_t size;
    uint32_t id; 
    bool visible;
    
    bool operator==(const Object& other) const {
        return id == other.id;
    }
};

Remember:

- Each object has a unique ID
- We don't need to maintain any particular order
- We need efficient removal operations

Here’s the solution:

Use an unordered set. Here’s why it’s perfect: it only stores unique elements (no duplicates) in no particular order, but more importantly, it has constant time complexity for look-ups, insertions, and deletions. This means that we can store the objects in an unordered set, iterate over it, and remove the invisible parts in O(n) time. With full compiler optimizations and 100k simulated objects, the set implementation took about 0.75ms while the vector took roughly 550ms. That’s 1300fps compared to 2fps.

Full code:

#include <iostream>
#include <vector>
#include <cstdint>
#include <chrono>
#include <unordered_set>

struct Object {
    uint32_t size;
    uint32_t id; 
    bool visible;
    
    bool operator==(const Object& other) const {
        return id == other.id;
    }
};

namespace std {
    template<>
    struct hash<Object> {
        size_t operator()(const Object& obj) const noexcept {
            return hash<int>()(obj.id); 
        }
    };
}


void remove_invisible_vector(std::vector<Object>& vectorArray) {
    const size_t n = vectorArray.size();
    
    for(size_t i = 0; i < n; ++i) {
        if(!vectorArray[i].visible) {
            vectorArray.erase(vectorArray.begin() + i);
            --i;
        }
    }
}

void remove_invisible_set(std::unordered_set<Object>& setArray) {
    auto itr = setArray.begin();
    
    while(itr != setArray.end()) {
        if(!itr->visible)
            itr = setArray.erase(itr);
        else
            ++itr;
    }
}

int main() {   
    const size_t objectsCount= 100000;
    std::vector<Object> vectorArray;
    vectorArray.reserve(objectsCount);
    
    std::unordered_set<Object> setArray;
    setArray.reserve(objectsCount);

    // create a large amount of random objects
    for(int i = 0; i < objectsCount; ++i) {
        Object obj;
        obj.size = rand() % (i+1);
        obj.id = i;
        obj.visible = (i & 1) != 0; 
        
        setArray.insert(obj);
        vectorArray.emplace_back(obj);
    }

  // measure vector
    auto time1 = std::chrono::high_resolution_clock::now();
    remove_invisible_vector(vectorArray);
    auto time2 = std::chrono::high_resolution_clock::now();
    
    std::chrono::duration<double, std::milli> milliseconds = time2 - time1;
    std::cout << "Time to remove all invisible objects from a vector: " << milliseconds.count() << " ms\n";
    
  // measure unordered_set
    time1 = std::chrono::high_resolution_clock::now();
    remove_invisible_set(setArray);
    time2 = std::chrono::high_resolution_clock::now();
    
    milliseconds = time2 - time1;
    std::cout << "Time to remove all invisible objects from a set: " << milliseconds.count() << " ms\n";
    
    return 0;
}

For further research, I highly recommend watching this video (which this post is based on): https://www.youtube.com/watch?v=WwkuAqObplU

3 Likes
2

nice post, i do wish the code explained more but for something decently simple like this - i understand why it doesnt

1 Like