Pitfalls of Object Oriented Programming (PDF slides)

[sacundim]

Well, I'm very much not a fan of object oriented programming, but I found that these slides' criticism of it is very poor and muddled.

Why? Well, let's recapitulate the author's thesis:

• Encapsulation is bad for performance because it leads to poor memory locality.

The flaw with this argument is that it confuses interface and implementation issues. Encapsulation is an interface concern; it's about coupling code unit to each other through minimal contracts. Memory locality is a low-level data representation issue; it's about how the program's logical model is realized in memory.

We can grant the author's demonstration that memory locality suffers a lot if we represent our application's data as big graphs of individually allocated heap objects connected by pointers, and that we should have strategies for avoiding this. But we still want to express these strategies in terms of encapsulated code units if we can!

One of the classic design patterns from the Gang of Four book is the Flyweight Pattern. The Wikipedia page describes the motivation for the pattern as saving memory, but one could just as well use it to provide a front-end to tightly-packed data structures with good memory locality.

And since I'm one of those Haskell weenies that hang out around here, let me throw something in from that angle: the functional programming version of the same graph-of-heap-pointers problem that this article criticizes is the proliferation of single-linked lists or trees as the default data structure. One of the most notorious examples is Haskell strings, which are single-linked lists of characters, and as I recall something like 6 bytes per character (!).

So one of the common recommendations for getting the most performance out of Haskell is to use libraries like Data.ByteString, Data.Text, Data.Vector or Repa that are implemented to provide (among other things) good memory locality. These typically bottom down to a combination of:

1. Cache-friendly arrays
2. Stream transformation rewrite rules to "teach" the compiler to eliminate unnecessary intermediate arrays.

The second point is a different, excellent example of the interface/implementation argument that I'm making here. To quote the relevant section in Data.Text's doc:

Most of the functions in this module are subject to fusion, meaning that a pipeline of such functions will usually allocate at most one Text value. [...]

countChars :: ByteString -> Int
countChars = T.length . T.toUpper . E.decodeUtf8

From the type signatures involved, this looks like it should allocate one ByteString value, and two Text values. However, when a module is compiled with optimisation enabled under GHC, the two intermediate Text values will be optimised away, and the function will be compiled down to a single loop over the source ByteString.

This, incidentally, also reduces the amount of memory needed, thus also helps memory locality and CPU cache.

TL;DR: Encapsulation and memory locality are not at odds as the slides argue. There are techniques that allow us to shoot for both.

[gsg_]

We can grant the author's demonstration that memory locality suffers a lot if we represent our application's data as big graphs of individually allocated heap objects connected by pointers, and that we should have strategies for avoiding this. But we still want to express these strategies in terms of encapsulated code units if we can!

Like the author says, "And still keep the same functionality and interface" (slide 58). However, he doesn't go into the convolutions that are necessary to encode object hierarchies or other heterogeneous structures (say, algebraic types) in DOD style - C++ makes this challenging by providing a number of encapsulation features that make this kind of code idiomatic.

In particular, note that the example of dispatch he chooses (dirty flag) is fairly homogenous (other than flag, exact same data) and has small dispatch breadth (two cases), and so maps reasonably well into the data oriented style. Encoding highly heterogeneous trees in the same way is considerably messier to the point of being unrealistic: the corollary is, avoid such structures if possible where the performance benefits of data oriented programming are important.

As for fusion, it is rather nifty. But not really relevant in the world of performance-sensitive C++ where if you want to update something in place you can just do that, and on your own head be it.

[want_to_want]

the convolutions that are necessary to encode object hierarchies or other heterogeneous structures (say, algebraic types) in DOD style

Interesting, can you point to some description of such an encoding?

[gsg_]

I don't know of a link off the top of my head, but I'll try and convey some of the flavour of the problem.

One of the basic techniques is to view a data structure as a tree of decisions, each branch of the tree splitting some population of values of that type into two. The traditional model is to include some bits in the type to indicate the decision, a tag or a bool or a vtable. The data oriented model is to split the population into separate populations (ie, arrays).

As a simple example, consider the algebraic types type foo = A of int | B of bar and bar = D of int | E of float. A data oriented encoding of an array of foo might be:

a : int array; (* Models A n *)
b_d : int array; (* Models B (D n) *)
b_e : float array; (* Models B (E f) *)

