6

I'm currently in a high-performance computing class taught in C++. Usually, I do work in C#, meaning everything is taken care of for me, and optimization comes behind maintainability and higher-level features. It's like... a nice productivity furnace that keeps me nice and warm in the programming project winter at the expense of my CPU cycle/cache miss electricity bill. However, now that I'm in C++ and efficient algorithm land, that stuff takes a back seat to optimization.

Since most of my work has been in C#, object-oriented programming is sort of my style. However, I have been reading/hearing more and more about how object-oriented code is an enemy of performance. As my understanding of software architecture shifts from being exclusively about class structure and encapsulation to understanding how things are disposed of from L1 cache and pipelining, I'm trying to understand the real reasons why object-oriented design (especially as it applies to C++) causes waste of hardware resources. Can you guys give me a few basic reasons why it impacts computer performance? I know there are other debates about OOP, but I'd like to just keep it to performance on a hardware and algorithmic level.

  • 2
    Everything definitely isn't "taken care of" for you in C#. Writing truly performant C# code you will definitely teach a person that. – Rig Feb 9 '14 at 22:38
8

Many of the OOP's performance problems come from indirection caused by inheritance and virtual methods. The virtual methods are problematic because:

  • They take more time because of virtual table lookup
  • Cannot be properly optimized, eg. using inlining for example. Or at least it is too hard to do it.
  • In some languages, they are forced to be reference types, so when you have many of them, they are scattered in memory instead of continuous block, hurting cache.

