Does object-orientation really affect algorithm performance?

Question

Object orientation has helped me a lot in implementing many algorithms. However, object-oriented languages sometimes guide you in "straightforward" approach and I doubt if this approach is always a good thing.

OO is really helpful in coding algorithms fast and easily. But could this OOP be a disadvantage for software based on performance i.e. how fast does the programm executes?

For example, storing graph nodes in a data structure seems "straightforward" in the first place, but if Node objects contain many attributes and methods, could this lead to a slow algorithm?

In other words, could many references between many different objects, or using many methods from many classes, result in a "heavy" implementation?

Answer 1

Object orientation may prevent certain algorithmic optimizations, because of encapsulation. Two algorithms may work particularly well together, but if they are hidden behind OO interfaces, the possibility to use their synergy is lost.

Look at numerical libraries. A lot of them (not only those written in the 60s or 70s) are not OOP. There is a reason for that -- numerical algorithms work better as a set of decoupled modules than as OO hierarchies with interfaces and encapsulation.

Answer 2

That's not really about object orientation as about containers. If you used a double linked list to store pixels in your video player it's going to suffer.

However if you use the correct container there is no reason a std::vector is slower than an array, and since you have all the common algorithms already written for it - by experts - it's probably quicker than your home rolled array code.

Answer 3

OOP is obviously a good idea, and like any good idea it can be over-used. In my experience it is way over-used. Poor performance and poor maintainability result.

It has nothing to do with the overhead of calling virtual functions, and not much to do with what the optimizer / jitter does.

It has everything to do with data structures that, while having the very best big-O performance, have very bad constant factors. This is done on the assumption that if there is any performance-limiting problem in the app, it is elsewhere.

One way this manifests is the number of times per second new is performed, which is assumed to have O(1) performance, but can execute hundreds to thousands of instructions (including the matching delete or GC time). That can be mitigated by saving used objects, but that makes the code less "clean".

Another way it manifests is the way people are encouraged to write property functions, notification handlers, calls to base class functions, all kinds of subterranean function calls that exist to try to maintain consistency. For maintaining consistency they are of limited success, but they are wildly successful at wasting cycles. Programmers understand the concept of normalized data but they tend to apply it only to database design. They do not apply it to data structure design, at least partly because OOP tells them they don't have to. As simple a thing as setting a Modified bit in an object can result in a tsunami of updates running through the data structure, because no class worth its code takes a Modified call and just stores it.

Maybe the performance of a given app is just fine as written.

On the other hand, if there is a performance problem, here's an example of how I go about tuning it. It's a multi-stage process. At each stage, some particular activity accounts for a large fraction of time and could be replaced by something faster. (I did not say "bottleneck". These are not the kinds of things that profilers are good at finding.) This process often requires, in order to get the speedup, wholesale replacement of data structure. Often that data structure is there only because it's recommended OOP practice.

Answer 4

In theory, it could lead to slowness, but even then, it would not be a slow algorithm, it would be a slow implementation. In practice, object orientation will allow you to try various what-if scenarios (or revisit the algorithm in the future) and thus provide algorithmic improvements to it, which you could never hope to achieve if you had written it the spaghetti way in the first place, because the task would be daunting. (You would essentially have to rewrite the whole thing.)

For example, by having divided the various tasks and entities to clean-cut objects, you may be able to easily come in later and, say, embed a caching facility between some objects, (transparent to them,) which could yield a thousand-fold improvement.

Generally, the types of improvements you can achieve by using a low-level language (or clever tricks with a high-level language) give constant (linear) time improvements, which do not figure in terms of big-oh notation. With algorithmic improvements you may be able to achieve non-linear improvements. That's priceless.

Answer 5

What determines performance?

The fundamentals: data structures, algorithms, computer architecture, hardware. Plus overhead.

An OOP program can be designed to align exactly with the choice of data structures and algorithms that is deemed optimal by CS theory. It will have the same performance characteristic as the optimal program, plus some overhead. The overhead can usually be minimized.

However, a program that is initially designed with only OOP concerns, without concerning the fundamentals, may be initially sub-optimal. The sub-optimality is sometimes removable by refactoring; sometimes it is not - requiring a complete rewrite.

Caveat: does performance matter in business software?

Yes, but time-to-market (TTM) is more important, by orders of magnitude. Business software place the emphasis on the adaptability of the code to complex business rules. Performance measurements should be taken throughout the development life cycle. (See section: what does optimal performance mean?) Only marketable enhancements should be made, and should be gradually introduced in later versions.

What does optimal performance mean?

In general, the issue with software performance is that: in order to prove that "a faster version exists", that faster version must come into existence first (i.e. no proof other than itself).

Sometimes that faster version is first seen in a different language or paradigm. This should be taken as a hint to improvement, not a judgment of inferiority of some other languages or paradigms.

Why are we doing OOP if it may hinder our search for optimal performance?

OOP introduces overhead (in space and execution), in return for improving the "workability" and hence the business value of the code. This reduces the cost of further development and optimization. See @MikeNakis.

Which parts of OOP may encourage an initially sub-optimal design?

The parts of OOP that (i) encourages simplicity / intuitiveness, (ii) use of colloquial design methods instead of fundamentals, (iii) discourages multiple tailored implementations of same purpose.

