Strict OO principles vs. speed

Quote:

Original post by BattleMetalChris I've been told that in games programming, a lot of OO principles such as encapsulation are mercilessly ignored in favour of having things run as fast as possible? Is there any truth to this and to what extent can you get away with bending the rules?

I think if you don't know when to "break the rules" then you shouldn't even contemplate it. I remember an episode of House where Dr House was getting in trouble because he's constantly flaunting the rules. The officer-dude said, "the rules are in place because 95% of the time, for 95% of people, they're the right thing to do." And Cuddy (or one of the other doctors) said, "yeah, but what about that other 5%?". "Everybody thinks they're that 5%."

Very few games actually "stretch computing power to the limit", and the benefit of using good design principles (not just "OO") will almost always outweigh the cost of maintaining a mess of code that might be 0.5% faster under certain conditions...

Quote:

Original post by Codeka I remember an episode of House where Dr House was getting in trouble because he's constantly flaunting the rules. The officer-dude said, "the rules are in place because 95% of the time, for 95% of people, they're the right thing to do." And Cuddy (or one of the other doctors) said, "yeah, but what about that other 5%?". "Everybody thinks they're that 5%."

hehe, I'm going to rememeber that quote :D

Quote:

Original post by BattleMetalChris I've been told that in games programming, a lot of OO principles such as encapsulation are mercilessly ignored in favour of having things run as fast as possible? Is there any truth to this and to what extent can you get away with bending the rules?

There certainly WAS truth to this, and it exists in some form on consoles today.

The problem is this 'truth' comes from older coders, older coders who were in a position where they had to do such things because of the hardware they were using at the time. Instead of looking again to see if the problems they had still exist they continue to use the ways they 'know' are fast.

Sometimes you need to bend or break the rules, I've done it myself, but normally after much agonising and looking for a 'good' solution. Sometimes profiling will show the problems as well.

By default however good coding practises are the way forward; remember the guy who might be staring at the code looking confused in a few months time could be you. Do you really hate future you that much? [sad]

AFAIK, the biggest performance hits associated with the OO style comes from the fact that many things involve (1) extraneous object copying, and (2) dereferencing function pointers. Both of these are eliminated, to my knowledge, by yet more modern language features of C++ (that's the language we're talking about, right?), specifically templates.

For an example, some very high-performance math libraries (e.g. "eigen") are written in an entirely OO way in C++, and beat equivalent C libraries for speed. The way it's done is through heavy use of templating, and some non-obvious (but nevertheless very OO) design choices: specifically, rather than having e.g. matrix-matrix products return matrix objects, they return "expression" objects which are lazy-evaluated. "Functors" (AFAIK, the meaning of this word in software engineering has nothing to do with its meaning in math) are also heavily used.

Personally I find it a little absurd that, in order to get high performance out of C++ we've layered another Turing-equivalent language (templates) atop it, and I will admit that I have not invested the time to learn it beyond the very basics, so (1) I'm not saying I'm in love with these approaches, or (2) that I'm any good at them myself, but I do know that they exist, so that, in the right hands, an extremely OO style can also produce extremely fast code.

...and it all boils down, more or less, to writing OO code that does as much as possible at compile- rather than run- time.

Quote:

Original post by Emergent AFAIK, the biggest performance hits associated with the OO style comes from the fact that many things involve (1) extraneous object copying, and (2) dereferencing function pointers. Both of these are eliminated, to my knowledge, by yet more modern language features of C++ (that's the language we're talking about, right?), specifically templates.

If you don't want copies, don't do them, if you don't want function pointers, don't use virtual functions.

Here is a nice problem of why "OO" (whatever that means) is problematic. Object-Oriented, nicely encapsulated linked list is 100 times slower than data-centric versions, despite doing exactly the same work.

OO today is often assumed to mean GoF-style patterned designs. And those are an absolute disaster.

Performance today will come from data-centric streaming algorithms, or cache-oblivious designs.

Unfortunately, most OO-centric languages don't offer anything or much to ease such development. In-place data structures are intrusive, and require breaking of encapsulation in purest OO sense (see in-place linked list above, where node needs to be aware of container to maintain indexes).

Quote:

Personally I find it a little absurd that, in order to get high performance out of C++ we've layered another Turing-equivalent language (templates) atop it, and I will admit that I have not invested the time to learn it beyond the very basics,

Templates have nothing to do with the issue at hand. Templates are the same as hard-coding the data. What can be evaluated during compile-time should be, either via macros, templates, hard-coded data. But it doesn't affect the run-time part, which needs to be done during run-time.

Quote:

...and it all boils down, more or less, to writing OO code that does as much as possible at compile- rather than run- time.

