13 deleted 15980 characters in body
source | link

It sounds to me like your needs are driving you towards data-oriented design, which is pretty exciting since I don't think I've met too many Python developers who have developed that inclination out of their measurements. For designs where performance is the top goal, it's often a very powerful way of going about design.

It's a common mindset among developers working with tight resources or need frugality anyway because speed is one of the most competitive qualities of their product. It is a very effective design strategy when applied carefully to the areas of a codebase that truly handle a heavy load.

If you wish to pursue data-oriented design, I might be able to offer some tips as one who has been applying this basic mindset from the beginning (started out in C on DOS with very tight resources and it just seemed like the most natural way to design software back then).

It's also worth noting that it's not incompatible at all with object-oriented programming, only very granular object-oriented programming.

Data-Oriented Design

Data-oriented design tackles design and architecture from the data side of the picture. Instead of thinking about operations and entities first, we think more about data. "This program simulates a boatload of particles, and particles need these data fields." Operations and algorithms are secondary to data structures and memory layouts, since the first interact with the second from this data-centric point of view.

Data-oriented designers tend to communicate their designs primarily through the data representations and/or data structures, somewhat leaving the public interface/operations to the imagination, like so with C-style pseudocode:

struct Particles
{
    struct ParticleHot
    {
        // AoSoA representation (hot fields) -- YMM register alignment.
        ALIGN32 float x[8];
        ALIGN32 float y[8];
        ALIGN32 float z[8];
    };
    struct ParticleCold
    {
        // Fields not accessed in critical loops (cold fields).
        float size;
        int id;
    };
    struct ParticleHot particles_hot[ceil_int(n / 8)];
    struct ParticleCold particles_cold[n];
};

This might seem backwards with an unhealthy focus on implementation details, but the goal here is still design, namely interface design. Thinking about the data first is still more of an exercise to help us think about the right things when trying to produce public interface designs for performance-critical areas.

Interface Stability

In complex performance-critical codebases, an interface design can conform beautifully to SOLID engineering principles and still find plenty of instability where the number one reason for a design to change becomes a greater need for performance.

The result can be otherwise well-engineered interfaces having to become deprecated with slow cascading transformations of the codebase, or jarring cascading breakages (if no deprecation strategy is sought out) towards new interfaces simply for added performance.

Embracing a data-oriented mindset can significantly counter that and lead to very stable designs even when performance is a very high-priority design goal. It leads to designs that offer all the wiggle room you need to iterate towards faster and faster solutions without changing the design whatsoever, only the implementation behind it.

It's worth keeping this in mind. The goal isn't to try to come up with the fastest implementation possible on the first try, if ever (this could easily start to become very counter-productive), but more to come up with a stable interface that won't ever have "performance" among its reasons to change. For implementations, performance is still something we tend to iterate towards with a profiler in hand, and seeking the absolute peak ideal is often undesirable as optimizations start to yield diminishing returns while rapidly degrading maintainability as you start scraping metal.

Collection Interfaces

As noted, data-oriented design isn't incompatible with object-oriented design, only very granular object-oriented design. It's because a lot of granular structure will be demolished through the DOD processDesign bigger objects.

Granular entities like A Pixel, Particle, Point, Rect, possibly even Sprite or Person will turn into implementation details: raw data behind some collection interface like Image, ParticleSystem, Points, Rects, SpriteHandler, People.

It sounds to me like your Volatility structure is likewise too granular and needs to be demolished in favor of an object-oriented interface modeling a collection of these.

Public interfaces will start to handle data in bulk, not in little teeny scalar pieces.

Bulk Algorithms

Related to the idea of a collection interface, algorithms like transform algorithms will often need to take on has no breathing room for a generic form to avoid turning your collection interfaces into monoliths trying to do everything imaginable (ex: an image interface that tries to provide every singleparallelized loop or GPU image operation imaginable as opposed to just one generic way to transform pixels in bulk).

Similar to the collection interface, your abstract algorithmic functions will likewise tend to start processing data in bulk. For example, instead of this:

boolean some_predicate(element)
void modify_point(point)

... you might have something more like this:

void some_predicate(num_elements, elements[], boolean out_results[])
void modify_points(num_points, points[])

