Data Oriented Design, if done right, can produce very cpu-friendly code. It's easier to fit the relevant data into the L2/L3 cache, improve branch prediction and avoid cache misses, and also for the compiler to implement SIMD instructions.
Knowing how to store and read 2d arrays in 1d format is the single most useful thing in graphics programming from my experience. It's fast, efficient and so many engines already use these kind of arrays (eg. in vertex buffers, or frame buffers). I remember writing 100% software rasterizer and that was my go-to representation for framebuffer. As for OOP vs DOP: so many beginners try to use OOP in game programming, where it brings more harm than good, just because programming schools and courses focus too heavily on it. It has its usefulness, but the performance overhead can sometimes be a detriment. Not everything needs to be a separate object :)
To add, if we remember arrays are basically just pointers, grid[3][4] is not one contiguous chunk of memory but just a list of pointers to the arrays containing the real data. If you flatten the 2D array, it's guaranteed to be contiguous and there's only one pointer to the head involved, so every action in the grid only involves a looking at the offset from the head. Not the double jump in [x][y].
@@zytr0x108 This was 9 months ago. It does look like I did say something wrong - that multidimensional arrays in C aren't contiguous, they are. A nested vector in C++ is not, especially since they can be moved if they grow. I'd have to test a std::array, it's not a normal object, it's basically a C array with a simple wrapper. But I'm not sure if it nests. If you want to process all the cells in a grid, you might do something like for (int r = 0; r < num_rows; ++r) { for (int c = 0; r < num_cols; ++c) { grid[r][c] =... }} This means go to the address "grid", then move over "r * sizeof(grid[0])", then over "c * sizeof(grid[r][0])". Then at the end of the row, we go back the beginning of the next row, creating non-contiguous memory access (which is probably what I meant to say in the comment). If you process data as a 1D row or in vectors (not C++ vectors but vectorized instructions on CPU or GPU), that memory access can be a lot faster.
Awesome demonstration. I've always had the suspicion that OOP was kinda fluffy academic language stuff and was never really tested for performance. Makes me think about how much better a lot of software could be were it not written according to programming paradigms that ignore the memory layout of the computer.
OOP is not some kinda fluffy academic language stuff. OOP is not the problem. It is only a design pattern (or whatever you want o all it) created to solve certain type of problems. Just like DOD or anything else. The problem are the people that use one unique tool for all problems. This either shows their ignorance or shows them using programming as it it was some ideology or to ego prancing. If you want to blame the academy then blame those academics (only a certain part of the whole) that were more evangelic fanatics instead of engineers. There are many of those everywhere and it is not only in the academics and not only for OOP.
Nice video! There was always something misterious about DOD for me because of me not finding many examples, atleast not as clear as this one. I started making a project thinking on "DOD mode" but now i see that i failed completly, anyway, gonna refactor all that. Another thing, i understand that DOD it's more efficient because it maps better the data for the cpu right? Most of what i reed or watched was really more oriented to low level languages and how the cpu had a better time with it, but seeing something like this in python it's really interesting, and shows me how impactful it can be independent of the language (ngl i would be the kind of guy that makes fun of python for being slow, now my mouth is shut)
Great video! Super clear and helpful explanation of the difference between the two paradigms. Do you have a sense for how much of the speedup is due more to numpy handling a lot of the calculation and memory management vs. a more objective measure of the two algorithms' efficiency. Not sure how much pure python you were using in the version at the beginning of the video, but that could explain a lot of the difference depending. Regardless it's a great example of how to use numpy to good effect if you're writing anything in Python that can be expressed as numerical data.
Thanks! I'm not sure what's meant by "a more objective of the two algorithms' efficiency", as data oriented design is meant to take cache lines into account, this isn't a factor in traditional algorithm analysis anyway. Nonetheless I understand your point, I'm currently working on a higher level example to compare. Regarding the issue of "Yeah but this is just numpy", my perspective would be: then use numpy! It runs in python and basically does lists faster (since it stores the data directly in memory without layers of pointer indirection). Even using regular numpy without compilation I got a 10x speedup, which is encouraging. Now the question of whether there's anything in python which can't be expressed in numerical data is sort of philosophical. I'd argue it's always possible to recast a problem as purely numerical. Even callback functions can be indexed as arrays of function references. Just my opinion though.
I'm truly perplexed how this affected performance in any direction except negatively... please help :) What was described on paper, putting every single cube and transformation into a single class of multiple arrays, shouldn't be any different from having each in an array in a different class - the objects of that class should still be references to their components, with each pointer still being O(1) since there are no list traversals, and each object in the heap would be stored contiguously. And given the size of the arrays we'd expect from all transformations, unless we preallocate a HUGE amount of memory space, we're still going to be hindered (speed and cache misses) by the single virtual memory space being separated throughout the core. If, instead, you're truly creating a single OBJECT with all of the cubes and transformations in a single set of arrays, I'd expect the still constant time calculation of the indices for lookup to be at least twice as computationally intensive as pointing directly to them. Not to mention - if this is all a single array - what this would do to insertion and removal times! Even implementing with a search tree instead of an array should still be slower, if I'm understanding this correctly (which I am clearly not :D) Is this just a python thing, to trick the interpreter into doing what you want? I've never done graphics programming, and I know nothing about how Python works under the hood... someone please explain what I'm getting wrong here :)
So, per usual, I should have just watched the full video before commenting... but my questions are still somewhat relevant (maybe?). It seems your implementation makes perfect sense here, since you're using a small, set number of cubes with a set number of transformations mapped 1:1. I'm curious if this 1) scales with thousands of objects, and/or 2) remains efficient with frequent additions/removals?
I don’t remember exactly what implementation I went with here, from memory this should scale decently for more objects but needs some modification to actually be useful within a more complicated system. There will be certain thresholds at which one approach beats another. Currently I’m going with an ordered array and binary search lookup for my engines, but this is prefaced on the idea that I’ll be searching data a lot more than adding/deleting. Beyond a certain size a hashmap would probably perform better.
Wouldn't it be easier to read/handle if the fields that are used often together be in a struct instead of in multiple arrays? I understand that by exploding everything, it's easier to just pick and choose what data you need, but I'm concerned about the performance if you have to handle multiple huge arrays in a tight loop.
Data Oriented Design, if done right, can produce very cpu-friendly code. It's easier to fit the relevant data into the L2/L3 cache, improve branch prediction and avoid cache misses, and also for the compiler to implement SIMD instructions.
And the holy grail (at least in my opinion), batch up jobs so compute shaders can handle updates etc.
Knowing how to store and read 2d arrays in 1d format is the single most useful thing in graphics programming from my experience. It's fast, efficient and so many engines already use these kind of arrays (eg. in vertex buffers, or frame buffers). I remember writing 100% software rasterizer and that was my go-to representation for framebuffer. As for OOP vs DOP: so many beginners try to use OOP in game programming, where it brings more harm than good, just because programming schools and courses focus too heavily on it. It has its usefulness, but the performance overhead can sometimes be a detriment. Not everything needs to be a separate object :)
To add, if we remember arrays are basically just pointers, grid[3][4] is not one contiguous chunk of memory but just a list of pointers to the arrays containing the real data. If you flatten the 2D array, it's guaranteed to be contiguous and there's only one pointer to the head involved, so every action in the grid only involves a looking at the offset from the head. Not the double jump in [x][y].
it also is easier to copy around, since you copy the whole data block and don't have to copy each subtable separately@@asongfromunderthefloorboards
@@asongfromunderthefloorboards ohhhh thanks
@@asongfromunderthefloorboardsIsn’t that just syntactic sugar though? As far as I know they are still stored as a 1D array.
@@zytr0x108 This was 9 months ago. It does look like I did say something wrong - that multidimensional arrays in C aren't contiguous, they are. A nested vector in C++ is not, especially since they can be moved if they grow. I'd have to test a std::array, it's not a normal object, it's basically a C array with a simple wrapper. But I'm not sure if it nests.
If you want to process all the cells in a grid, you might do something like
for (int r = 0; r < num_rows; ++r) {
for (int c = 0; r < num_cols; ++c) {
grid[r][c] =...
}}
This means go to the address "grid", then move over "r * sizeof(grid[0])", then over "c * sizeof(grid[r][0])". Then at the end of the row, we go back the beginning of the next row, creating non-contiguous memory access (which is probably what I meant to say in the comment).
If you process data as a 1D row or in vectors (not C++ vectors but vectorized instructions on CPU or GPU), that memory access can be a lot faster.
Awesome demonstration. I've always had the suspicion that OOP was kinda fluffy academic language stuff and was never really tested for performance. Makes me think about how much better a lot of software could be were it not written according to programming paradigms that ignore the memory layout of the computer.
Agreed, especially python. Those pointer accesses are super expensive.
OOP is great for standard business software where readability and adaptability are the most important parts.
Performance sensitive work, not at all
OOP is not some kinda fluffy academic language stuff. OOP is not the problem. It is only a design pattern (or whatever you want o all it) created to solve certain type of problems. Just like DOD or anything else.
The problem are the people that use one unique tool for all problems. This either shows their ignorance or shows them using programming as it it was some ideology or to ego prancing.
If you want to blame the academy then blame those academics (only a certain part of the whole) that were more evangelic fanatics instead of engineers. There are many of those everywhere and it is not only in the academics and not only for OOP.
That was a brilliant explanation! Thank you!
Nice video! There was always something misterious about DOD for me because of me not finding many examples, atleast not as clear as this one. I started making a project thinking on "DOD mode" but now i see that i failed completly, anyway, gonna refactor all that. Another thing, i understand that DOD it's more efficient because it maps better the data for the cpu right? Most of what i reed or watched was really more oriented to low level languages and how the cpu had a better time with it, but seeing something like this in python it's really interesting, and shows me how impactful it can be independent of the language (ngl i would be the kind of guy that makes fun of python for being slow, now my mouth is shut)
Clearly no one told python it was meant to be a slow language 🤣
Wow!
Great video!
Good stuff, actually understood what this buzzword was about.
Great video! Super clear and helpful explanation of the difference between the two paradigms. Do you have a sense for how much of the speedup is due more to numpy handling a lot of the calculation and memory management vs. a more objective measure of the two algorithms' efficiency. Not sure how much pure python you were using in the version at the beginning of the video, but that could explain a lot of the difference depending.
Regardless it's a great example of how to use numpy to good effect if you're writing anything in Python that can be expressed as numerical data.
Thanks!
I'm not sure what's meant by "a more objective of the two algorithms' efficiency", as data oriented design is meant to take cache lines into account, this isn't a factor in traditional algorithm analysis anyway. Nonetheless I understand your point, I'm currently working on a higher level example to compare.
Regarding the issue of "Yeah but this is just numpy", my perspective would be: then use numpy! It runs in python and basically does lists faster (since it stores the data directly in memory without layers of pointer indirection). Even using regular numpy without compilation I got a 10x speedup, which is encouraging. Now the question of whether there's anything in python which can't be expressed in numerical data is sort of philosophical. I'd argue it's always possible to recast a problem as purely numerical. Even callback functions can be indexed as arrays of function references. Just my opinion though.
I'm truly perplexed how this affected performance in any direction except negatively... please help :)
What was described on paper, putting every single cube and transformation into a single class of multiple arrays, shouldn't be any different from having each in an array in a different class - the objects of that class should still be references to their components, with each pointer still being O(1) since there are no list traversals, and each object in the heap would be stored contiguously. And given the size of the arrays we'd expect from all transformations, unless we preallocate a HUGE amount of memory space, we're still going to be hindered (speed and cache misses) by the single virtual memory space being separated throughout the core. If, instead, you're truly creating a single OBJECT with all of the cubes and transformations in a single set of arrays, I'd expect the still constant time calculation of the indices for lookup to be at least twice as computationally intensive as pointing directly to them. Not to mention - if this is all a single array - what this would do to insertion and removal times! Even implementing with a search tree instead of an array should still be slower, if I'm understanding this correctly (which I am clearly not :D)
Is this just a python thing, to trick the interpreter into doing what you want?
I've never done graphics programming, and I know nothing about how Python works under the hood... someone please explain what I'm getting wrong here :)
So, per usual, I should have just watched the full video before commenting... but my questions are still somewhat relevant (maybe?).
It seems your implementation makes perfect sense here, since you're using a small, set number of cubes with a set number of transformations mapped 1:1.
I'm curious if this 1) scales with thousands of objects, and/or 2) remains efficient with frequent additions/removals?
I don’t remember exactly what implementation I went with here, from memory this should scale decently for more objects but needs some modification to actually be useful within a more complicated system. There will be certain thresholds at which one approach beats another. Currently I’m going with an ordered array and binary search lookup for my engines, but this is prefaced on the idea that I’ll be searching data a lot more than adding/deleting. Beyond a certain size a hashmap would probably perform better.
Wouldn't it be easier to read/handle if the fields that are used often together be in a struct instead of in multiple arrays? I understand that by exploding everything, it's easier to just pick and choose what data you need, but I'm concerned about the performance if you have to handle multiple huge arrays in a tight loop.
DOTS handle CPU bottlenecks. I'm using DOTS when needed. OOP is much better for more complex problems (like Behaviour trees etc.)
Feels like a fancy term for a glorified logical extension of "unwrapping the loop" solution for performance.