OO concepts, as exposed and compiled by current crop of compilers, are at odds with style of development that is required to optimally utilize current generation of hardware.

Polymorphism can be implemented in many ways. Compilers today use v-table, which is a disaster on in-order CPUs. This makes polymorphic calls highly undesirable.

Encapsulation mandates that class must be fully encapsulated. This goes against common intrusive or in-place techniques where different instances are implicitly linked.

General approach to multi-threading and bulk data processing often utilizes resource duplication or raw data copies (array of floats to array of floats, rather than RGB triplet to RGB triplet). With full type safety, an array of RGB instances would first need to be converted to array of floats just to get around type checking system. Instead, using a little of compiler abuse, raw typecast would get around this.

Quote:

Is there any truth to this

Yes, there is some truth, but not until one understands why. Just ignoring encapsulation for sake of speed will do exactly nothing.

Using classes and inheritance will not hurt performance.
Only using "advanced" features like: polymorphism and templates can hurt performance.
The problem with polymorphism is that the this pointer will have to be adjusted dynamically to the real type of the object, so this may have some overhead.

The problem with templates is that every time you use a template class with different parameters, the class will be duplicated. This can increase the size of the executable and so hurts the performance.

Quote:

Original post by shmok123 The problem with templates is that every time you use a template class with different parameters, the class will be duplicated. This can increase the size of the executable and so hurts the performance.

Which raises the question of does it really?

If you've instanced a templated class with a new type then you need that functionality.
If you need that functionality you need that code.
Therefore logically someone has to write the code, either you directly or the compiler via a template.
Add in optimisations and things such as comdat folding does it really cause an overhead when you need the functionality? vs writing it by hand?

Quote:

Original post by phantom Quote: Original post by shmok123 The problem with templates is that every time you use a template class with different parameters, the class will be duplicated. This can increase the size of the executable and so hurts the performance. Which raises the question of does it really? If you've instanced a templated class with a new type then you need that functionality. If you need that functionality you need that code. Therefore logically someone has to write the code, either you directly or the compiler via a template. Add in optimisations and things such as comdat folding does it really cause an overhead when you need the functionality? vs writing it by hand?

Well, there is also the C-style ADT which uses void* pointers. It is less comfortable then templates and much more risky but it doesn't duplicate the class.
Personally I prefer suffering the performance loss... writing C-style ADTs damages my health. Now days it is better to concentrate on concurrency to improve performance.

I suppose the most pragmatic answer is to profile your code extensively and understand exactly where your bottlenecks are. If benchmarking shows a significant gain you might consider a less "clean" architecture.

Quote:

Original post by shmok123 Well, there is also the C-style ADT which uses void* pointers. It is less comfortable then templates and much more risky but it doesn't duplicate the class.

Templates won't duplicate code unless they have to, either. If you have a std::vector and std::vector, then what happens is the compiler will generate separate definitions for each, but then the linker will say "these two methods are the same, so I'll just include one of them" and it'll coalese them back into one again.

It's only if you do something like std::vector and std::vector. But in that case, you don't want the code to be shared. That way, the compiler can use SSE intrinsics for the float version (if it's smart enough), for example.

Quote:

Original post by shmok123 Personally I prefer suffering the performance loss... writing C-style ADTs damages my health. Now days it is better to concentrate on concurrency to improve performance.

Absolutely.

Quote:

Original post by Antheus Here is a nice problem of why "OO" (whatever that means) is problematic. Object-Oriented, nicely encapsulated linked list is 100 times slower than data-centric versions, despite doing exactly the same work.

Obvserve that they are doing VERY different things.

At first the thread is comparing a linked list (with one allocation per item, 5000 allocations total) to a vector (allocated in bulk, about 5 allocations total).

This has nothing to do with it being "object oriented", but it has everything to do with choosing the correct algorithm for the job.




The performance difference is due to the allocations. At first rip-off mentioned it, then Antheus provided an actual sample.

The sample just re-iterates the point that the time is being spent in allocations. Fix the allocation problem, and it performs on par with the std::vector. If the vector were to reserve that many spaces, it would likely be the same in terms of performance.

Just my $0.02: I think OO principles are not at odds with performance. If they are, people probably applied OO principles incorrectly, or modeled the wrong objects. You can have great OO design with simple C programs, and terrible OO design with C++ (or pick your favorite "object-oriented" language instead).

The goodness of OO design is data encapsulation, hiding of complexity, and simple decoupled components. I've yet to see a case where you couldn't achieve that and get good performance. And OO principles certainly don't require vtables for every object, for instance. Sometimes good OO design means a particular class or struct does not support polymorphism--it can be a known primitive type. (See Stroustroup's later chapters on class design).