... where the predicate receives more than one element at a time and outputs its results to a boolean array (typically one that's either reusedtransformations or on the stack for temporal locality across calls to the "bulk" predicate), and transform_points modifies more than one point at a time.

This helps to enable new optimization capabilities for bulk processinganything like SoA SIMD intrinsics. They also significantly mitigate dynamic dispatch overhead (and the optimization barriers they impose), and can also encourage thread locks at a more appropriate level (not too granular/frequent for overly-light work). Likewise if you ever want to do GPGPU, GPGPU likewise wants data to be fed to it in contiguous bulk, which likewise favors a data-oriented mindset.

In other cases, you might even expose raw chunks of data as plain old data types to process in bulk, or possibly behind safer proxies that return data to process in bulk.

Wiggle Room

The main problem that very granular object-oriented design imposes from a performance standpoint is not the cost of objects, per se. With optimizing C++ compilers, for example, the cost of an object is often free. The optimizer will obliterate away the structure and make things like accessor functions cost nothing at all at runtime.

The difficulty is that modeling something at a granular level like a singleAn ParticleImage will paint you into a data representation corner as the rest of your codebase becomes coupled to the object-oriented interface of a single particle that encapsulates and owns its state. We can no longer apply effective memory optimizations like hot/cold field splitting when there's nothing being aggregated beyond the fields of a single particle. We can't utilize SoA representations, we can't reach around and coalesce data from surrounding particles in a way that goes beyond a straightforward AoS form. We can't obliterate away this structure and just packdoes provided it into an array of floats for a very efficient bulk-processing library or hardware to process.

So it's not really about avoiding the cost of user-defined types. Against some compilers at least, user-defined type objects can be free. Yet they're not free in terms of what they do from a design standpoint -- they take away all wiggle room to optimize the data representation further. Collections of elements, on the other hand, leave lots of wiggle room.

It's like if youdoesn't have a race car, a lot of its speed is going to be wasted if the road is only 10 meters long.

Contiguous Memory

In particular, a heavy DOD mindset will tend to favor bulk processing over contiguous chunks of data -- arrays of elements rather than individual elements being passed one at a time. It's a natural tendency due to the way that hardware favors spatial locality with its CPU cache design, and likewise in part the operating system with the way it physically maps memory through contiguous pages at really large input scales.

Even linked structures may start to take on more partially-contiguous forms, like unrolled lists instead of linked lists, n-ary trees instead of binary trees, in response to measurements and tuning. The alternative is to reach under these data structures and achieve contiguitygo through the memory allocator, but a data-oriented mindset generally favors contiguity and processing which uses all data in a cache line or physically-mapped page prior to eviction by whatever means possible (memory pools or data structure or combo of both).

Metadata and alignment/padding costs per element will often want to be mitigated and squashed down to a minimum, all in favor of packing more relevant data into a contiguous chunk. Cold data fields which are irrelevant in your critical paths of execution will want to be split away from hot data fields to allow more relevant hot fields to be packed into contiguous chunks so that the machine can consume such data at a faster rate.

Plain Old Data

One of the tendencies that tend to arise with a DOD mindset is a greater appreciation for plain old data types, like int, float, double, short. They're lowest common denominator types that directly communicate the amountbarrier of memory required, don't require any coupling to other user-defined types in your system, and can be a universal way of achieving interoperability with other APIs and languages.

With DOD, there tends to be significantly reduced coupling in your system as you end up turning those granular object-oriented designs liketeeny Pixel or Particle into implementation details, no longer complex objects of their own.

In complex codebases embracing a granular object-oriented mindeset, a lot of coupling tends to be in the form of message passing of more complex user-defined parameter types, like a single Rect, a single Point, etc. With DOD, those teeny structures tend to be demolished in favor of plain old data types, arrays of them, or at least simpler structures, and that can result in a significant amount of decoupling and more independent interfaces.

Through such independence often comes a more timeless quality about your code, since plain old data types don't go out of style. A very complex and bulky expression template linear algebra library might go out of style a lot faster than an array of floats or doubles. The interfaces associated with POD types tend to be less expressive and more inconvenient, but that timeless quality that comes from very decoupled and independent designs can make up for it if you're seeking designs that last a very long time and can be deployed and reused easily in various projects over the years to come.

Stride

For the greatest level of flexibility and stability in your performance-critical interfaces, it can be helpful to accept stride parameters to indicate the stride size to get from one field to the next, like so:

void process_points(int num_points, float xyz[], int stride)

... even more flexible might separate the fields away from an AoS (array of structures) mindset, like so:

void process_points(int num_points, 
                    float x[], float y[], float z[],
                    int x_stride, int y_stride, int z_stride)

... this allows even SoA (structure of array) representations to be squeezed through this interface directly without forming some kind of temporary array, and also allows the implementors of these abstract functions to potentially utilize SoA SIMD optimizations when the x/y/z strides indicate that these fields are contiguous in nature (xxxxxxxx yyyyyyyy zzzzzzzz etc).

This is getting pretty inconvenient to use, however, so it may be worth wrapping these to a more complex and bundled parameter type if this degree of representation flexibility is needed.

In spite of the inconvenience at the implementation level, interface designs which accept data in bulk with stride parameters can achieve tremendous stability with performance being stricken completely from the list of reasons to change.

Data Structures

A lot of data-oriented design discussions will go very quickly into memory and SIMD and multithreading and GPU-level micro-optimizations, but solely because they're the most counter-intuitive and something that isn't often quite as big of a focus in computer science and SE courses.

Yet of course, if you are designing a raytracer, the first thing to think about is your acceleration data structure like a K-D tree or bounding volume hierarchy. Micro-optimizations like ray packets for SIMD are secondary in nature. If you are designing a video game with a bunch of sprites with collision detection, probably the first thing to think about is a spatial indexing accelerator which is going to accelerate the collision detection. The same concept applies, nevertheless, at the interface level. Whether the priority is data structures first and memory layouts second or vice versa (ex: in places that cannot do better than linear complexity), the DOD mindset considers data first.

Python

It seems kind of unusual to encounter a Python developer evolving a data-oriented mindset. Some of the techniques mentioned above like using interfaces with a stride may be inapplicable without pointers and the ability to kind of dangerously work at the bits and bytes level. SoA SIMD intrinsics might be out (at least at the hand-written level, not sure about the ability for Python optimizers to generate vectorized instructions from an SoA memory access pattern).

Nevertheless, the overall concepts related to interface design and thinking about data should apply, and concepts like cache-friendliness and memory optimization apply regardless of the language. It may help at least at the level of helping you design interfaces and data representations that you can pass through in bulk to native C APIs like numpy.

DOD should be applicable to all languages since the hardware characteristics and the nature of data structures don't change across languages. Some languages might not let you get to quite the same level of explicit control over memory representation and micro-optimization, e.g., but we're still unified by the same hardware, memory hierarchy, a need for interface designs that don't have to change to seek higher performance.

If you can't do much in the way of memory allocators, for example, you can do more at the data structure level. It's all a blur anyway between data structures and memory pools. You might use a data structure which favors storing nodes directly in an array with indices, for example, instead of using a memory allocator to achieve spatial locality underneath the data structure.

Anyway, I hope some of this above will help a bit. There's nothing wrong with data-oriented design, as it can be the most effective and productive way to design things that handle a heavy load. It does tend to push implementations to a lower, more difficult level (though interfaces can remain fairly high-level, and sometimes even higher-level than interfaces that deal with a scalar, "one little element at a time" mindset). As a result, the cost of implementing under data-oriented design tends to increase upfront and the need for testing increases with often-reduced type safety, though the bigger, large-scale maintenance costs associated with interface instability go away if the interfaces to which you are applying a data-oriented design mindset truly handle a heavy load.

It sounds to me like your needs are driving you towards data-oriented design, which is pretty exciting since I don't think I've met too many Python developers who have developed that inclination out of their measurements. For designs where performance is the top goal, it's often a very powerful way of going about design.

It's a common mindset among developers working with tight resources or need frugality anyway because speed is one of the most competitive qualities of their product. It is a very effective design strategy when applied carefully to the areas of a codebase that truly handle a heavy load.

If you wish to pursue data-oriented design, I might be able to offer some tips as one who has been applying this basic mindset from the beginning (started out in C on DOS with very tight resources and it just seemed like the most natural way to design software back then).

It's also worth noting that it's not incompatible at all with object-oriented programming, only very granular object-oriented programming.

Data-Oriented Design

Data-oriented design tackles design and architecture from the data side of the picture. Instead of thinking about operations and entities first, we think more about data. "This program simulates a boatload of particles, and particles need these data fields." Operations and algorithms are secondary to data structures and memory layouts, since the first interact with the second from this data-centric point of view.

Data-oriented designers tend to communicate their designs primarily through the data representations and/or data structures, somewhat leaving the public interface/operations to the imagination, like so with C-style pseudocode:

struct Particles
{
    struct ParticleHot
    {
        // AoSoA representation (hot fields) -- YMM register alignment.
        ALIGN32 float x[8];
        ALIGN32 float y[8];
        ALIGN32 float z[8];
    };
    struct ParticleCold
    {
        // Fields not accessed in critical loops (cold fields).
        float size;
        int id;
    };
    struct ParticleHot particles_hot[ceil_int(n / 8)];
    struct ParticleCold particles_cold[n];
};

This might seem backwards with an unhealthy focus on implementation details, but the goal here is still design, namely interface design. Thinking about the data first is still more of an exercise to help us think about the right things when trying to produce public interface designs for performance-critical areas.

Interface Stability

In complex performance-critical codebases, an interface design can conform beautifully to SOLID engineering principles and still find plenty of instability where the number one reason for a design to change becomes a greater need for performance.

The result can be otherwise well-engineered interfaces having to become deprecated with slow cascading transformations of the codebase, or jarring cascading breakages (if no deprecation strategy is sought out) towards new interfaces simply for added performance.

Embracing a data-oriented mindset can significantly counter that and lead to very stable designs even when performance is a very high-priority design goal. It leads to designs that offer all the wiggle room you need to iterate towards faster and faster solutions without changing the design whatsoever, only the implementation behind it.

It's worth keeping this in mind. The goal isn't to try to come up with the fastest implementation possible on the first try, if ever (this could easily start to become very counter-productive), but more to come up with a stable interface that won't ever have "performance" among its reasons to change. For implementations, performance is still something we tend to iterate towards with a profiler in hand, and seeking the absolute peak ideal is often undesirable as optimizations start to yield diminishing returns while rapidly degrading maintainability as you start scraping metal.

Collection Interfaces

As noted, data-oriented design isn't incompatible with object-oriented design, only very granular object-oriented design. It's because a lot of granular structure will be demolished through the DOD process.

Granular entities like Pixel, Particle, Point, Rect, possibly even Sprite or Person will turn into implementation details: raw data behind some collection interface like Image, ParticleSystem, Points, Rects, SpriteHandler, People.

It sounds to me like your Volatility structure is likewise too granular and needs to be demolished in favor of an object-oriented interface modeling a collection of these.

Public interfaces will start to handle data in bulk, not in little teeny scalar pieces.

Bulk Algorithms

Related to the idea of a collection interface, algorithms like transform algorithms will often need to take on a generic form to avoid turning your collection interfaces into monoliths trying to do everything imaginable (ex: an image interface that tries to provide every single image operation imaginable as opposed to just one generic way to transform pixels in bulk).

Similar to the collection interface, your abstract algorithmic functions will likewise tend to start processing data in bulk. For example, instead of this:

boolean some_predicate(element)
void modify_point(point)

... you might have something more like this:

void some_predicate(num_elements, elements[], boolean out_results[])
void modify_points(num_points, points[])

... where the predicate receives more than one element at a time and outputs its results to a boolean array (typically one that's either reused or on the stack for temporal locality across calls to the "bulk" predicate), and transform_points modifies more than one point at a time.

This helps to enable new optimization capabilities for bulk processing like SoA SIMD intrinsics. They also significantly mitigate dynamic dispatch overhead (and the optimization barriers they impose), and can also encourage thread locks at a more appropriate level (not too granular/frequent for overly-light work). Likewise if you ever want to do GPGPU, GPGPU likewise wants data to be fed to it in contiguous bulk, which likewise favors a data-oriented mindset.

In other cases, you might even expose raw chunks of data as plain old data types to process in bulk, or possibly behind safer proxies that return data to process in bulk.

Wiggle Room

The main problem that very granular object-oriented design imposes from a performance standpoint is not the cost of objects, per se. With optimizing C++ compilers, for example, the cost of an object is often free. The optimizer will obliterate away the structure and make things like accessor functions cost nothing at all at runtime.

The difficulty is that modeling something at a granular level like a single Particle will paint you into a data representation corner as the rest of your codebase becomes coupled to the object-oriented interface of a single particle that encapsulates and owns its state. We can no longer apply effective memory optimizations like hot/cold field splitting when there's nothing being aggregated beyond the fields of a single particle. We can't utilize SoA representations, we can't reach around and coalesce data from surrounding particles in a way that goes beyond a straightforward AoS form. We can't obliterate away this structure and just pack it into an array of floats for a very efficient bulk-processing library or hardware to process.

So it's not really about avoiding the cost of user-defined types. Against some compilers at least, user-defined type objects can be free. Yet they're not free in terms of what they do from a design standpoint -- they take away all wiggle room to optimize the data representation further. Collections of elements, on the other hand, leave lots of wiggle room.

It's like if you have a race car, a lot of its speed is going to be wasted if the road is only 10 meters long.

Contiguous Memory

In particular, a heavy DOD mindset will tend to favor bulk processing over contiguous chunks of data -- arrays of elements rather than individual elements being passed one at a time. It's a natural tendency due to the way that hardware favors spatial locality with its CPU cache design, and likewise in part the operating system with the way it physically maps memory through contiguous pages at really large input scales.

Even linked structures may start to take on more partially-contiguous forms, like unrolled lists instead of linked lists, n-ary trees instead of binary trees, in response to measurements and tuning. The alternative is to reach under these data structures and achieve contiguity through the memory allocator, but a data-oriented mindset generally favors contiguity and processing which uses all data in a cache line or physically-mapped page prior to eviction by whatever means possible (memory pools or data structure or combo of both).

Metadata and alignment/padding costs per element will often want to be mitigated and squashed down to a minimum, all in favor of packing more relevant data into a contiguous chunk. Cold data fields which are irrelevant in your critical paths of execution will want to be split away from hot data fields to allow more relevant hot fields to be packed into contiguous chunks so that the machine can consume such data at a faster rate.

Plain Old Data

One of the tendencies that tend to arise with a DOD mindset is a greater appreciation for plain old data types, like int, float, double, short. They're lowest common denominator types that directly communicate the amount of memory required, don't require any coupling to other user-defined types in your system, and can be a universal way of achieving interoperability with other APIs and languages.

With DOD, there tends to be significantly reduced coupling in your system as you end up turning those granular object-oriented designs like Pixel or Particle into implementation details, no longer complex objects of their own.

In complex codebases embracing a granular object-oriented mindeset, a lot of coupling tends to be in the form of message passing of more complex user-defined parameter types, like a single Rect, a single Point, etc. With DOD, those teeny structures tend to be demolished in favor of plain old data types, arrays of them, or at least simpler structures, and that can result in a significant amount of decoupling and more independent interfaces.

Through such independence often comes a more timeless quality about your code, since plain old data types don't go out of style. A very complex and bulky expression template linear algebra library might go out of style a lot faster than an array of floats or doubles. The interfaces associated with POD types tend to be less expressive and more inconvenient, but that timeless quality that comes from very decoupled and independent designs can make up for it if you're seeking designs that last a very long time and can be deployed and reused easily in various projects over the years to come.

Stride

For the greatest level of flexibility and stability in your performance-critical interfaces, it can be helpful to accept stride parameters to indicate the stride size to get from one field to the next, like so:

void process_points(int num_points, float xyz[], int stride)

... even more flexible might separate the fields away from an AoS (array of structures) mindset, like so:

void process_points(int num_points, 
                    float x[], float y[], float z[],
                    int x_stride, int y_stride, int z_stride)

... this allows even SoA (structure of array) representations to be squeezed through this interface directly without forming some kind of temporary array, and also allows the implementors of these abstract functions to potentially utilize SoA SIMD optimizations when the x/y/z strides indicate that these fields are contiguous in nature (xxxxxxxx yyyyyyyy zzzzzzzz etc).

This is getting pretty inconvenient to use, however, so it may be worth wrapping these to a more complex and bundled parameter type if this degree of representation flexibility is needed.

In spite of the inconvenience at the implementation level, interface designs which accept data in bulk with stride parameters can achieve tremendous stability with performance being stricken completely from the list of reasons to change.

Data Structures

A lot of data-oriented design discussions will go very quickly into memory and SIMD and multithreading and GPU-level micro-optimizations, but solely because they're the most counter-intuitive and something that isn't often quite as big of a focus in computer science and SE courses.

Yet of course, if you are designing a raytracer, the first thing to think about is your acceleration data structure like a K-D tree or bounding volume hierarchy. Micro-optimizations like ray packets for SIMD are secondary in nature. If you are designing a video game with a bunch of sprites with collision detection, probably the first thing to think about is a spatial indexing accelerator which is going to accelerate the collision detection. The same concept applies, nevertheless, at the interface level. Whether the priority is data structures first and memory layouts second or vice versa (ex: in places that cannot do better than linear complexity), the DOD mindset considers data first.

Python

It seems kind of unusual to encounter a Python developer evolving a data-oriented mindset. Some of the techniques mentioned above like using interfaces with a stride may be inapplicable without pointers and the ability to kind of dangerously work at the bits and bytes level. SoA SIMD intrinsics might be out (at least at the hand-written level, not sure about the ability for Python optimizers to generate vectorized instructions from an SoA memory access pattern).

Nevertheless, the overall concepts related to interface design and thinking about data should apply, and concepts like cache-friendliness and memory optimization apply regardless of the language. It may help at least at the level of helping you design interfaces and data representations that you can pass through in bulk to native C APIs like numpy.

DOD should be applicable to all languages since the hardware characteristics and the nature of data structures don't change across languages. Some languages might not let you get to quite the same level of explicit control over memory representation and micro-optimization, e.g., but we're still unified by the same hardware, memory hierarchy, a need for interface designs that don't have to change to seek higher performance.

If you can't do much in the way of memory allocators, for example, you can do more at the data structure level. It's all a blur anyway between data structures and memory pools. You might use a data structure which favors storing nodes directly in an array with indices, for example, instead of using a memory allocator to achieve spatial locality underneath the data structure.

Anyway, I hope some of this above will help a bit. There's nothing wrong with data-oriented design, as it can be the most effective and productive way to design things that handle a heavy load. It does tend to push implementations to a lower, more difficult level (though interfaces can remain fairly high-level, and sometimes even higher-level than interfaces that deal with a scalar, "one little element at a time" mindset). As a result, the cost of implementing under data-oriented design tends to increase upfront and the need for testing increases with often-reduced type safety, though the bigger, large-scale maintenance costs associated with interface instability go away if the interfaces to which you are applying a data-oriented design mindset truly handle a heavy load.

Design bigger objects. A Pixel object has no breathing room for a parallelized loop or GPU image transformations or anything like that. An Image does provided it doesn't have to go through the barrier of a teeny Pixel object to get at the data.

12 Rollback to Revision 10
source | link

As you can see, the OOP way gives me a lot of security that people won't be adding Volatility the wrong way, but the vector method is just so crazy fast! Is there a design in which I can get both? I am sure a lot of you have run into similar design choices, how did you work it out?

WorkingIt sounds to me like your needs are driving you towards data-oriented design, which is pretty exciting since I don't think I've met too many Python developers who have developed that inclination out of their measurements. For designs where performance is the top goal, it's often a very powerful way of going about design.

It's a common mindset among developers working with tight resources or need frugality anyway because speed is one of the most competitive qualities of their product. It is a very effective design strategy when applied carefully to the areas of a codebase that truly handle a heavy load.

If you wish to pursue data-oriented design, I might be able to offer some tips as one who has been applying this basic mindset from the beginning (started out in C on deleting my postsDOS with positive answersvery tight resources and it just seemed like the most natural way to design software back then). Going

It's also worth noting that it's not incompatible at all with object-oriented programming, only very granular object-oriented programming.

Data-Oriented Design

Data-oriented design tackles design and architecture from the data side of the picture. Instead of thinking about operations and entities first, we think more about data. "This program simulates a boatload of particles, and particles need these data fields." Operations and algorithms are secondary to data structures and memory layouts, since the first interact with the second from this data-centric point of view.

Data-oriented designers tend to communicate their designs primarily through the data representations and/or data structures, somewhat leaving the public interface/operations to the imagination, like so with C-style pseudocode:

struct Particles
{
    struct ParticleHot
    {
        // AoSoA representation (hot fields) -- YMM register alignment.
        ALIGN32 float x[8];
        ALIGN32 float y[8];
        ALIGN32 float z[8];
    };
    struct ParticleCold
    {
        // Fields not accessed in critical loops (cold fields).
        float size;
        int id;
    };
    struct ParticleHot particles_hot[ceil_int(n / 8)];
    struct ParticleCold particles_cold[n];
};

This might seem backwards with an unhealthy focus on implementation details, but the goal here is still design, namely interface design. Thinking about the data first is still more of an exercise to help us think about the right things when trying to produce public interface designs for performance-critical areas.

Interface Stability

In complex performance-critical codebases, an interface design can conform beautifully to SOLID engineering principles and still find plenty of instability where the number one reason for a design to change becomes a greater need for performance.

The result can be otherwise well-engineered interfaces having to become deprecated with slow cascading transformations of the codebase, or jarring cascading breakages (if no deprecation strategy is sought out) towards new interfaces simply for added performance.

Embracing a data-oriented mindset can significantly counter that and lead to very stable designs even when performance is a very high-priority design goal. It leads to designs that offer all the wiggle room you need to iterate towards faster and faster solutions without changing the design whatsoever, only the implementation behind it.

It's worth keeping this in mind. The goal isn't to try to come up with the fastest implementation possible on the first try, if ever (this could easily start to become very counter-productive), but more to come up with a stable interface that won't ever have "performance" among its reasons to change. For implementations, performance is still something we tend to iterate towards with a profiler in hand, and seeking the absolute peak ideal is often undesirable as optimizations start to yield diminishing returns while rapidly degrading maintainability as you start scraping metal.

Collection Interfaces

As noted, data-oriented design isn't incompatible with object-oriented design, only very granular object-oriented design. It's because a lot of granular structure will be demolished through the DOD process.

Granular entities like Pixel, Particle, Point, Rect, possibly even Sprite or Person will turn into implementation details: raw data behind some collection interface like Image, ParticleSystem, Points, Rects, SpriteHandler, People.

It sounds to me like your Volatility structure is likewise too granular and needs to be demolished in favor of an object-oriented interface modeling a collection of these.

Public interfaces will start to handle data in bulk, not in little teeny scalar pieces.

Bulk Algorithms

Related to the idea of a collection interface, algorithms like transform algorithms will often need to take on a generic form to avoid turning your collection interfaces into monoliths trying to do everything imaginable (ex: an image interface that tries to provide every single image operation imaginable as opposed to just one generic way to transform pixels in bulk).

Similar to the collection interface, your abstract algorithmic functions will likewise tend to start processing data in bulk. For example, instead of this:

boolean some_predicate(element)
void modify_point(point)

... you might have something more like this:

void some_predicate(num_elements, elements[], boolean out_results[])
void modify_points(num_points, points[])

... where the predicate receives more than one element at a time and outputs its results to a boolean array (typically one that's either reused or on the stack for maximum negative votes!temporal locality across calls to the "bulk" predicate), and transform_points modifies more than one point at a time.

This helps to enable new optimization capabilities for bulk processing like SoA SIMD intrinsics. They also significantly mitigate dynamic dispatch overhead (and the optimization barriers they impose), and can also encourage thread locks at a more appropriate level (not too granular/frequent for overly-light work). Likewise if you ever want to do GPGPU, GPGPU likewise wants data to be fed to it in contiguous bulk, which likewise favors a data-oriented mindset.

In other cases, you might even expose raw chunks of data as plain old data types to process in bulk, or possibly behind safer proxies that return data to process in bulk.

Wiggle Room

The main problem that very granular object-oriented design imposes from a performance standpoint is not the cost of objects, per se. With optimizing C++ compilers, for example, the cost of an object is often free. The optimizer will obliterate away the structure and make things like accessor functions cost nothing at all at runtime.

The difficulty is that modeling something at a granular level like a single Particle will paint you into a data representation corner as the rest of your codebase becomes coupled to the object-oriented interface of a single particle that encapsulates and owns its state. We can no longer apply effective memory optimizations like hot/cold field splitting when there's nothing being aggregated beyond the fields of a single particle. We can't utilize SoA representations, we can't reach around and coalesce data from surrounding particles in a way that goes beyond a straightforward AoS form. We can't obliterate away this structure and just pack it into an array of floats for a very efficient bulk-processing library or hardware to process.

So it's not really about avoiding the cost of user-defined types. Against some compilers at least, user-defined type objects can be free. Yet they're not free in terms of what they do from a design standpoint -- they take away all wiggle room to optimize the data representation further. Collections of elements, on the other hand, leave lots of wiggle room.

It's like if you have a race car, a lot of its speed is going to be wasted if the road is only 10 meters long.

Contiguous Memory

In particular, a heavy DOD mindset will tend to favor bulk processing over contiguous chunks of data -- arrays of elements rather than individual elements being passed one at a time. It's a natural tendency due to the way that hardware favors spatial locality with its CPU cache design, and likewise in part the operating system with the way it physically maps memory through contiguous pages at really large input scales.

Even linked structures may start to take on more partially-contiguous forms, like unrolled lists instead of linked lists, n-ary trees instead of binary trees, in response to measurements and tuning. The alternative is to reach under these data structures and achieve contiguity through the memory allocator, but a data-oriented mindset generally favors contiguity and processing which uses all data in a cache line or physically-mapped page prior to eviction by whatever means possible (memory pools or data structure or combo of both).

Metadata and alignment/padding costs per element will often want to be mitigated and squashed down to a minimum, all in favor of packing more relevant data into a contiguous chunk. Cold data fields which are irrelevant in your critical paths of execution will want to be split away from hot data fields to allow more relevant hot fields to be packed into contiguous chunks so that the machine can consume such data at a faster rate.

Plain Old Data

One of the tendencies that tend to arise with a DOD mindset is a greater appreciation for plain old data types, like int, float, double, short. They're lowest common denominator types that directly communicate the amount of memory required, don't require any coupling to other user-defined types in your system, and can be a universal way of achieving interoperability with other APIs and languages.

With DOD, there tends to be significantly reduced coupling in your system as you end up turning those granular object-oriented designs like Pixel or Particle into implementation details, no longer complex objects of their own.

In complex codebases embracing a granular object-oriented mindeset, a lot of coupling tends to be in the form of message passing of more complex user-defined parameter types, like a single Rect, a single Point, etc. With DOD, those teeny structures tend to be demolished in favor of plain old data types, arrays of them, or at least simpler structures, and that can result in a significant amount of decoupling and more independent interfaces.

Through such independence often comes a more timeless quality about your code, since plain old data types don't go out of style. A very complex and bulky expression template linear algebra library might go out of style a lot faster than an array of floats or doubles. The interfaces associated with POD types tend to be less expressive and more inconvenient, but that timeless quality that comes from very decoupled and independent designs can make up for it if you're seeking designs that last a very long time and can be deployed and reused easily in various projects over the years to come.

Stride

For the greatest level of flexibility and stability in your performance-critical interfaces, it can be helpful to accept stride parameters to indicate the stride size to get from one field to the next, like so:

void process_points(int num_points, float xyz[], int stride)

... even more flexible might separate the fields away from an AoS (array of structures) mindset, like so:

void process_points(int num_points, 
                    float x[], float y[], float z[],
                    int x_stride, int y_stride, int z_stride)

... this allows even SoA (structure of array) representations to be squeezed through this interface directly without forming some kind of temporary array, and also allows the implementors of these abstract functions to potentially utilize SoA SIMD optimizations when the x/y/z strides indicate that these fields are contiguous in nature (xxxxxxxx yyyyyyyy zzzzzzzz etc).

This is getting pretty inconvenient to use, however, so it may be worth wrapping these to a more complex and bundled parameter type if this degree of representation flexibility is needed.

In spite of the inconvenience at the implementation level, interface designs which accept data in bulk with stride parameters can achieve tremendous stability with performance being stricken completely from the list of reasons to change.

Data Structures

A lot of data-oriented design discussions will go very quickly into memory and SIMD and multithreading and GPU-level micro-optimizations, but solely because they're the most counter-intuitive and something that isn't often quite as big of a focus in computer science and SE courses.

Yet of course, if you are designing a raytracer, the first thing to think about is your acceleration data structure like a K-D tree or bounding volume hierarchy. Micro-optimizations like ray packets for SIMD are secondary in nature. If you are designing a video game with a bunch of sprites with collision detection, probably the first thing to think about is a spatial indexing accelerator which is going to accelerate the collision detection. The same concept applies, nevertheless, at the interface level. Whether the priority is data structures first and memory layouts second or vice versa (ex: in places that cannot do better than linear complexity), the DOD mindset considers data first.

Python

It seems kind of unusual to encounter a Python developer evolving a data-oriented mindset. Some of the techniques mentioned above like using interfaces with a stride may be inapplicable without pointers and the ability to kind of dangerously work at the bits and bytes level. SoA SIMD intrinsics might be out (at least at the hand-written level, not sure about the ability for Python optimizers to generate vectorized instructions from an SoA memory access pattern).

Nevertheless, the overall concepts related to interface design and thinking about data should apply, and concepts like cache-friendliness and memory optimization apply regardless of the language. It may help at least at the level of helping you design interfaces and data representations that you can pass through in bulk to native C APIs like numpy.

DOD should be applicable to all languages since the hardware characteristics and the nature of data structures don't change across languages. Some languages might not let you get to quite the same level of explicit control over memory representation and micro-optimization, e.g., but we're still unified by the same hardware, memory hierarchy, a need for interface designs that don't have to change to seek higher performance.

If you can't do much in the way of memory allocators, for example, you can do more at the data structure level. It's all a blur anyway between data structures and memory pools. You might use a data structure which favors storing nodes directly in an array with indices, for example, instead of using a memory allocator to achieve spatial locality underneath the data structure.

Anyway, I hope some of this above will help a bit. There's nothing wrong with data-oriented design, as it can be the most effective and productive way to design things that handle a heavy load. It does tend to push implementations to a lower, more difficult level (though interfaces can remain fairly high-level, and sometimes even higher-level than interfaces that deal with a scalar, "one little element at a time" mindset). As a result, the cost of implementing under data-oriented design tends to increase upfront and the need for testing increases with often-reduced type safety, though the bigger, large-scale maintenance costs associated with interface instability go away if the interfaces to which you are applying a data-oriented design mindset truly handle a heavy load.

Working on deleting my posts with positive answers. Going to try for maximum negative votes!

As you can see, the OOP way gives me a lot of security that people won't be adding Volatility the wrong way, but the vector method is just so crazy fast! Is there a design in which I can get both? I am sure a lot of you have run into similar design choices, how did you work it out?

It sounds to me like your needs are driving you towards data-oriented design, which is pretty exciting since I don't think I've met too many Python developers who have developed that inclination out of their measurements. For designs where performance is the top goal, it's often a very powerful way of going about design.

It's a common mindset among developers working with tight resources or need frugality anyway because speed is one of the most competitive qualities of their product. It is a very effective design strategy when applied carefully to the areas of a codebase that truly handle a heavy load.

If you wish to pursue data-oriented design, I might be able to offer some tips as one who has been applying this basic mindset from the beginning (started out in C on DOS with very tight resources and it just seemed like the most natural way to design software back then).

It's also worth noting that it's not incompatible at all with object-oriented programming, only very granular object-oriented programming.

Data-Oriented Design

Data-oriented design tackles design and architecture from the data side of the picture. Instead of thinking about operations and entities first, we think more about data. "This program simulates a boatload of particles, and particles need these data fields." Operations and algorithms are secondary to data structures and memory layouts, since the first interact with the second from this data-centric point of view.

Data-oriented designers tend to communicate their designs primarily through the data representations and/or data structures, somewhat leaving the public interface/operations to the imagination, like so with C-style pseudocode:

struct Particles
{
    struct ParticleHot
    {
        // AoSoA representation (hot fields) -- YMM register alignment.
        ALIGN32 float x[8];
        ALIGN32 float y[8];
        ALIGN32 float z[8];
    };
    struct ParticleCold
    {
        // Fields not accessed in critical loops (cold fields).
        float size;
        int id;
    };
    struct ParticleHot particles_hot[ceil_int(n / 8)];
    struct ParticleCold particles_cold[n];
};

This might seem backwards with an unhealthy focus on implementation details, but the goal here is still design, namely interface design. Thinking about the data first is still more of an exercise to help us think about the right things when trying to produce public interface designs for performance-critical areas.

Interface Stability

In complex performance-critical codebases, an interface design can conform beautifully to SOLID engineering principles and still find plenty of instability where the number one reason for a design to change becomes a greater need for performance.

The result can be otherwise well-engineered interfaces having to become deprecated with slow cascading transformations of the codebase, or jarring cascading breakages (if no deprecation strategy is sought out) towards new interfaces simply for added performance.

Embracing a data-oriented mindset can significantly counter that and lead to very stable designs even when performance is a very high-priority design goal. It leads to designs that offer all the wiggle room you need to iterate towards faster and faster solutions without changing the design whatsoever, only the implementation behind it.

It's worth keeping this in mind. The goal isn't to try to come up with the fastest implementation possible on the first try, if ever (this could easily start to become very counter-productive), but more to come up with a stable interface that won't ever have "performance" among its reasons to change. For implementations, performance is still something we tend to iterate towards with a profiler in hand, and seeking the absolute peak ideal is often undesirable as optimizations start to yield diminishing returns while rapidly degrading maintainability as you start scraping metal.

Collection Interfaces

As noted, data-oriented design isn't incompatible with object-oriented design, only very granular object-oriented design. It's because a lot of granular structure will be demolished through the DOD process.

Granular entities like Pixel, Particle, Point, Rect, possibly even Sprite or Person will turn into implementation details: raw data behind some collection interface like Image, ParticleSystem, Points, Rects, SpriteHandler, People.

It sounds to me like your Volatility structure is likewise too granular and needs to be demolished in favor of an object-oriented interface modeling a collection of these.

Public interfaces will start to handle data in bulk, not in little teeny scalar pieces.

Bulk Algorithms

Related to the idea of a collection interface, algorithms like transform algorithms will often need to take on a generic form to avoid turning your collection interfaces into monoliths trying to do everything imaginable (ex: an image interface that tries to provide every single image operation imaginable as opposed to just one generic way to transform pixels in bulk).

Similar to the collection interface, your abstract algorithmic functions will likewise tend to start processing data in bulk. For example, instead of this:

boolean some_predicate(element)
void modify_point(point)

... you might have something more like this:

void some_predicate(num_elements, elements[], boolean out_results[])
void modify_points(num_points, points[])

... where the predicate receives more than one element at a time and outputs its results to a boolean array (typically one that's either reused or on the stack for temporal locality across calls to the "bulk" predicate), and transform_points modifies more than one point at a time.

This helps to enable new optimization capabilities for bulk processing like SoA SIMD intrinsics. They also significantly mitigate dynamic dispatch overhead (and the optimization barriers they impose), and can also encourage thread locks at a more appropriate level (not too granular/frequent for overly-light work). Likewise if you ever want to do GPGPU, GPGPU likewise wants data to be fed to it in contiguous bulk, which likewise favors a data-oriented mindset.

In other cases, you might even expose raw chunks of data as plain old data types to process in bulk, or possibly behind safer proxies that return data to process in bulk.

Wiggle Room

The main problem that very granular object-oriented design imposes from a performance standpoint is not the cost of objects, per se. With optimizing C++ compilers, for example, the cost of an object is often free. The optimizer will obliterate away the structure and make things like accessor functions cost nothing at all at runtime.

The difficulty is that modeling something at a granular level like a single Particle will paint you into a data representation corner as the rest of your codebase becomes coupled to the object-oriented interface of a single particle that encapsulates and owns its state. We can no longer apply effective memory optimizations like hot/cold field splitting when there's nothing being aggregated beyond the fields of a single particle. We can't utilize SoA representations, we can't reach around and coalesce data from surrounding particles in a way that goes beyond a straightforward AoS form. We can't obliterate away this structure and just pack it into an array of floats for a very efficient bulk-processing library or hardware to process.

So it's not really about avoiding the cost of user-defined types. Against some compilers at least, user-defined type objects can be free. Yet they're not free in terms of what they do from a design standpoint -- they take away all wiggle room to optimize the data representation further. Collections of elements, on the other hand, leave lots of wiggle room.

It's like if you have a race car, a lot of its speed is going to be wasted if the road is only 10 meters long.

Contiguous Memory

In particular, a heavy DOD mindset will tend to favor bulk processing over contiguous chunks of data -- arrays of elements rather than individual elements being passed one at a time. It's a natural tendency due to the way that hardware favors spatial locality with its CPU cache design, and likewise in part the operating system with the way it physically maps memory through contiguous pages at really large input scales.

Even linked structures may start to take on more partially-contiguous forms, like unrolled lists instead of linked lists, n-ary trees instead of binary trees, in response to measurements and tuning. The alternative is to reach under these data structures and achieve contiguity through the memory allocator, but a data-oriented mindset generally favors contiguity and processing which uses all data in a cache line or physically-mapped page prior to eviction by whatever means possible (memory pools or data structure or combo of both).

Metadata and alignment/padding costs per element will often want to be mitigated and squashed down to a minimum, all in favor of packing more relevant data into a contiguous chunk. Cold data fields which are irrelevant in your critical paths of execution will want to be split away from hot data fields to allow more relevant hot fields to be packed into contiguous chunks so that the machine can consume such data at a faster rate.

Plain Old Data

One of the tendencies that tend to arise with a DOD mindset is a greater appreciation for plain old data types, like int, float, double, short. They're lowest common denominator types that directly communicate the amount of memory required, don't require any coupling to other user-defined types in your system, and can be a universal way of achieving interoperability with other APIs and languages.

With DOD, there tends to be significantly reduced coupling in your system as you end up turning those granular object-oriented designs like Pixel or Particle into implementation details, no longer complex objects of their own.

In complex codebases embracing a granular object-oriented mindeset, a lot of coupling tends to be in the form of message passing of more complex user-defined parameter types, like a single Rect, a single Point, etc. With DOD, those teeny structures tend to be demolished in favor of plain old data types, arrays of them, or at least simpler structures, and that can result in a significant amount of decoupling and more independent interfaces.

Through such independence often comes a more timeless quality about your code, since plain old data types don't go out of style. A very complex and bulky expression template linear algebra library might go out of style a lot faster than an array of floats or doubles. The interfaces associated with POD types tend to be less expressive and more inconvenient, but that timeless quality that comes from very decoupled and independent designs can make up for it if you're seeking designs that last a very long time and can be deployed and reused easily in various projects over the years to come.

Stride

For the greatest level of flexibility and stability in your performance-critical interfaces, it can be helpful to accept stride parameters to indicate the stride size to get from one field to the next, like so:

void process_points(int num_points, float xyz[], int stride)

... even more flexible might separate the fields away from an AoS (array of structures) mindset, like so:

void process_points(int num_points, 
                    float x[], float y[], float z[],
                    int x_stride, int y_stride, int z_stride)

... this allows even SoA (structure of array) representations to be squeezed through this interface directly without forming some kind of temporary array, and also allows the implementors of these abstract functions to potentially utilize SoA SIMD optimizations when the x/y/z strides indicate that these fields are contiguous in nature (xxxxxxxx yyyyyyyy zzzzzzzz etc).

This is getting pretty inconvenient to use, however, so it may be worth wrapping these to a more complex and bundled parameter type if this degree of representation flexibility is needed.

In spite of the inconvenience at the implementation level, interface designs which accept data in bulk with stride parameters can achieve tremendous stability with performance being stricken completely from the list of reasons to change.

Data Structures

A lot of data-oriented design discussions will go very quickly into memory and SIMD and multithreading and GPU-level micro-optimizations, but solely because they're the most counter-intuitive and something that isn't often quite as big of a focus in computer science and SE courses.

Yet of course, if you are designing a raytracer, the first thing to think about is your acceleration data structure like a K-D tree or bounding volume hierarchy. Micro-optimizations like ray packets for SIMD are secondary in nature. If you are designing a video game with a bunch of sprites with collision detection, probably the first thing to think about is a spatial indexing accelerator which is going to accelerate the collision detection. The same concept applies, nevertheless, at the interface level. Whether the priority is data structures first and memory layouts second or vice versa (ex: in places that cannot do better than linear complexity), the DOD mindset considers data first.

Python

It seems kind of unusual to encounter a Python developer evolving a data-oriented mindset. Some of the techniques mentioned above like using interfaces with a stride may be inapplicable without pointers and the ability to kind of dangerously work at the bits and bytes level. SoA SIMD intrinsics might be out (at least at the hand-written level, not sure about the ability for Python optimizers to generate vectorized instructions from an SoA memory access pattern).

Nevertheless, the overall concepts related to interface design and thinking about data should apply, and concepts like cache-friendliness and memory optimization apply regardless of the language. It may help at least at the level of helping you design interfaces and data representations that you can pass through in bulk to native C APIs like numpy.

DOD should be applicable to all languages since the hardware characteristics and the nature of data structures don't change across languages. Some languages might not let you get to quite the same level of explicit control over memory representation and micro-optimization, e.g., but we're still unified by the same hardware, memory hierarchy, a need for interface designs that don't have to change to seek higher performance.

If you can't do much in the way of memory allocators, for example, you can do more at the data structure level. It's all a blur anyway between data structures and memory pools. You might use a data structure which favors storing nodes directly in an array with indices, for example, instead of using a memory allocator to achieve spatial locality underneath the data structure.

Anyway, I hope some of this above will help a bit. There's nothing wrong with data-oriented design, as it can be the most effective and productive way to design things that handle a heavy load. It does tend to push implementations to a lower, more difficult level (though interfaces can remain fairly high-level, and sometimes even higher-level than interfaces that deal with a scalar, "one little element at a time" mindset). As a result, the cost of implementing under data-oriented design tends to increase upfront and the need for testing increases with often-reduced type safety, though the bigger, large-scale maintenance costs associated with interface instability go away if the interfaces to which you are applying a data-oriented design mindset truly handle a heavy load.

11 deleted 16419 characters in body
source | link

As you can see, the OOP way gives me a lot of security that people won't be adding Volatility the wrong way, but the vector method is just so crazy fast! Is there a design in which I can get both? I am sure a lot of you have run into similar design choices, how did you work it out?

It sounds to me like your needs are driving you towards data-oriented design, which is pretty exciting since I don't think I've met too many Python developers who have developed that inclination out of their measurements. For designs where performance is the top goal, it's often a very powerful way of going about design.

It's a common mindset among developers working with tight resources or need frugality anyway because speed is one of the most competitive qualities of their product. It is a very effective design strategy when applied carefully to the areas of a codebase that truly handle a heavy load.

If you wish to pursue data-oriented design, I might be able to offer some tips as one who has been applying this basic mindset from the beginning (started out in C on DOS with very tight resources and it just seemed like the most natural way to design software back then).

It's also worth noting that it's not incompatible at all with object-oriented programming, only very granular object-oriented programming.

Data-Oriented Design

Data-oriented design tackles design and architecture from the data side of the picture. Instead of thinking about operations and entities first, we think more about data. "This program simulates a boatload of particles, and particles need these data fields." Operations and algorithms are secondary to data structures and memory layouts, since the first interact with the second from this data-centric point of view.

Data-oriented designers tend to communicate their designs primarily through the data representations and/or data structures, somewhat leaving the public interface/operations to the imagination, like so with C-style pseudocode:

struct Particles
{
    struct ParticleHot
    {
        // AoSoA representation (hot fields) -- YMM register alignment.
        ALIGN32 float x[8];
        ALIGN32 float y[8];
        ALIGN32 float z[8];
    };
    struct ParticleCold
    {
        // Fields not accessed in critical loops (cold fields).
        float size;
        int id;
    };
    struct ParticleHot particles_hot[ceil_int(n / 8)];
    struct ParticleCold particles_cold[n];
};

This might seem backwards with an unhealthy focusWorking on implementation details, but the goal here is still design, namely interface design. Thinking about the data first is still more of an exercise to help us think about the right things when trying to produce public interface designs for performance-critical areas.

Interface Stability

In complex performance-critical codebases, an interface design can conform beautifully to SOLID engineering principles and still find plenty of instability where the number one reason for a design to change becomes a greater need for performance.

The result can be otherwise well-engineered interfaces having to become deprecateddeleting my posts with slow cascading transformations of the codebase, or jarring cascading breakages (if no deprecation strategy is sought out) towards new interfaces simply for added performance.

Embracing a data-oriented mindset can significantly counter that and lead to very stable designs even when performance is a very high-priority design goal. It leads to designs that offer all the wiggle room you need to iterate towards faster and faster solutions without changing the design whatsoever, only the implementation behind it.

It's worth keeping this in mindpositive answers. The goal isn'tGoing to try to come up with the fastest implementation possible on the first try, if ever (this could easily start to become very counter-productive), but more to come up with a stable interface that won't ever have "performance" among its reasons to change. For implementations, performance is still something we tend to iterate towards with a profiler in hand, and seeking the absolute peak ideal is often undesirable as optimizations start to yield diminishing returns while rapidly degrading maintainability as you start scraping metal.

Collection Interfaces

As noted, data-oriented design isn't incompatible with object-oriented design, only very granular object-oriented design. It's because a lot of granular structure will be demolished through the DOD process.

Granular entities like Pixel, Particle, Point, Rect, possibly even Sprite or Person will turn into implementation details: raw data behind some collection interface like Image, ParticleSystem, Points, Rects, SpriteHandler, People.

It sounds to me like your Volatility structure is likewise too granular and needs to be demolished in favor of an object-oriented interface modeling a collection of these.

Public interfaces will start to handle data in bulk, not in little teeny scalar pieces.

Bulk Algorithms

Related to the idea of a collection interface, algorithms like transform algorithms will often need to take on a generic form to avoid turning your collection interfaces into monoliths trying to do everything imaginable (ex: an image interface that tries to provide every single image operation imaginable as opposed to just one generic way to transform pixels in bulk).

Similar to the collection interface, your abstract algorithmic functions will likewise tend to start processing data in bulk. For example, instead of this:

boolean some_predicate(element)
void modify_point(point)

... you might have something more like this:

void some_predicate(num_elements, elements[], boolean out_results[])
void modify_points(num_points, points[])

... where the predicate receives more than one element at a time and outputs its results to a boolean array (typically one that's either reused or on the stack for temporal locality across calls to the "bulk" predicate), and transform_points modifies more than one point at a time.

This helps to enable new optimization capabilities for bulk processing like SoA SIMD intrinsics. They also significantly mitigate dynamic dispatch overhead (and the optimization barriers they impose), and can also encourage thread locks at a more appropriate level (not too granular/frequent for overly-light work). Likewise if you ever want to do GPGPU, GPGPU likewise wants data to be fed to it in contiguous bulk, which likewise favors a data-oriented mindset.

In other cases, you might even expose raw chunks of data as plain old data types to process in bulk, or possibly behind safer proxies that return data to process in bulk.

Wiggle Room

The main problem that very granular object-oriented design imposes from a performance standpoint is not the cost of objects, per se. With optimizing C++ compilers, for example, the cost of an object is often free. The optimizer will obliterate away the structure and make things like accessor functions cost nothing at all at runtime.

The difficulty is that modeling something at a granular level like a single Particle will paint you into a data representation corner as the rest of your codebase becomes coupled to the object-oriented interface of a single particle that encapsulates and owns its state. We can no longer apply effective memory optimizations like hot/cold field splitting when there's nothing being aggregated beyond the fields of a single particle. We can't utilize SoA representations, we can't reach around and coalesce data from surrounding particles in a way that goes beyond a straightforward AoS form. We can't obliterate away this structure and just pack it into an array of floats for a very efficient bulk-processing library or hardware to process.

So it's not really about avoiding the cost of user-defined types. Against some compilers at least, user-defined type objects can be free. Yet they're not free in terms of what they do from a design standpoint -- they take away all wiggle room to optimize the data representation further. Collections of elements, on the other hand, leave lots of wiggle room.

It's like if you have a race car, a lot of its speed is going to be wasted if the road is only 10 meters long.

Contiguous Memory

In particular, a heavy DOD mindset will tend to favor bulk processing over contiguous chunks of data -- arrays of elements rather than individual elements being passed one at a time. It's a natural tendency due to the way that hardware favors spatial locality with its CPU cache design, and likewise in part the operating system with the way it physically maps memory through contiguous pages at really large input scales.

Even linked structures may start to take on more partially-contiguous forms, like unrolled lists instead of linked lists, n-ary trees instead of binary trees, in response to measurements and tuning. The alternative is to reach under these data structures and achieve contiguity through the memory allocator, but a data-oriented mindset generally favors contiguity and processing which uses all data in a cache line or physically-mapped page prior to eviction by whatever means possible (memory pools or data structure or combo of both).

Metadata and alignment/padding costs per element will often want to be mitigated and squashed down to a minimum, all in favor of packing more relevant data into a contiguous chunk. Cold data fields which are irrelevant in your critical paths of execution will want to be split away from hot data fields to allow more relevant hot fields to be packed into contiguous chunks so that the machine can consume such data at a faster rate.

Plain Old Data

One of the tendencies that tend to arise with a DOD mindset is a greater appreciation for plain old data types, like int, float, double, short. They're lowest common denominator types that directly communicate the amount of memory required, don't require any coupling to other user-defined types in your system, and can be a universal way of achieving interoperability with other APIs and languages.

With DOD, there tends to be significantly reduced coupling in your system as you end up turning those granular object-oriented designs like Pixel or Particle into implementation details, no longer complex objects of their own.

In complex codebases embracing a granular object-oriented mindeset, a lot of coupling tends to be in the form of message passing of more complex user-defined parameter types, like a single Rect, a single Point, etc. With DOD, those teeny structures tend to be demolished in favor of plain old data types, arrays of them, or at least simpler structures, and that can result in a significant amount of decoupling and more independent interfaces.

Through such independence often comes a more timeless quality about your code, since plain old data types don't go out of style. A very complex and bulky expression template linear algebra library might go out of style a lot faster than an array of floats or doubles. The interfaces associated with POD types tend to be less expressive and more inconvenient, but that timeless quality that comes from very decoupled and independent designs can make up for it if you're seeking designs that last a very long time and can be deployed and reused easily in various projects over the years to come.

Stride

For the greatest level of flexibility and stability in your performance-critical interfaces, it can be helpful to accept stride parameters to indicate the stride size to get from one field to the next, like so:

void process_points(int num_points, float xyz[], int stride)

... even more flexible might separate the fields away from an AoS (array of structures) mindset, like so:

void process_points(int num_points, 
                    float x[], float y[], float z[],
                    int x_stride, int y_stride, int z_stride)

... this allows even SoA (structure of array) representations to be squeezed through this interface directly without forming some kind of temporary array, and also allows the implementors of these abstract functions to potentially utilize SoA SIMD optimizations when the x/y/z strides indicate that these fields are contiguous in nature (xxxxxxxx yyyyyyyy zzzzzzzz etc).

This is getting pretty inconvenient to use, however, so it may be worth wrapping these to a more complex and bundled parameter type if this degree of representation flexibility is needed.

In spite of the inconvenience at the implementation level, interface designs which accept data in bulk with stride parameters can achieve tremendous stability with performance being stricken completely from the list of reasons to change.

Data Structures

A lot of data-oriented design discussions will go very quickly into memory and SIMD and multithreading and GPU-level micro-optimizations, but solely because they're the most counter-intuitive and something that isn't often quite as big of a focus in computer science and SE courses.

Yet of course, if you are designing a raytracer, the first thing to think about is your acceleration data structure like a K-D tree or bounding volume hierarchy. Micro-optimizations like ray packets for SIMD are secondary in nature. If you are designing a video game with a bunch of sprites with collision detection, probably the first thing to think about is a spatial indexing accelerator which is going to accelerate the collision detection. The same concept applies, nevertheless, at the interface level. Whether the priority is data structures first and memory layouts second or vice versa (ex: in places that cannot do better than linear complexity), the DOD mindset considers data first.

Python

It seems kind of unusual to encounter a Python developer evolving a data-oriented mindset. Some of the techniques mentioned above like using interfaces with a stride may be inapplicable without pointers and the ability to kind of dangerously work at the bits and bytes level. SoA SIMD intrinsics might be out (at least at the hand-written level, not sure about the ability for Python optimizers to generate vectorized instructions from an SoA memory access pattern).

Nevertheless, the overall concepts related to interface design and thinking about data should apply, and concepts like cache-friendliness and memory optimization apply regardless of the language. It may help at least at the level of helping you design interfaces and data representations that you can pass through in bulk to native C APIs like numpy.

DOD should be applicable to all languages since the hardware characteristics and the nature of data structures don't change across languages. Some languages might not let you get to quite the same level of explicit control over memory representation and micro-optimization, e.g., but we're still unified by the same hardware, memory hierarchy, a need for interface designs that don't have to change to seek higher performance.

If you can't do much in the way of memory allocators, for example, you can do more at the data structure level. It's all a blur anyway between data structures and memory pools. You might use a data structure which favors storing nodes directly in an array with indices, for example, instead of using a memory allocator to achieve spatial locality underneath the data structure.

Anyway, I hope some of this above will help a bit. There's nothing wrong with data-oriented design, as it can be the most effective and productive way to design things that handle a heavy load. It does tend to push implementations to a lower, more difficult level (though interfaces can remain fairly high-level, and sometimes even higher-level than interfaces that deal with a scalar, "one little element at a time" mindset). As a result, the cost of implementing under data-oriented design tends to increase upfront and the need for testing increases with often-reduced type safety, though the bigger, large-scale maintenance costs associated with interface instability go away if the interfaces to which you are applying a data-oriented design mindset truly handle a heavy load.maximum negative votes!

As you can see, the OOP way gives me a lot of security that people won't be adding Volatility the wrong way, but the vector method is just so crazy fast! Is there a design in which I can get both? I am sure a lot of you have run into similar design choices, how did you work it out?

It sounds to me like your needs are driving you towards data-oriented design, which is pretty exciting since I don't think I've met too many Python developers who have developed that inclination out of their measurements. For designs where performance is the top goal, it's often a very powerful way of going about design.

It's a common mindset among developers working with tight resources or need frugality anyway because speed is one of the most competitive qualities of their product. It is a very effective design strategy when applied carefully to the areas of a codebase that truly handle a heavy load.

If you wish to pursue data-oriented design, I might be able to offer some tips as one who has been applying this basic mindset from the beginning (started out in C on DOS with very tight resources and it just seemed like the most natural way to design software back then).

It's also worth noting that it's not incompatible at all with object-oriented programming, only very granular object-oriented programming.

Data-Oriented Design

Data-oriented design tackles design and architecture from the data side of the picture. Instead of thinking about operations and entities first, we think more about data. "This program simulates a boatload of particles, and particles need these data fields." Operations and algorithms are secondary to data structures and memory layouts, since the first interact with the second from this data-centric point of view.

Data-oriented designers tend to communicate their designs primarily through the data representations and/or data structures, somewhat leaving the public interface/operations to the imagination, like so with C-style pseudocode:

struct Particles
{
    struct ParticleHot
    {
        // AoSoA representation (hot fields) -- YMM register alignment.
        ALIGN32 float x[8];
        ALIGN32 float y[8];
        ALIGN32 float z[8];
    };
    struct ParticleCold
    {
        // Fields not accessed in critical loops (cold fields).
        float size;
        int id;
    };
    struct ParticleHot particles_hot[ceil_int(n / 8)];
    struct ParticleCold particles_cold[n];
};

This might seem backwards with an unhealthy focus on implementation details, but the goal here is still design, namely interface design. Thinking about the data first is still more of an exercise to help us think about the right things when trying to produce public interface designs for performance-critical areas.

Interface Stability

In complex performance-critical codebases, an interface design can conform beautifully to SOLID engineering principles and still find plenty of instability where the number one reason for a design to change becomes a greater need for performance.

The result can be otherwise well-engineered interfaces having to become deprecated with slow cascading transformations of the codebase, or jarring cascading breakages (if no deprecation strategy is sought out) towards new interfaces simply for added performance.

Embracing a data-oriented mindset can significantly counter that and lead to very stable designs even when performance is a very high-priority design goal. It leads to designs that offer all the wiggle room you need to iterate towards faster and faster solutions without changing the design whatsoever, only the implementation behind it.

It's worth keeping this in mind. The goal isn't to try to come up with the fastest implementation possible on the first try, if ever (this could easily start to become very counter-productive), but more to come up with a stable interface that won't ever have "performance" among its reasons to change. For implementations, performance is still something we tend to iterate towards with a profiler in hand, and seeking the absolute peak ideal is often undesirable as optimizations start to yield diminishing returns while rapidly degrading maintainability as you start scraping metal.

Collection Interfaces

As noted, data-oriented design isn't incompatible with object-oriented design, only very granular object-oriented design. It's because a lot of granular structure will be demolished through the DOD process.

Granular entities like Pixel, Particle, Point, Rect, possibly even Sprite or Person will turn into implementation details: raw data behind some collection interface like Image, ParticleSystem, Points, Rects, SpriteHandler, People.

It sounds to me like your Volatility structure is likewise too granular and needs to be demolished in favor of an object-oriented interface modeling a collection of these.

Public interfaces will start to handle data in bulk, not in little teeny scalar pieces.

Bulk Algorithms

Related to the idea of a collection interface, algorithms like transform algorithms will often need to take on a generic form to avoid turning your collection interfaces into monoliths trying to do everything imaginable (ex: an image interface that tries to provide every single image operation imaginable as opposed to just one generic way to transform pixels in bulk).

Similar to the collection interface, your abstract algorithmic functions will likewise tend to start processing data in bulk. For example, instead of this:

boolean some_predicate(element)
void modify_point(point)

... you might have something more like this:

void some_predicate(num_elements, elements[], boolean out_results[])
void modify_points(num_points, points[])

... where the predicate receives more than one element at a time and outputs its results to a boolean array (typically one that's either reused or on the stack for temporal locality across calls to the "bulk" predicate), and transform_points modifies more than one point at a time.

This helps to enable new optimization capabilities for bulk processing like SoA SIMD intrinsics. They also significantly mitigate dynamic dispatch overhead (and the optimization barriers they impose), and can also encourage thread locks at a more appropriate level (not too granular/frequent for overly-light work). Likewise if you ever want to do GPGPU, GPGPU likewise wants data to be fed to it in contiguous bulk, which likewise favors a data-oriented mindset.

In other cases, you might even expose raw chunks of data as plain old data types to process in bulk, or possibly behind safer proxies that return data to process in bulk.

Wiggle Room

The main problem that very granular object-oriented design imposes from a performance standpoint is not the cost of objects, per se. With optimizing C++ compilers, for example, the cost of an object is often free. The optimizer will obliterate away the structure and make things like accessor functions cost nothing at all at runtime.

The difficulty is that modeling something at a granular level like a single Particle will paint you into a data representation corner as the rest of your codebase becomes coupled to the object-oriented interface of a single particle that encapsulates and owns its state. We can no longer apply effective memory optimizations like hot/cold field splitting when there's nothing being aggregated beyond the fields of a single particle. We can't utilize SoA representations, we can't reach around and coalesce data from surrounding particles in a way that goes beyond a straightforward AoS form. We can't obliterate away this structure and just pack it into an array of floats for a very efficient bulk-processing library or hardware to process.

So it's not really about avoiding the cost of user-defined types. Against some compilers at least, user-defined type objects can be free. Yet they're not free in terms of what they do from a design standpoint -- they take away all wiggle room to optimize the data representation further. Collections of elements, on the other hand, leave lots of wiggle room.

It's like if you have a race car, a lot of its speed is going to be wasted if the road is only 10 meters long.

Contiguous Memory

In particular, a heavy DOD mindset will tend to favor bulk processing over contiguous chunks of data -- arrays of elements rather than individual elements being passed one at a time. It's a natural tendency due to the way that hardware favors spatial locality with its CPU cache design, and likewise in part the operating system with the way it physically maps memory through contiguous pages at really large input scales.

Even linked structures may start to take on more partially-contiguous forms, like unrolled lists instead of linked lists, n-ary trees instead of binary trees, in response to measurements and tuning. The alternative is to reach under these data structures and achieve contiguity through the memory allocator, but a data-oriented mindset generally favors contiguity and processing which uses all data in a cache line or physically-mapped page prior to eviction by whatever means possible (memory pools or data structure or combo of both).

Metadata and alignment/padding costs per element will often want to be mitigated and squashed down to a minimum, all in favor of packing more relevant data into a contiguous chunk. Cold data fields which are irrelevant in your critical paths of execution will want to be split away from hot data fields to allow more relevant hot fields to be packed into contiguous chunks so that the machine can consume such data at a faster rate.

Plain Old Data

One of the tendencies that tend to arise with a DOD mindset is a greater appreciation for plain old data types, like int, float, double, short. They're lowest common denominator types that directly communicate the amount of memory required, don't require any coupling to other user-defined types in your system, and can be a universal way of achieving interoperability with other APIs and languages.

With DOD, there tends to be significantly reduced coupling in your system as you end up turning those granular object-oriented designs like Pixel or Particle into implementation details, no longer complex objects of their own.

In complex codebases embracing a granular object-oriented mindeset, a lot of coupling tends to be in the form of message passing of more complex user-defined parameter types, like a single Rect, a single Point, etc. With DOD, those teeny structures tend to be demolished in favor of plain old data types, arrays of them, or at least simpler structures, and that can result in a significant amount of decoupling and more independent interfaces.

Through such independence often comes a more timeless quality about your code, since plain old data types don't go out of style. A very complex and bulky expression template linear algebra library might go out of style a lot faster than an array of floats or doubles. The interfaces associated with POD types tend to be less expressive and more inconvenient, but that timeless quality that comes from very decoupled and independent designs can make up for it if you're seeking designs that last a very long time and can be deployed and reused easily in various projects over the years to come.

Stride

For the greatest level of flexibility and stability in your performance-critical interfaces, it can be helpful to accept stride parameters to indicate the stride size to get from one field to the next, like so:

void process_points(int num_points, float xyz[], int stride)

... even more flexible might separate the fields away from an AoS (array of structures) mindset, like so:

void process_points(int num_points, 
                    float x[], float y[], float z[],
                    int x_stride, int y_stride, int z_stride)

... this allows even SoA (structure of array) representations to be squeezed through this interface directly without forming some kind of temporary array, and also allows the implementors of these abstract functions to potentially utilize SoA SIMD optimizations when the x/y/z strides indicate that these fields are contiguous in nature (xxxxxxxx yyyyyyyy zzzzzzzz etc).

This is getting pretty inconvenient to use, however, so it may be worth wrapping these to a more complex and bundled parameter type if this degree of representation flexibility is needed.

In spite of the inconvenience at the implementation level, interface designs which accept data in bulk with stride parameters can achieve tremendous stability with performance being stricken completely from the list of reasons to change.

Data Structures

A lot of data-oriented design discussions will go very quickly into memory and SIMD and multithreading and GPU-level micro-optimizations, but solely because they're the most counter-intuitive and something that isn't often quite as big of a focus in computer science and SE courses.

Yet of course, if you are designing a raytracer, the first thing to think about is your acceleration data structure like a K-D tree or bounding volume hierarchy. Micro-optimizations like ray packets for SIMD are secondary in nature. If you are designing a video game with a bunch of sprites with collision detection, probably the first thing to think about is a spatial indexing accelerator which is going to accelerate the collision detection. The same concept applies, nevertheless, at the interface level. Whether the priority is data structures first and memory layouts second or vice versa (ex: in places that cannot do better than linear complexity), the DOD mindset considers data first.

Python

It seems kind of unusual to encounter a Python developer evolving a data-oriented mindset. Some of the techniques mentioned above like using interfaces with a stride may be inapplicable without pointers and the ability to kind of dangerously work at the bits and bytes level. SoA SIMD intrinsics might be out (at least at the hand-written level, not sure about the ability for Python optimizers to generate vectorized instructions from an SoA memory access pattern).

Nevertheless, the overall concepts related to interface design and thinking about data should apply, and concepts like cache-friendliness and memory optimization apply regardless of the language. It may help at least at the level of helping you design interfaces and data representations that you can pass through in bulk to native C APIs like numpy.

DOD should be applicable to all languages since the hardware characteristics and the nature of data structures don't change across languages. Some languages might not let you get to quite the same level of explicit control over memory representation and micro-optimization, e.g., but we're still unified by the same hardware, memory hierarchy, a need for interface designs that don't have to change to seek higher performance.

If you can't do much in the way of memory allocators, for example, you can do more at the data structure level. It's all a blur anyway between data structures and memory pools. You might use a data structure which favors storing nodes directly in an array with indices, for example, instead of using a memory allocator to achieve spatial locality underneath the data structure.

Anyway, I hope some of this above will help a bit. There's nothing wrong with data-oriented design, as it can be the most effective and productive way to design things that handle a heavy load. It does tend to push implementations to a lower, more difficult level (though interfaces can remain fairly high-level, and sometimes even higher-level than interfaces that deal with a scalar, "one little element at a time" mindset). As a result, the cost of implementing under data-oriented design tends to increase upfront and the need for testing increases with often-reduced type safety, though the bigger, large-scale maintenance costs associated with interface instability go away if the interfaces to which you are applying a data-oriented design mindset truly handle a heavy load.

Working on deleting my posts with positive answers. Going to try for maximum negative votes!

10 deleted 2 characters in body
source | link
9 added 177 characters in body
source | link
8 added 381 characters in body
source | link
7 added 1304 characters in body
source | link
6 added 463 characters in body
source | link
5 added 2 characters in body
source | link
4 added 2 characters in body
source | link
3 added 2 characters in body
source | link
2 added 23 characters in body
source | link
1
source | link