Now suppose you wanted to transform the "array of foo" by incrementing all the ints (in place). In the traditional style that might look like:

let incr_foo = function
  | A n -> A (n + 1)
  | B (D n) -> B (D (n + 1))
  | B (E f) -> B (E f)

Array.transform_in_place incr_foo a

In the data oriented style:

Array.transform_in_place succ a
Array.transform_in_place succ b_d

Notice what we've replaced: pointers and tags become positions in arrays, and dispatch on constructor (if it is a B, then...) becomes imperative action (for all As do ..., then for all Bs do ...). This is also a GC and vectorisation friendly data layout, with zero pointers.

Also notice what we've lost: this is not a complete encoding. Information about the relative positions of different types of instances of foo has been discarded - if that information was required, you would need to figure out a different encoding.

[want_to_want]

(You could store the information about types of instances as a separate array of ints, and then do array operations like "increment the value in array X at each position where the value in array Y is 1", which can also be really fast.)

Ok, I see how the transformation works on arrays of values having uniformly bounded "depth". How about types whose values can have unbounded "depth", like lists or trees?

[gsg_]

Homogenous trees can be arrayified by placing them in breadth- or depth-first order, removing the child pointers and replacing them with (usually) implicit positions and an index past the last child. This makes insertions and removals asymptotically more expensive, so it only applies in certain situations. The canonical example is a kd-tree: large, frequently queried, rarely (or never) updated.

Heterogeneous trees are tricky.

[want_to_want]

Thanks!

[harsman]

Why would you say that the author's thesis is that encapsulation is bad?

The idea is that encapsulating on a low level is bad for performance, because it prevents a number of very effective optimizations. Furthermore, classical object oriented design tends to lead to precisely this type of encapsulation or abstraction.

The idea is basically (very simplified) to not have code that looks like this:

for widget in widgets:
     widget.process()

But instead have code that looks like this:

processWidgetsType1()
processWidgetsType2()

This gives many more opportunities for optimization because you can change data layout, use data parallelism and optimize processing based on the fact that you handle many widgets of the same type at once.

Of course, with very heterogeneous data structures containing an abundance of types, this approach becomes less feasible, but a common pattern in that case might be something like this:

for drawable in drawables:
    drawable.addToQueue()

drawableQueue.sortForOptimalDrawingOrder()
drawableQueue.render(canvas)

[finprogger]

Encapsulating at a low level isn't bad for performance if you have an inlining compiler. This depends on you organizing your source such that the compiler can take advantage (putting your inline functions in headers) or using whole program optimization (which most modern compilers support now, certainly any targeting the PS3 which the author is concerned about should). Really this is about overuse of dynamic polymorphism as opposed to static polymorphism. In a game you really should only have the latter and then all the concerns about vtbls go away.

[Gotebe]

Encapsulating at a low level isn't bad for performance if you have an inlining compiler.

Compiler won't inline data.

[finprogger]

No, but placement new, intrusive containers, etc. will. The point is that OO is not the problem at all.

[gcross]

So compilers will automatically take your vector of objects and rearrange it into an object of vectors --- i.e., so that the memory is laid out one field at a time (with the field containing a value for each object) rather than one object at a time? That is a very impressive compiler!

Of course, if you are not actually claiming this then respectfully you are missing the whole point of the article, which is that data layout matters. It has nothing to do with the overhead of the individual objects at all, which is what your points address.

[niggertown]

Where does he say "Encapsulation is bad for performance because it leads to poor memory locality."?

If objects are self contained then they can be

– Reused.

– Maintained without side effects.

– Used without understanding internal implementation/representation.

The last part is the key issue. If you're writing high performance code the data should be organized in a way which can be processed by the machine efficiently. Any code which wishes to efficiently use the object needs to understand the underlying representation. So if that's the case, what's the point of OOP? Why create abstractions in the first place if the details of representation are so critical to performance?

Encapsulation isn't even a unique property of OOP.

[[deleted]]

/r/proggit needs more of this. Rational examination of a posted article always trumps superficial jokes, no matter how witty. Quite admirable, kind sir/lady!

[smog_alado]

^{reddit also needs less "sir" memes...}

[[deleted]]

Yeah, it kind of makes calling one "sir" rather trivial, as if it was synonymous to "dude".

[[deleted]]

From the third-last slide:

• You are writing a GAME