• KISS
• YAGNI
• DRY
• Object design (e.g. with CRC cards) without giving equal thoughts to fundamentals)

Strict application of some OOP guidelines (encapsulation, message passing, do one thing well) will indeed result in slower code at first. Performance measurements will help diagnose those issues. As long as the data structure and algorithm aligns with the theory-predicted optimal design, overhead can usually be minimized.

What are the common mitigations to OOP overheads?

(welcome to edit)

How could we adopt OOP without sacrificing performance?

Learn and apply both the OOP and the fundamentals.

It is true that strict adherence to OOP may prevent you from writing a faster version. Sometimes a faster version can only be written from scratch. This is why it helps to write multiple versions of code using different algorithms and paradigms (OOP, generic, functional, mathematical, spaghetti), and then use optimization tools to make each version approach the observed maximal performance.

Are there types of code that will not benefit from OOP?

(Expanded from the discussion between [@quant_dev], [@SK-logic] and [@MikeNakis])

1. Numerical recipes, which originate from mathematics.
   • The mathematical equations and transforms themselves can be understood as objects.
   • Very sophisticated code transformation techniques are needed to generate efficient executable code. The naive ("white-board") implementation will have abysmal performance.
   • However, today's mainstream compilers are unable to do so.
   • Specialized software (MATLAB and Mathematica, etc) have both JIT and symbolic solvers able to generate efficient code for some sub-problems. These specialized solvers can be seen as special-purpose compilers (mediators between human-readable code and machine-executable code) which will themselves benefit from an OOP design.
   • Each sub-problem requires its own "compiler" and "code transformations". Therefore, this is a very active open research area with new results appearing every year.
   • Because research takes long time, software writers have to carry out optimization on paper and transcribe the optimized code into software. The transcribed code might indeed be unintelligible.
2. Very low level code.
   *

Answer 6

Yes, the object-oriented mindset can definitely be neutral or negative when it comes to high-performance programming, both at the algorithmic and implementation level. If OOP replaces algorithmic analysis, it can lead you into premature implementation and, at the lowest level, the OOP abstractions have to be put aside.

The issue stems from OOP's emphasis on thinking about individual instances. I think it's fair to say that the OOP way of thinking about an algorithm is by thinking about a specific set of values and implementing it that way. If that is your highest-level path, you are unlikely to realize a transformation or restructuring that would lead to Big O gains.

At the algorithmic level, it is often thinking about the bigger picture and the constraints or relationships between values that lead to Big O gains. An example might be that there's nothing in the OOP mindset that would lead you to transform "sum a continuous range of integers" from a loop to (max + min) * n/2

At the implementation level, although computers are "fast enough" for most application-level algorithms, in low-level performance-critical code one worries a great deal about locality. Again, the OOP emphasis on thinking about an individual instance and the values of one pass through the loop can be a negative. In high-performing code, instead of writing a straightforward loop, you might want to partially unroll the loop, group several loading instructions up at the top, then transform them in a group, then write them in a group. All the while you'd be paying attention to intermediate calculations and, hugely, to cache and memory access; issues where the OOP abstractions are no longer valid. And, if followed, can be misleading: at this level, you have to know about and think about the machine-level representations.

When you look at something like Intel's Performance Primitives you have literally thousands of implementations of the Fast Fourier Transform, each one tweaked to work better for a specific data-size and machine architecture. (Fascinatingly, it turns out that the bulk of these implementations are machine-generated: Markus Püschel Automatic Performance Programming)

Of course, as most of the answers have said, for most development, for most algorithms, OOP is irrelevant to performance. As long as you aren't "prematurely pessimizing" and adding in a lot of non-local calls, the this pointer is neither here nor there.

Answer 7

Its related, and often overlooked.

Its not an easy answer, its depends on what do you want to do.

Some algorithms are better in performance using plain structured programming, while others, are better using object orientation.

Before Object Orientation, many schools teach (ed) algorithm design with structured programming. Today, many schools, teach object oriented programming, ignoring algorithm design & performance..

Of course, there where schools that teach structured programming, that didn't care about algorithms, at all.

Answer 8

Performance all comes down to CPU and memory cycles in the end. But the percentage difference between the overhead of OOP messaging and encapsulation and a more wide open programming semantic may or may not be a significant enough percentage to make a noticeable difference in your application's performance. If an app is disk or data-cache-miss bound, any OOP overhead may be completely lost in the noise.

But, in the inner loops of real-time signal and image processing and other numerical compute bound applications, the difference may well be a significant percentage of CPU and memory cycles, which can make any OOP overhead much more costly to execute.

The semantics of a particular OOP language may or may not expose enough opportunities for the compiler to optimize away those cycles, or for the CPU's branch prediction circuits to always guess correctly and cover those cycles with pre-fetch and pipelining.

Answer 9

A good object oriented design helped me to speed up an application considerably. A had to generate complex graphics in an algorithmic way. I did it through Microsoft Visio automation. I worked, but was incredibly slow. Fortunately, I had inserted an extra level of abstraction between the logic (the algorithm) and the Visio stuff. My Visio component did expose its functionality through an interface. This allowed me to easily replace the slow component with another creating SVG-files, that was at least 50 times faster! Without a clean object-oriented approach, the codes for the algorithm and the Vision control would have been entangled in a way, which would have turned the change into a nightmare.