If your code is performance-sensitive, find that 5% of the code where 95% of the CPU time is taking place. Centralize that critical code in an object. You can then optimize that code, with whatever complexity is required, without infecting the rest of the system.

Often I've seen that 5% of critical code spread around multiple objects. For instance, you may be spreading complicated rendering code among multiple objects that are trying to render themselves. To achieve full OO decoupling, you could hide each object's rendering complexity, which means passing around more high-level state at interfaces, performing redundant transformations, etc. And so you degrade performance.

But a better way to solve that is to refactor your code so that the complex rendering is in one place, and you change how objects declare their rendering behavior.

I'd say that if you find applying strict OO principles to your objects is yielding inefficiencies, you may have modeled your domain incorrectly (or at least, nonoptimally for your use case).

Quote:

Original post by frob The sample just re-iterates the point that the time is being spent in allocations. Fix the allocation problem, and it performs on par with the std::vector. If the vector were to reserve that many spaces, it would likely be the same in terms of performance.

The drastic difference does come from allocator, but consider the separation of concerns.

In-place linked list violates SRP by taking care of links as well as allocations.

By providing a custom std::allocator one could achieve similar effect, but would create dependence on specific type in non-obvious way. Linked list would guarantee certain performance characteristics it cannot enforce. For example, one might often want linked list to guarantee it uses continuous storage, std::list, despite being "open for extension" cannot enforce that constraint (aside from asserting allocations come from fixed address range).

A more elaborate example would be indexed vertex and other streams. There it becomes impossible, or at very least highly impractical, to represent an object in an OO way. Multiple objects are pieced together from various data fragments in a GPU friendly way.

Strict OO cannot be used for this, but conceptual notion of objects can be retained.


In such non-trivial cases, while not necessarily difficult to implement reliably and robustly, basic OO requirements such as SRP fail first in their pure form.

Quote:

The goodness of OO design is data encapsulation, hiding of complexity, and simple decoupled components. I've yet to see a case where you couldn't achieve that and get good performance

Discussion.
Presentation (pdf).

It is not black and white, but definitely something to consider. And more importantly, these lessons apply to managed languages as well. I've had cases where C# or Java code saw up to 8 times shorter running times just by rearranging the data (which required breaking up the encapsulation, since some nice C++ tricks aren't available there).

Quote:

I'd say that if you find applying strict OO principles to your objects is yielding inefficiencies, you may have modeled your domain incorrectly

This is one of classic anti-OO arguments. Namely its frequent failure to incorrectly model the problem.

Either way, the point of non-OO approach is that whichever design is chosen, it should be designed around data, not some other concepts.

Quote:

Original post by Antheus Quote: I'd say that if you find applying strict OO principles to your objects is yielding inefficiencies, you may have modeled your domain incorrectly This is one of classic anti-OO arguments. Namely its frequent failure to incorrectly model the problem.

The counter argument is that it's usually the programmer's failure -- that OO is quite capable of modeling the problem correctly.

How quickly would you fix allocation problems in the example you opened with, without OO? A 1-liner change of containers did the job in the linked example. This was only possible thanks to the implicit interface of a container with ForwardIterator compatible iterators -- compile time polymorphism -- central concepts of OO. Let's not forget that a fundamental concept there enabling this change, iterators, is one of those GoF patterns -- "an absolute disaster" seems a bit strong!

Am I wrong?

Quote:

Original post by MaulingMonkey This was only possible thanks to the implicit interface of a container with ForwardIterator compatible iterators -- compile time polymorphism -- central concepts of OO. Let's not forget that a fundamental concept there enabling this change, iterators,

Sadly, it also demonstrates why C++'s approach is fundamentally broken in this respect. In practice, you will be given a third-party library with following signature:

void foo(std::list<int> & x);

This is not a failure of OO, just the typical C++ problem.

And other languages do not solve it that well either:

public void javaFoo(LinkedList i);

I suppose one could try to override the standard LinkedList implementation.

Not to mention the following anti-case:

virtual void LinkedList::foo()

which is the frequently used demonstration of what polymorphism does. Isn't this the main reason why component/container approaches came to be?


But in practice, the following is the "correct" solution:

void foo(Iterable/Iterator list);

Is this really still what could be considered OO? Aren't we crossing into a functional domain? Or actor model? Obviously current mainstram OO practices encourage coding to interfaces, but they don't do much to steer towards reusable design as such. How much code out there is coded with this in mind?

As always, YMMV, following just one style will never be optimal, but in average case, OO designs will frequently not be even remotely as flexible or adaptable as promised, or they will be vastly over-engineered.

If anything, extreme reuse and separation of concerns these days has, in practice, proven to work well with DI and IOC, which is basically data-centric design. Provide fragments of data, wire the handlers. They still fall under OO, obviously - but aren't they much closer to original C design, where you have free functions to which you pass arguments they need? Or other, data-driven concepts?

