Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am torn between object oriented and vector based design. I love the abilities, structure and safety that objects give to the whole architecture. But at the same time, speed is very important to me, and having simple float variables in an array really helps in vector based languages/ libraries like Matlab or numpy in Python.

Here is a piece of code I wrote to illustrate my point

Problem: Adding Tow volatility numbers. If x and y are two volatility numbers, the sum of the volatility is (x^2 + y^2)^0.5 (assuming certain mathematical condition but that's not important here).

I want to perform this operation very fast, and at the same time I need to ensure that people don't just add the volatility in the wrong way (x+y). Both of these are important.

The OO based design would be something like this:

from datetime import datetime 
from pandas import *

class Volatility:
    def __init__(self,value):
       self.value = value

    def __str__(self):
       return "Volatility: "+ str(self.value)

    def __add__(self,other):
        return Volatility(pow(self.value*self.value + other.value*other.value, 0.5))

(Aside: For those who are new to Python, __add__ is just a function that overrides the + operator)

Let's say I add tow lists of volatility values

n = 1000000
vs1 = Series(map(lambda x: Volatility(2*x-1.0), range(0,n)))
vs2 = Series(map(lambda x: Volatility(2*x+1.0), range(0,n))) 

(Aside: Again, a Series in Python is sort of a list with an index) Now I want to add the two:

t1 = datetime.now()
vs3 = vs1 + vs2
t2 = datetime.now()
print t2-t1

Just the addition runs in 3.8 seconds on my machine, the results I have given doesn't include the object initializaion time at all, its only the addition code that has been timed. If I run the same thing using numpy arrays:

nv1 = Series(map(lambda x: 2.0*x-1.0, range(0,n)))
nv2 = Series(map(lambda x: 2.0*x+1.0, range(0,n)))

t3 = datetime.now()
nv3 = numpy.sqrt((nv1*nv1+nv2*nv2))
t4 = datetime.now()
print t4-t3

It runs in 0.03 seconds. That's more than 100 times faster!

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?

The choice of language here is immaterial. I know a lot of you would advise that use C++ or Java, and the code may run faster than vector based languages anyway. But that's not the point. I need to use Python, because I have a host of libraries not available in other languages. That's my constraint. I need to optimize within it.

And I know, that a lot of people would suggest parallelization, gpgpu etc. But I want to maximize single core performance first, and then I can parallelize both the versions of code.

Thanks in advance!

share|improve this question
3  
A closely related way to think about this problem: Should you use a structure of arrays (SoA) or an array of structures (AoS) for performance? With SoA being easier to vectorize and AoS being more OOP friendly in most languages. – Patrick Jun 4 '13 at 5:45
    
yes @Patrick, if you see the first answer, I think Bart gave a practical example of the point you are making. Am I right? I notice you say most languages, so are there languages where both are close in performance? – Ramanuj Lal Jun 4 '13 at 10:45
    
Algorithms + Data Structures = Programs by Niklaus Wirth – radarbob Jan 5 at 18:42

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.

share|improve this answer

This is one of those areas where it is impossible to give definitive answers, because it concerns a trade-off. As you found out, neither OO, nor vector-based is always superior, but it all depends on how the software will be used.

You could try to combine the best of both and create both a Volatility object and a VolatilitySeries object, where the second conceptually represents a Series of Volatility objects, but internally uses a storage method that is much better suited for vectorizing the computations (a structure of arrays). Then you just have to educate your users that using VolatilitySeries is much preferable over Series(Volatility).

share|improve this answer
    
Thanks Bart, that's a good idea. In fact I have gone that way in my current design in parts, where some objects like monetary amounts were redesigned that way. But soon I realized that my code becomes a slave of that particular data structure. For e.g. If I have a VolatilitySeries as you suggest, then I cannot have a list, or a tuple or (assuming you are familiar with Python) a DataFrame of volatility items. That bothers me, because then my architecture doesn't scale well, and the benefits fade away after a while. And that is what brings me here :). – Ramanuj Lal Jun 4 '13 at 10:46
    
The other issue is that nothing is stopping anyone to write a code like volatilitySeries[0] + 3.0, which will be wrong. Once you wriggle out values from VolatilitySeries, you can go berserk, so safety is only short lived. In a polymorphic environment where people are not always aware of the exact class being used, this is highly possible. And you know, you can only educate your users so much. I know you will say that, hey I can also do the same thing if I wriggle out Volatility.value, but you know, at least the user is aware now that he is using a special value. – Ramanuj Lal Jun 4 '13 at 10:55
    
Some may also suggest that override all those usual functions inherited from Series in VolatilitySeries, but that defeats the whole purpose. So what I have learnt from going down that path is that having a VolatilitySeries object only really works out in the long run if the individual cells are of type Volatility. – Ramanuj Lal Jun 4 '13 at 10:57
    
@RamanujLal: I don't know python well enough to determine if the VolatileSeries approach is viable. If you already tried it and it did not work, then you have a hard choice to make between safety and speed. We can't help you there. (unless someone else has a brilliant answer) – Bart van Ingen Schenau Jun 4 '13 at 13:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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