1
\$\begingroup\$

I have been reading many resources about data oriented programming, and one thing I understand about it is that it's about keeping chunks of memory together to improve performance. Other than that, I find it hard to understand. can someone tell me if this counts as DOP or if I am doing it all wrong?

I can't tell if my pseudocode counts as data-orientated programming:

// attempted non-OOP format since I am bored of standard OOP and trying C instead of C++,
// where object_ids is array of objects holding their type id's 

update() {
    for (int i=0;i<nObjects-1;i++) { // where i is the object id
        // get the update function for the type of object
        object_update_functions[object_ids[i]](i); 
    }
}

// example
void * object_update_functions[0](int id) { 
    // // object #0's update function 
    object_x[id] += 2;
}

I'm still unsure of how to use data-orientated programming, without object-orientated programming. Unfortunately, all of the examples I've seen of data-orientated programming still use class-based object-orientated programming.

As far as I know, back in the day of the NES, they didn't have object-orientated programming like they did, today. They had to store object variables in different arrays, consequently leading to better-performing, data-orientated code.

I want to avoid making the mistake of writing pseudo data-orientated programming, and not really getting the benefits of caching and modularity. How do I use data-orientated programming without object-orientated programming?

\$\endgroup\$
  • \$\begingroup\$ I'm slightly confused about what your actual question is. "DOP" and OOP are in no way incompatible; bad OOP is hard to code in a data-oriented fashion, but there are plenty of excellent ways to use OOP in highly-efficient code. \$\endgroup\$ – Sean Middleditch Jan 7 '17 at 23:29
5
\$\begingroup\$

Without really commenting on the whole mess that is "data oriented programming" versus "object oriented programming," (because largely those arguments get in the way of actually getting things done), the crux of your concern seems to be: is this code going to make efficient utilization of the cache?

Making efficient use of the memory cache is fairly straightforward at the high level: it means structuring your code so that if you touch some address, the next addresses you touch are near (ideally next to) the last address you just touched.

Typically this kind of code looks like "put a bunch of data in a big array, loop over that entire array and do something."

With that said, your code

for (int i=0;i<nObjects-1;i++) { // where i is the object id
    object_update_functions[object_ids[i]](i); // get the update function for the type of object
}

is not necessarily doing that. What you're doing is looping over an array of object IDs. If you were going to do something with each of those object IDs, that would probably be taking advantage of the contiguous nature of the object ID array. However, instead you use the ID to index into another array. This other array is (potentially) nowhere near object_ids in memory. In the worst-case scenario both arrays fit exactly into one cache line and every iteration of the loop causes a cache miss, because first the memory containing object_ids must be fetched to read object_ids[i], and then the memory for object_update_functions must be read in to index into that array.

Further, you're using the result of this indirection to simply call out to some other block of code, which may do who-knows-what. Generally you'd want to consider organizing your code so you do some operation F() on a bunch of data, and then some other operation G(). Not, as you are potentially doing, calling F() then G(), then K(), then F() again.


What you'll want to do instead is start thinking about organizing data in terms of the operations that might need it. The operation "update the position" needs a certain set of data: the current position, the velocity, the acceleration, maybe other things. Try to organize your data so that all the "position data" for all your objects is in a big, contiguous list. Then blast through that list updating the positions of everything.

Similarly if your next task is "update the shield and HP status of every object," then you'll want to similarly have every object's shield level and HP stuffed into a contiguous array, and blast through that.

You can have, somewhere, a mapping from object ID to the set of position properties, and object ID to the set of shield properties. But the key is that you'll want both of those sets of properties to be stored contiguously for their respective operations already. You don't want to have to indirect through the object ID table to get to them; you just have that functionality around for other places in the code where you don't need to be maximally cache-coherent.

Similarly, I'd venture to say your "update" function pointers are leading you into a trap and you probably don't need them. Your top level game update function (the one you call in your game loop directly) can just call these individual update operations directly. There's really no particular need to abstract them into function pointers:

void UpdateTheGame(float elapsedSeconds) {
  UpdateAllPositions(elapsedSeconds, positionDataArray);
  UpdateShieldStatus(elapsedSeconds, shieldDataArray);
}

where positionDataArray is an array of PositionData:

struct PositionData {
  float x, y, z;
  float vx, vy, vz; // velocity
};

and so on. This means your "game objects" might end up looking like:

struct GameObject {
  int positionDataIndex;
  int shieldDataIndex;
};

so that you can retrieve the relevant data for any individual game object if you need to. The point is you want to avoid having to follow the object to get the data during the important, cache-sensitive update of all that data if you can.

\$\endgroup\$
  • \$\begingroup\$ So would sorting them by type and having object_update_functions simply hold pointers to the update function for object #i be cache-efficient? Like just object_update_functions[i](i)? Or no? If not, I don't know what I should be doing instead. \$\endgroup\$ – Accumulator Jan 7 '17 at 23:41
  • \$\begingroup\$ Expanded my answer a bit; as I note at the end I think your idea of "update function" pointers are probably leading you down a path you don't want to go and you should get rid of them. \$\endgroup\$ – Josh Jan 7 '17 at 23:52
  • \$\begingroup\$ How else could I handle the... state updating of complex objects? The way I understand your edit is that you are saying it would work like a sort of queue instead of doing things immediately, but you would still need something that calls those functions, which normally is an "update" function. \$\endgroup\$ – Accumulator Jan 8 '17 at 0:03
  • \$\begingroup\$ You could put the functions into a queue, but even that I think is not worthwhile. Just call them directly. You want to get away from thinking about "what do I do with this object and with that object" and think more about "what do I with this kind of data (for all objects) and that kind of data." \$\endgroup\$ – Josh Jan 8 '17 at 0:26
  • \$\begingroup\$ + 1 for the great answer. Just one thing that could be misleading (but I think you say​ that just as example): you can have two (or few more) arrays at the same time, even if they're not near each other in memory, in the cache and so update, for example, the values of the first according to the ones in the second. That's usually what you want to do to make things interact. \$\endgroup\$ – Liuka May 15 '17 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.