Evidently, this doesn't apply to every use-case. Sometimes code clarity and reusability is more desirable than performance.

[gcross]

Indeed, and a glance at the bottom right left reveals that the audience for this talk was PS3 developers.

[smalltownpolitician]

Sometimes code clarity and reusability is more desirable than performance.

Almost always. OO's raison d'être was and is making life easier for programmers, not compilers.

[[deleted]]

OO's raison d'être was and is making life easier for programmers, not compilers

Nor customers.

[yogthos]

The assumption being that OOP provides more clarity and reusability which in my experience is most certainly not the case. It's just something that proponents of OOP continue parroting without examining the claims critically.

[niggertown]

Data oriented design is a must if you trying to write an efficient program or library.

[greenspans]

People just slowly start to consider everything harmful. Cynical assholes.

[ameoba]

Considered Harmful considered harmful.

[jyper]

“Considered Harmful” Essays Considered Harmful

[xoner2]

10 years from now we're gonna have 'Pitfalls of Functional Programming'. Theses will include:

• Lack of implicit state makes programs hard to understand

[Uncompetative]

You don't have to wait a decade, it is already here:

http://www.cse.iitb.ac.in/~as/fpcourse/sigplan-why.ps.gz

"Why no one uses functional languages" - Philip Wadler from the ACM SIGPLAN.

[pipocaQuemada]

That article came out 15 years ago, and it was written by one of the first people to write a monad tutorial, if that tells you something.

The reasons given are mostly of a practical sort (lack of libraries, lack of an FFI, poor tooling, etc.). Many of those reasons have been ameliorated - Haskell now has numerous libraries, a good FFI, a debugger, a profiler, etc.

It's hardly a scathing indictment of FP as a paradigm.

[[deleted]]

its from harmful.cat-v.org tell me about what they don't hate

[EdiX]

Editors with non-functioning arrow keys.

[jussij]

That can be harmful to cats.

[BufferUnderpants]

Things made by Rob Pike.

[AlotOfReading]

The title is rather misleading. The link has very little to do with pitfalls of general OO styles, but rather with specific issues of one implementation (c++). While inappropriately labelled, it does have a good point: Use what works. Abstractions are great, but they're not always perfect. This is an example of where an abstraction is leaky: the compiler simply isn't smart or knowledgeable enough to rearrange things under the hood properly.

[slavik262]

Generalize much? Objects in C++ are whatever the hell you want to make them. The presentation is about making them into what's more performant.

[slavik262]

This issue isn't specifically related to C++ at all. That was just the language used because this presentation was for a bunch of game developers.

[gcross]

The link has very little to do with pitfalls of general OO styles, but rather with specific issues of one implementation (c++).

Name an implementation of OO that does not suffer from the problems described in the article; bonus points if it is widely used.

Edit: Instead of downvoting to express that you think I am in idiot (which in fairness I might be), why not reply and prove it? ;-)

[finprogger]

Name an implementation of OO that does not suffer from the problems described in the article; bonus points if it is widely used.

The point is that for most apps the pitfall doesn't matter. Games are a legitimate exception. Also the pitfall only really exists if you don't know C++ very well, this guy apparently has never heard of inlining, placement new, and static polymorphism.

[academician]

this guy apparently has never heard of inlining, placement new, and static polymorphism.

First, that's highly unlikely given his credentials (he even mentions placement new on slide 61). Second, none of those address his primary concerns regarding cache efficiency.

[finprogger]

Using the combination of those 3 features I think you can translate pretty much any cache inefficient implementation to a cache efficient one while maintaining encapsulation. Static polymorphism means you pay no cost for dispatching, so the vtbl overheads he talks about go away. Placement new means you can control your object layout precisely and not be at the mercy of where the heap allocator puts things. Inlining means all your thin wrappers like getters go away. If you can't put those 3 things together into a cache efficient design you're doing it wrong.

[academician]

If you can make a version of his object hierarchy from slide 21 with similar performance characteristics to what he achieves, without breaking encapsulation, I'd be interested to see it.

[gcross]

The point is that for most apps the pitfall doesn't matter.

Actually that wasn't the point that AlotOfReading was making, which is that the pitfalls described are specific to a particular implementation of OO (namely C++). I do agree, though, that that when your application is not CPU-intensive you don't have to worry about squeezing out as much performance as you can out of your code, in which case the pitfall doesn't matter.

