22

The usual example of Data Oriented Design is with the Ball structure:

struct Ball
{
  float Radius;
  float XYZ[3];
};

and then they make some algorithm that iterates a std::vector<Ball> vector.

Then they give you the same thing, but implemented in Data Oriented Design:

struct Balls
{
  std::vector<float> Radiuses;
  std::vector<XYZ[3]> XYZs;
};

Which is good and all if you're going to iterate trough all radiuses first, then all positions and so on. However, how do you move the balls in the vector? In the original version, if you have a std::vector<Ball> BallsAll, you can just move any BallsAll[x] to any BallsAll[y].

However to do that for the Data Oriented version, you must do the same thing for every property (2 times in the case of Ball - radius and position). But it gets worse if you have a lot more properties. You'll have to keep an index for each "ball" and when you try to move it around, you have to do the move in every vector of properties.

Doesn't that kill any performance benefit of Data Oriented Design?

22

Another answer gave an excellent overview over how you'd nicely encapsulate the row-oriented storage and give a better view. But since you also ask about performance, let me address that: SoA layout is not a silver bullet. It's a pretty good default (for cache usage; not so much for ease of implementation in most languages), but it's not all there is, not even in data oriented design (whatever that exactly means). It's possible that the authors of some introductions you've read missed that point and present only SoA layout because they think that's the entire point of DOD. They'd be wrong, and thankfully not everyone falls into that trap.

As you've probably already realized, not every piece of primitive data benefits from being pulled out into its own array. SoA layout is of advantage when the components that you split into separate arrays are usually accessed separately. But not every tiny piece is accessed in isolation, for example a position vector is almost always read and updated wholesale, so naturally you don't split that one. In fact, your example didn't do that either! Likewise, if you usually access all the properties of a Ball together, because you spend most of your time swapping balls around in your collection of balls, there is no point in separating them.

However, there's a second side to DOD. You don't get all the cache and organization advantages just by turning your memory layout 90° and doing the least to fix the resulting compile errors. There are other common tricks taught under this banner. For example "existence-based processing": If you frequently deactivate balls and re-reactivate them, don't add a flag to the ball object and make the update loop ignore balls with the flag set to false. Move the ball from a "active" collection to a "inactive" collection, and make the update loop only inspect the "active" collection.

More importantly and relevantly to your example: If you spend so much time shuffling the balls array, maybe you are doing something wrong. Why does the order matter? Can you make it not matter? If so, you'd gain several benefits:

  • You don't need to shuffle the collection (the fastest code is no code at all).
  • You can add and delete more easily and efficiently (swap to end, drop last).
  • The remaining code may become eligible for further optimizations (such as the layout change you focus on).

So instead of blindly throwing SoA at everything, think about your data and how you process it. If you find that you process the positions and velocities in one loop, then go through the meshes, and then update the hitpoints, try splitting your memory layout into these three parts. If you find that you access the x, y, z components of the position in isolation, maybe turn your position vectors into a SoA. If you find yourself shuffling data more than actually doing something useful, maybe stop shuffling it.

18

Data-Oriented Mindset

Data-oriented design doesn't mean apply SoAs everywhere. It simply means designing architectures with a predominant focus on data representation -- specifically with a focus on efficient memory layout and memory access.

That could possibly lead to SoA reps when appropriate like so:

struct BallSoa
{
   vector<float> x;        // size n
   vector<float> y;        // size n
   vector<float> z;        // size n
   vector<float> r;        // size n
};

... this is often suitable for vertical loopy logic that doesn't process a sphere center vector components and radius simultaneously (the four fields aren't simultaneously hot), but instead one at a time (a loop through radius, another 3 loops through individual components of sphere centers).

In other cases it might be more appropriate to use an AoS if the fields are frequently accessed together (if your loopy logic is iterating through all the fields of balls rather than individually) and/or if random-access of a ball is needed:

struct BallAoS
{
    float x;
    float y;
    float z;
    float r;
};
vector<BallAoS> balls;        // size n

... in other cases it might be suitable to use a hybrid which balances both benefits:

struct BallAoSoA
{
    float x[8];
    float y[8];
    float z[8];
    float r[8];
};
vector<BallAoSoA> balls;      // size n/8

... you might even compress the size of a ball to half using half-floats to fit more ball fields into a cache line/page.

struct BallAoSoA16
{
    Float16 x2[16];
    Float16 y2[16];
    Float16 z2[16];
    Float16 r2[16];
};
vector<BallAoSoA16> balls;    // size n/16

... perhaps even the radius is not accessed nearly as often as the sphere center (perhaps your codebase often treats them like points and only rarely as spheres, e.g.). In that case, you might apply a hot/cold field splitting technique further.