If you remove this, you will loose major point of using OOP, like modularity or extensibility, but you will gain a performance. The major advantage of C++ (especially compared to Java and C#) is you can pick where you want this indirection and where you want non-OOP way of doing things. You could do this in C#, but it is not that nice and easy as in C++.

  • Sidenote: Modularity and extensibility in OOP are not dependent on inheritance (source of virtual table lookup). – Jack Jan 15 '16 at 1:46
  • @Jack And how else can those be achieved? Delegates are not OOP construct (and can be converted to classes) and interface is just pure abstract class. – Euphoric Jan 15 '16 at 7:16
  • @Eupohoric Claiming a single language feature like inheritance is the only way to achieve an abstract design ideal like modularity is never true. Languages, programs, and design are all more complicated than that. – Jack Jan 15 '16 at 7:42
  • @Jack I'm claiming OOP's only way is inheritance. Not language's only way. Multi-paradigm language will have different ways (but they are usually only syntactic sugar, because all indirections can be converted to OOP-based syntax with inheritance and back). – Euphoric Jan 15 '16 at 7:46
  • Even then, "modularity" and "extensibility" are not well defined enough to make that claim. I've worked in OOP projects that felt very modular and easy to extend and had zero inheritance or interfaces. Language features are generally concrete well defined things, design goals and ideals are not - you can't construct absolute claims about things that aren't rigorously defined from things that are. – Jack Jan 15 '16 at 7:51
3

I'll tackle only the design side of the question, not the implementation mechanics (the hot/cold field splitting and SIMD focus below will only be exemplary to highlight the point of what designs will and will not allow further optimizations without cascading interface breakages).

This applies to all languages potentially. The biggest issue if you are going for max performance (and you absolutely shouldn't do this everywhere, a profiler will keep you honest and productive even when efficiency is a critical competitive goal) is a design related one.

// Models the design of a *single* point.
class Point
{
public:
    ...
private:
    float x;   // hot field, accessed sequentially.
    float y;   // hot field, accessed sequentially.
    float z;   // hot field, accessed sequentially.
    char id;   // cold field, rarely accessed.
               // 3 bytes of padding.
};

Such a class gives you little room to optimize for, say, cache efficiency. You'll want to reach around the class and try to find ways to make its data fields interact with other points. A peak efficiency mindset has to do just that, and demolish this structure in favor of something more like this:

// Models the design of *many* points.
class Points
{
public:
    ...
private:
    vector<float> x; // hot field, accessed sequentially.
    vector<float> y; // hot field, accessed sequentially.
    vector<float> z; // hot field, accessed sequentially.
    vector<char> id; // cold field, rarely accessed.
};

... now you're good given the memory access patterns. We're allowing SoA SIMD instructions (either handwritten or compiler-generated) and we've reduced the memory usage for a large number of points by eliminating per-point 3-byte padding without messing with alignment (3 bytes is actually kind of a huge deal when an L1 cache line is 64 bytes and the total size of the L3 cache is just 2 megs per core, e.g., and also relatively a big deal when a point is 13 bytes w/o padding and 16 bytes w/padding, not to mention that only 12 bytes are hot).

Or let's change the dynamics a bit. Let's say your system's most critical loops access points at random, but the id field is still cold. In that case, an AoS representation will do better, and we can change the above without breaking anything externally using the Points class:

class Points
{
public:
    ...
private:
    vector<vec3f> xyz; // hot field, accessed randomly.
    vector<char> id;   // cold field, rarely accessed.
};

The key here is that Points gives you that breathing room to iterate towards faster solutions. You can forget half of what I suggested here about hot/cold field splitting, cache efficiency, padding, SoA SIMD access. I've done this kind of stuff long enough and measured it repeatedly against vtune and benchmarks to know how they pay off (though still reaching for vtune anyway, always). It's not critical to know this stuff upfront so much. The point is that Points gave me that room to optimize, Point didn't. You can even start off with this simple implementation:

// Models the design of *many* points.
class Points
{
public:
    ...
private:
    struct Point
    {
        float x;
        float y;
        float z;
        char id;
    };
    vector<Point> points; // simple representation
};

... doesn't matter, the use of Point here is a private detail you can optimize away later as needed since the rest of the system won't have access to it, only Points.

That's the key above all else: it's designing for performance. Design is something you have to account for upfront. If you know your system is going to be accessing points by the masses (hundreds of thousands to millions repeatedly each frame, e.g.), then the basic design consideration to take into account upfront is whether you design a Point class or a Points class. The latter will give exponentially more breathing room to tweak and tune the hell out of it (not just at the memory optimization level, but also one central target to optimize data structures), Point will leave you trapped with a sub-optimal memory representation.

It's that simple to me, really -- this is the first and biggest step to consider when applying object-oriented design in a performance-critical context, and upfront, since you can't have a codebase that has 10,000 lines of code dependent on a Point interface and then change your mind later without serious grief.

There's other issues like runtime abstraction cost (dynamic dispatch with virtual function calls, dylib calls, std::function, etc) but to me that's kind of petty stuff. If you design your performance-critical interfaces at a coarse level, these concerns become moot -- pennies. When you start dealing with observer patterns with callbacks and things like that, same mentality. We want this:

void (*transform_many_points)(int num_points, float x[], float y[], float z[]);

... more than something like this if we can help it:

void (*transform_one_point)(float& x, float& y, float& z);

... same goes for virtual functions, dylib APIs, etc. If you can process many things at once in a performance-critical context, deal with many things at once. Avoid trapping yourself into the design corner of dealing with teeny little things, accessible only one at a time.

In some cases if your code feels trapped into accessing little teeny things one at a time, one strategy is to have each little access write some trivially-cheap local state. Then, in a deferred process, plow through all the local state of each little thing and process it in a bulk transformation, doing all the heavy-duty work there. If you can't avoid accessing little teeny things one at a time, then simply don't do the heavy-lifting there immediately. Do ultra-light work and defer the heavy-lifting work elsewhere. On top of making it easier to optimize, it'll make it easier to reason about what goes on in your system when you flatten the heavy-lifting work this way and not spread it across little teeny isolated code branches.

It's all design. Object-oriented design is just that, a way of design. And it's only an obstacle to performance if you utilize it to model the most granular objects in the most performance-critical areas, at which point such a design style will trap you into a state representation which cannot possibly get anywhere close to peak efficiency.

If you go further, it's worth looking at concepts like entity-component systems and how they end up flattening systems that process components in bulk (with the most optimized ones often skipping unnecessary components that don't need processing).

But OOP is still plenty applicable for even the most performance-critical applications, the key is to leave yourself breathing room to use more efficient data structures, data representations, and message passing as needed. The desire to encapsulate every little teeny thing into a teeny little object can counteract those goals at the design level.

Understand this, and the rest will take care of itself with a profiler in hand, chasing hotspots and tuning the places that really matter while learning computer architecture and developing that understanding of why these hotspots exist.

2

As was already discussed, virtual functions can hurt performance. Not so much because of the v-table lookup which is extremely fast, but more because of the lost opportunity to inline, which saves function calling overhead and allows the compiler to optimize across function boundaries. Note though, in c++11 the 'final' keyword should allow inline of virtuals. Furthermore, this is only an issue with polymorphism. You don't always use polymorphism when you use OOD.

One of the biggest things in performance nowadays is cache misses. The difference in speed between CPU and RAM has grown a lot over the last decades. A cache miss can cause the CPU to just wait for upwards of 200 cycles, while you grab data. Trying to minimize this is a complicated topic, but one thing that's generally a good idea is this: if you have a tight loop in the critical path, you would ideally like the data being accessed to be stored exactly sequentially with no gaps. The CPU is actually quite smart, and will notice you are retrieving data sequentially. This means it will actually prefetch data and prevent you from cache missing, even on data that's never been requested yet!

OOD however pushes you towards a certain memory layout. For instance, suppose you have an object of class A, with members x, y, and z. These are all important. But the critical path of your program consists of performing some operation on an enormous array of A's, just on members x and y. Those z's are potentially hurting your performance, because they are useless gaps in the storage. If z is a very large type this could increase branch misses substantially.

Note that if you do use polymorphism, the above example becomes much more horrible: instead of an array of A's by value, you would have an array of pointers to A. Now your data is all over the place, which sucks.

It is still possible in many places to use OOD patterns but in a way that is conscious of these issues. For instance, one pattern I've used several times is generating "Op" objects. If you have a very defined critical path, then any code before or after this critical path is basically free. If your A contains lots of important information e.g. for configuration or setup purposes, it may be nice to create a leaner object with only necessary, properly arranged data for the loop in the critical path. I often call this class A_Op or similar, and give A a method that emits its "Op" class.

Edit: I would be remiss not to briefly mention templates here. Templates let you perform similar abstractions to OOD, but with zero run-time cost. A well known example is compile-time polymorphism (not true polymorphism in some sense) via curiously recurring template pattern. Or policy based design.

-3

When doing any kind of software design, it is important to be aware of "Premature Optimization". The first rule is to be correct. Only after you can be assured of correctness through a complete set of unit tests, should you consider performance.

Performance is achieved through testing. Test your algorithms once they are functional to determine if additional performance is required.

  • 3
    I think this is good advice, but I don't see what it has to do with the question. – Brian Snow Feb 9 '14 at 22:50

Your Answer

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

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