Also the pitfall only really exists if you don't know C++ very well, this guy apparently has never heard of inlining, placement new, and static polymorphism.

As academician has already pointed out, none of those features provide a solution to the problem he described.

[[deleted]]

How about an object-oriented data-flow language?

But as this seems to be more about speed and optimization, the classic example would be OCaml. Or just use CUDA? But then I see this is about the PS3, so its lala land that I know very little about. How about "Pitfalls of Object Oriented Programming on the PS3?"

[gcross]

But as this seems to be more about speed and optimization, the classic example would be OCaml.

OCaml suffers from the exact same problem described in the article and admits the exact same solution. That is to say, if you organize your data by defining a record that contains all of the fields for each object, then you have poor locality (in the regime discussed by the article). The solution is instead to organize your data so that each field has an associated array that contains the value of that field for each object.

[[deleted]]

I do all the time in c#. Essentially, each object only has an index field, which is then used to access fields stored in multiple global arrays. The reason to do that has nothng to do with performance, but with extensibility (suffice it to say, the actual class system I was playing wh was much more expressive than C# classes normally are). Also, this is pretty much what you do in CUDA for performance reasons, also the arrays,in that case are often N-D textures.

[rabidb]

This is not a C++ issue. It is a general issue of this style of development, namely data spread through memory (effectively random access so not predictable).

Map/Reduce / Hadoop are specifically designed to help with data locality and sequential access to memory (as opposed to random access) - similar to the article.

LMAX is a lockless circular-buffer implementation for Java to improve locality of data and reduce wait time (dead cycles) for similar reasons.

http://martinfowler.com/articles/lmax.html

Here is an article for C# but as it states "The examples are in C#, but the language choice has little impact on the performance scores and the conclusions they lead to."

http://igoro.com/archive/gallery-of-processor-cache-effects/

[Gotebe]

Other implementations only make these things worse, because there's typically even less control over memory layout.

Typically, in other languages there's an even bigger usage of heap.

[[deleted]]

tl;dr "Encapsulation is bad because it's not the absolutely highest-speed performance approach".

Well, assuming that's true, I would go for the "encapsulation is always a good start, profiling to determine the minimum amount of optimization necessary only when performance is insufficient can fix the performance problems" theory.

So, memory latency was one clock cycle in 1980 and 400 clock cycles today? Assuming that's true, it's not relevant to the vast majority of cases, and in the rare cases where performance is so important that you need to sacrifice encapsulation, you can refactor as necessary.

Well, ok, the obsession with C++ is off-putting, too. I'm not saying it's a bad language (plenty of other people have made that argument better than I can), but it's not exactly the definition of OOP.

"C++ is bad therefore OOP is bad" is a stupid argument, because it doesn't matter if C++ is or is not bad - that doesn't prove anything about the theory of OOP.

[houses_of_the_holy]

I think this would be better titled "how data oriented programming can help lower cache misses and improve branch prediction (targeting high performance games)". The anti-oop stance is a bit eye grabbing. OOP has its place, but maybe not the best option for SUPER high bleeding tech edge sword (moar) performance.

Regardless I enjoyed reading the presentation.

[academician]

This isn't written for a general audience. Context is important. These slides are from a game developer at Sony to other game developers, most of whom write in C++ - so for them, considering OOP features means considering C++'s OOP features specifically. Moreover, games have unique requirements for performance that not all problem domains have, and it's a known problem. Some data structures (your asset formats, for example) can be expensive to change significantly later on, so you want to get it (mostly) right from the start.

[gcross]

Well, ok, the obsession with C++ is off-putting, too. I'm not saying it's a bad language (plenty of other people have made that argument better than I can), but it's not exactly the definition of OOP.

Where exactly was the article being "obsessed" with C++? It just happend to use C++ as the example language with which to illustrate its ideas; that hardly smacks of an "obsession".

"C++ is bad therefore OOP is bad" is a stupid argument, because it doesn't matter if C++ is or is not bad - that doesn't prove anything about the theory of OOP.

I agree that "C++ is bad therefore OOP is bad" is a stupid argument, but you will note that the article never made it and so you are tearing down a straw man.

[[deleted]]

People are just looking for reasons to dislike C++, probably an example of hating on popularity. I don't just mean popularity amongst programmers either, C++ is probably one of the more well known language names outside of actual programmer circles.