struct BallAoSoA16Hot
{
    Float16 x2[16];
    Float16 y2[16];
    Float16 z2[16];
};
vector<BallAoSoA16Hot> balls;     // size n/16: hot fields
vector<Float16> ball_radiuses;    // size n: cold fields

The key to a data-oriented design is to consider all of these kinds of representations early in making your design decisions, to not trap yourself into a sub-optimal representation with a public interface behind it.

It puts a spotlight on memory access patterns and accompanying layouts, making them a significantly stronger concern than usual. In a sense it may even somewhat tear down abstractions. I've found by applying this mindset more that I no longer look at std::deque, e.g., in terms of its algorithmic requirements quite as much as the aggregated contiguous blocks representation it has and how random-access of it works at the memory level. It is somewhat putting a focus on implementation details, but implementation details which tend to have just as much or more of an impact on performance as the algorithmic complexity describing scalability.

Premature Optimization

A lot of the predominant focus of data-oriented design will appear, at least at a glance, as dangerously close to premature optimization. Experience often teaches us that such micro-optimizations are best applied in hindsight, and with a profiler in hand.

Yet perhaps a strong message to take from data-oriented design is to leave room for such optimizations. That's what a data-oriented mindset can help allow:

Data-oriented design can leave breathing room to explore more effective representations. It's not necessarily about achieving memory layout perfection in one go, but more about making the appropriate considerations in advance to allow increasingly-optimal representations.

Granular Object-Oriented Design

A lot of data-oriented design discussions will pit themselves against classical notions of object-oriented programming. Yet I would offer a way of looking at this which is not quite as hardcore as to dismiss OOP entirely.

The difficulty with object-oriented design is that it will often tempt us to model interfaces at a very granular level, leaving us trapped with a scalar, one-at-a-time mindset instead of a parallel bulk mindset.

As an exaggerated example, imagine an object-oriented design mindset applied to a single pixel of an image.

class Pixel
{
public:
    // Pixel operations to blend, multiply, add, blur, etc.

private:
    Image* image;          // back pointer to access adjacent pixels
    unsigned char rgba[4];
};

Hopefully no one actually does this. To make the example really gross, I stored a back pointer to the image containing the pixel so that it can access neighboring pixels for image processing algorithms like blur.

The image back pointer immediately adds a glaring overhead, but even if we excluded it (making only the public interface of pixel provide operations that apply to a single pixel), we end up with a class just to represent a pixel.

Now there's nothing wrong with a class in the immediate overhead sense in a C++ context besides this back pointer. Optimizing C++ compilers are great at taking all the structure we built and obliterating it down to smithereens.

The difficulty here is that we're modeling an encapsulated interface at too granular of a pixel level. That leaves us trapped with this kind of granular design and data, with potentially a vast number of client dependencies coupling them to this Pixel interface.

Solution: obliterate away the object-oriented structure of a granular pixel, and start modeling your interfaces at a coarser level dealing with a bulk number of pixels (at the image level).

By modeling at the bulk image level, we have significantly more room to optimize. We can, for example, represent large images as coalesced tiles of 16x16 pixels which perfectly fit into a 64-byte cache line but allow efficient neighboring vertical access of pixels with a typically-small stride (if we have a number of image processing algorithms which need to access neighboring pixels in a vertical fashion) as a hardcore data-oriented example.

Designing at a Coarser Level

The above example of modeling interfaces at an image level is kind of a no-brainer example as image processing is a very mature field that's been studied and optimized to death. Yet less obvious might be a particle in a particle emitter, a sprite vs. a collection of sprites, an edge in a graph of edges, or even a person vs. a collection of people.

The key to allowing data-oriented optimizations (in foresight or hindsight) is often going to boil down to designing interfaces at a much coarser level, in bulk. The idea of designing interfaces for single entities becomes replaced by designing for collections of entities with big operations that process them in bulk. This especially and immediately targets sequential access loops that need to access everything and cannot help but have linear complexity.

Data-oriented design often begins with the idea of coalescing data to form aggregates modeling data in bulk. A similar mindset echoes to the interface designs that accompany it.

This is the most valuable lesson I've taken from data-oriented design, since I'm not computer architecture-savvy enough to often find the most optimal memory layout for something on my first try. It becomes something I iterate towards with a profiler in hand (and sometimes with a few misses along the way where I failed to speed things up). Yet the interface design aspect of data-oriented design is what leaves me room to seek more and more efficient data representations.

The key is to design interfaces at a coarser level than we're usually tempted to do. This also often has side benefits like mitigating the dynamic dispatch overhead associated with virtual functions, function pointer calls, dylib calls and the inability for those to be inlined. The main idea to take out of all of this is to look at processing in a bulk fashion (when applicable).