Can this honestly be considered the triumph of OO? Or is the "better" solution something that just hand picks a few of OO concepts.

IMX, people who think that OO principles stand "vs." speed have a very strange concept of what those principles are.

Quote:

Original post by Antheus Quote: Original post by MaulingMonkey This was only possible thanks to the implicit interface of a container with ForwardIterator compatible iterators -- compile time polymorphism -- central concepts of OO. Let's not forget that a fundamental concept there enabling this change, iterators, Sadly, it also demonstrates why C++'s approach is fundamentally broken in this respect. In practice, you will be given a third-party library with following signature: void foo(std::list<int> & x); This is not a failure of OO, just the typical C++ problem. And other languages do not solve it that well either: public void javaFoo(LinkedList i); I suppose one could try to override the standard LinkedList implementation. Not to mention the following anti-case: virtual void LinkedList::foo() which is the frequently used demonstration of what polymorphism does. Isn't this the main reason why component/container approaches came to be? But in practice, the following is the "correct" solution: void foo(Iterable/Iterator list);

Raises hand!

Just so I make sure I follow you, in the last foo method, you are passing an Iterator to the linked list as opposed to the actual linked list. Correct?

Quote:

Original post by Zahlman IMX, people who think that OO principles stand "vs." speed have a very strange concept of what those principles are.

The only correlation is discussed in the presentations above, and has to do more with memory layout as a consequence of how typical instance of an object is defined in most languages, and with how polymorphic calls are typically implemented.

There is no major technical reason why it couldn't be implemented differently, especially with static or code flow analysis, it's just not really all that relevant in any except most specialized cases.

And often different programming language is better suited for such ADTs and algorithms anyway.

Quote:

Just so I make sure I follow you, in the last foo method, you are passing an Iterator to the linked list as opposed to the actual linked list.

Well, I don't know. It is iterator concept, but it could be implemented by linked list itself, or as a standalone objects, or as map...

As far as logic goes, we probably want to perform some action on a subset of elements. Ideally, how these elements are stored is none of our concern.

Quote:

Original post by Antheus But in practice, the following is the "correct" solution: void foo(Iterable/Iterator list); Is this really still what could be considered OO? Aren't we crossing into a functional domain? Or actor model? Obviously current mainstram OO practices encourage coding to interfaces, but they don't do much to steer towards reusable design as such. How much code out there is coded with this in mind?

In essense I agree with you, just want to point out that this specific example doesn't really cross over into functional territory: foo returns void, so it probably relies on side effects, and Iterator/Iterable can be cleanly expressed as an interface in the OO hierarchy. For example, C#:

void foo<T>(IEnumerable<T> list); // declarationfoo(new List<int>() { 1, 2, 3 }); // usage

This is a very common (OO) construct there, since all standard (and most non-standard) collections implement the IEnumerable interface.

A construct that cannot be expressed very well in 'pure' OO terms would be applying an unknown function to a collection of items. In pseudo-language:

foo(list<T>, func(T) -> result) -> list<result>

C# 2.0 can actually express this (and C# 3.0 / .Net 3.5 can express this much better), but the resulting code is still clunky and somewhat resembles an OO approach to a functional problem (Action delegates, etc etc).

Back on topic. Personally, when I am faced with the "speed vs clean design" dilemma, my choice is always clean design, unless (a) I am at the stage where I am optimizing performance and (b) I am below my performance target and (c) I have determined that breaking the design is the only way to meet my performance target. Simply put, if my baseline hardware is getting 30fps, I will not break my design to remove a "lot of extra overhead". Alternatively, if I am in a phase of development where I cannot yet measure performance meaningfully (because, say, large parts of the infrastructure are not yet in place), breaking the design to improve performance is flat-out wrong. Only if the application is nearing completion, performance is not there yet and I have exhausted all other methods of tuning (of which there are many) then, yes, I will add the nasty hack that will let us make the release date - but I'll make sure it's well-documented to avoid complications in the future.

This "lots of extra overhead" is completely misleading in the larger view of things. There are *very* few places where an interface access or a double indirection will actually make a difference. These places are well understood (no, don't use dynamic dispatch in your math library) and are generally self-contained. Hell, you are already using COM interfaces to access your graphics library, using proper abstraction and encapsulation won't hurt you any more than that!

Besides, which would you prefer: better performance right now and a missed release date two years down the road or proper design and meeting the release date? Every nasty little speed hack now will weight you down later on, so better make sure it's 120% worth it!

That's my personal perspective, at least. I don't know, maybe my experience with legacy, hacky codebases (some of them my own) has left me old and bitter. :)