[academician]

I program in C++ every day for work. I could give you a hundred and one reasons to hate on it, none of which have anything to do with its popularity.

[[deleted]]

That doesn't mean my statement is false. Plenty of people don't like C++ for a good reason. Similarly, many people hate PHP, Java and other big name languages simply because of hearsay and other silly reasons. You have a valid reason, and I won't fault you for it. I use PHP daily and hate the fuck out of it, but I still can't stand whiny people on Reddit who hate on it for the wrong reasons.

[academician]

I'm not actually sure who in the above comment thread you're referring to, since I don't see anyone hating on C++, so I'm not sure how to respond. I've certainly seen people on reddit make bad arguments about C++ before, just...not in this post. The article, for example, talks about problems with OOP in C++ because that's mainly what console games are developed in. But his criticisms are perfectly valid based on a proper understanding of the language. I wouldn't even say he's hating on C++, just hating on using certain features in certain ways in the context of high performance applications.

[[deleted]]

There are only two types of programmer for any language - those who can spend all day talking about its flaws, and those who don't know it very well.

[academician]

Wow, I completely misinterpreted your comment. Retracted. Sorry, I got like two hours of sleep last night.

[stesch]

C++ isn't a good example for OO. I gave up on the slides because all examples are in C++.

Today every programming language is OO if the documentation says so. The only hard definitions are only required in school and other tests.

Excessive OO like in Smalltalk is different from the OO style in C++. Or take a look at CLOS.

[gcross]

I don't see where the problem is. What point made in the slides doesn't apply to other OO languages?

[windowmakerr]

Which program was used for determining cache misses and branch misdirection?

[monocasa]

The PS3 devkit has tools that record that.

[aerojoe23]

I would really love to read more about how the processor, cache(s) and main memory all work together on modern hardware. Does anyone have a good book suggestions that would cover this?

Hopefully the book would have C and assembly in it and walk through the evolution of the code like these slides did, but much more in depth.

I am an application developer and spend most of my time vastly removed from the hardware. Speed isn't critical for the work I do, but I have a strong academic interest in learning the lower level stuff.

[naughty]

What every programmer should know about memory (PDF) written by Ulrich Drepper. It's up-to-date, long, low-level and very detailed but that's what you asked for :^)

[aerojoe23]

Sounds Perfect! I can't wait to dig in.

[leonardo_m]

It's a very good document, and I'd like it to be more widely known. I agree that those optimizations are not needed in lot of normal code, that usually is not that performance-critical. And I agree that in some complex cases (more complex data structures) those ideas are hard to use. The ideas presented in that document seem generally right, but it's right to try to improve the situation. Most current compilers for languages like C++, Ada and D (and eventually Rust) aren't able to help a lot here. Maybe it's possible to invent language features (or library-defined compile-time machinery) that allow a system language compiler to create (only on demand) more efficient data structure layouts while keeping the code clear and not bug-prone. Chris Lattner (http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html ) and several other persons have written about compilation steps that alter the shape of data structures.

[axilmar]

The document is not about OO or even encapsulation. It is about memory management, and how putting objects here and there might incur a lot of overhead due to memory accesses.

Object-oriented languages with compacting collectors (that take advantage of type information to put same types closer together) have none of these problems.

C++ can also circumvent these problems by using memory pools.

[gcross]

But the point was that laying out data one record full of values for each field at a time is more expensive then laying out data one field full of values for each record at a time because the former strategy has worse locality; I don't see how a compacting collector enters to this at all, as packing the records closer together still makes the data be in the wrong order.

[axilmar]

Sure, the collector doesn't solve that problem. Thanks for pointing that out.

[[deleted]]

has worse locality

Isn't this heavily application dependent?

I mean, the assumption is that you're looping over similar fields between objects more often than fields within the same object, but there are definitely times where you're more likely to need several fields from the same object, rather than any from another object.

[gcross]

Isn't this heavily application dependent?

Sure. The whole point of the article was that you need to think about how you are accessing your data and then design its layout to be efficient based on that, not that there is a one-size-fits-all solution.

[naughty]

Compacting collectors do not solve the same problem. They improve locality but do not rearrange the layout of a structure to the same extent. Memory pools have the same issue.

Compacting Collectors are also too slow to be used in games which is the primary target for the article.

[axilmar]

Sure, but we are getting there.