5

What you have described is an implementation problem. OO design is expressly not concerned with implementations.

You can encapsulate your column-oriented Ball container behind an interface that exposes a row- or column-oriented view. You could implement a Ball object with methods like volume and move, which merely modify the respective values in the underlying column-wise structure. At the same time, your Ball container could expose an interface for efficient column-wise operations. With appropriate templates/types and a clever inlining compiler, you can use these abstractions with zero runtime cost.

How often will you be accessing data column-wise vs. modifying it row-wise? In typical use cases for column storage, the ordering of the rows has no effect. You could define an arbitrary permutation of the rows by adding a separate index column. Changing the ordering would only require swapping values in the index column.

Efficient addition/removal of elements could be achieved with other techniques:

  • Maintain a bitmap of deleted rows instead of shifting elements. Compact the structure when it gets too sparse.
  • Group rows into appropriate-sized chunks in a B-Tree-like structure so that insertion or removal in arbitrary positions doesn't require modifying the entire structure.

Client code would see a sequence of Ball objects, a mutable container of Ball objects, a sequence of radii, an Nx3 matrix, etc; it doesn't have to be concerned with the ugly details of those complex (but efficient) structures. That's what the object abstraction buys you.

  • +1 AoS organization is perfectly amendable to a nice entity-oriented API, although admittedly it becomes uglier to use (ball->do_something(); versus ball_table.do_something(ball)) unless you want to fake a coherent entity via a pseudo-pointer (&ball_table, index). – user7043 Jul 1 '14 at 7:38
  • 1
    I'll go a step further: The conclusion to use SoA can be reached purely from OO design principles. The trick is you need a scenario where the columns are a more fundamental object than the rows. Balls are not a good example here. Instead, consider a terrain with various properties like height, soil type, or rainfall. Each property is modeled as a ScalarField object, which has its own methods like gradient() or divergence() that may return other Field objects. You can encapsulate things like map resolution, and different properties on the terrain can work with different resolutions. – 16807 Sep 19 '16 at 21:16
4

Short answer: you are fully correct, and articles like this one are completely missing this point.

The full answer is: the "Structure-Of-Arrays" approach of your examples can have performance advantages for some kind of operations ("column operations"), and "Arrays-of-Structs" for other kind of operations ("row operations", like the ones you mentioned above). The same principle has influenced database architectures, there are column-oriented databases vs. the classical row oriented databases

So the second thing to consider for choosing a design is what kind of operations you need most in your program, and if those will benefit from the different memory layout. However, the first thing to consider is if you really need that performance (I think in games programming, where the above article is from you often have this requirement).

Most current OO languages use an "Array-Of-Struct" memory layout for objects and classes. Getting the advantages of OO (like creating abstractions for your data, encapsulation and more local scope of basic functions), is typically linked to this kind of memory layout. So as long as you don't do high performance computing, I would not consider SoA as the primary approach.

  • 3
    DOD does not always mean Structure-of-Array (SoA) layout. It's common, because it often matches the access pattern, but when another layout works better, by all means use that. DOD is a far more general (and fuzzier), more like a design paradigm than a specific way to lay out data. Also, while the article you reference is far from the best resource and has its flaws, it does not advertise SoA layouts. The "A"s and "B"s can be fully featured Balls just as well as they can be individual floats or vec3s (which would themselves be subject to SoA-transformation). – user7043 Jul 1 '14 at 7:25
  • 2
    ... and the row oriented design you mention is always encompassed in DOD. It's called an array of structures (AoS), and the difference to what most resources call "the OOP way" (for better or wose) is not in row vs. column layout but simply how this layout is mapped to memory (many small objects linked via pointers versus a big continuous table of all records). In summary, -1 because although you raise good points against OP's misconceptions, you misrepresent the whole DOD jazz rather than correcting OP's understanding of DOD. – user7043 Jul 1 '14 at 7:34
  • @delnan: thanks for your comment, you are probably correct that I should have used the term "SoA" instead of "DOD". I edited my answer accordingly. – Doc Brown Jul 2 '14 at 16:12
  • Much better, downvote removed. Check out user2313838's answer for how SoA can be unified with nice "object"-oriented APIs (in the sense of abstractions, encapsulation, and "more local scope of basic functions"). It comes more naturally for AoS layout (since the array can be a dumb generic container rather than being married to the element type) but it's feasible. – user7043 Jul 2 '14 at 16:20
  • And this github.com/BSVino/JaiPrimer/blob/master/JaiPrimer.md which has automatic conversion from SoA to/from AoS Example: reddit.com/r/rust/comments/2t6xqz/… and then there is this: news.ycombinator.com/item?id=10235766 – Jerry Jeremiah Aug 14 at 5:15

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.