Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
Quite a strange question. I can understand how OOP helps on a level of architecture. But a level of algorithms implementation is normally built upon abstractions that are very alien to anything OOP stands for. So, chances are, performance is not the biggest problem for your OOP algorithms implementations. As for the performance, with OOP the single biggest bottleneck is normally related to virtual calls. –  SK-logic Dec 17 '11 at 17:17
    
@SK-logic > object orientation tend to manipulate everithing by pointer, which imply a more important workload on the memory allocation side, and non localized data tend to not be in the CPU cache and, last but not least, imply a lot of indirect branching (virtual functions) which is deadly for CPU pipeline. OO is a good thing, but it can certainly have a performance cost in some cases. –  deadalnix Dec 17 '11 at 17:45
    
If the nodes in your graph have a hundred attributes, you'll need place to store them regardless of the paradigm used for the actual implementation, and I don't see how any single paradigm has an edge on this in general. @deadalnix: Maybe the constant factores can be worse due to making certain optimizations harder. But note that I say harder, not impossible - for instance, PyPy can unbox objects in tight loops and JVMs have been inlining virtual function calls since forever. –  delnan Dec 17 '11 at 17:55
    
Python is good for prototyping algorithms, and yet you frequently do not need a class when implementing a typical algorithm in it. –  Job Dec 17 '11 at 19:20
1  
+1 For relating object orientation with algorithms, something that is overlooked these days, both in software industry, and academy ... –  umlcat Dec 17 '11 at 20:01

9 Answers 9

up vote 8 down vote accepted

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.

share|improve this answer
2  
The main reason for that is that only C++ figured out to use expression templates to make the OO version be as efficient. –  DeadMG Dec 17 '11 at 17:17
4  
Look at the modern C++ libraries (STL, Boost) - they're not OOP at all too. And not just because of performance. Algorithms could not normally be well represented in an OOP style. Things like generic programming are much better suited for low level algorithms. –  SK-logic Dec 17 '11 at 17:20
    
Wha-wha-what? I guess I come from a different planet than quant_dev and SK-logic. No, a different universe. With different laws of physics and everything. –  Mike Nakis Dec 17 '11 at 22:32
1  
@MikeNakis: the difference in viewpoint lies in (1) whether a certain piece of computational code can benefit in terms of human-readability from OOP at all (which numerical recipes aren't); (2) whether the OOP class design aligns with the optimal data structure and algorithm (see my answer); and (3) whether each layer of indirection deliver sufficient "value" (in terms of work-done per function call or conceptual clarity per layer) justifies the overhead (due to indirection, function call, layers, or data copying). (4) Finally, sophistication of compiler/JIT/optimizer is limiting factor. –  rwong Dec 17 '11 at 23:36
1  
@MikeNakis, what do you mean? Do you think STL is an OOP library? Generic programming does not go well with OOP anyway. And needless to mention that OOP is a too narrow framework, suitable only for a very few practical tasks, alien for anything else. –  SK-logic Dec 18 '11 at 14:50

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.

share|improve this answer
1  
+1: the difference between spaghetti and object-oriented code (or code written in a well-defined paradigm) is: each version of good code rewritten brings new understanding into the problem. Each version of spaghetti rewritten never brings any insight. –  rwong Dec 18 '11 at 2:38
    
@rwong couldn't be explain better ;-) –  umlcat Dec 19 '11 at 15:53

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.

share|improve this answer
    
Because compilers are sub-optimal (or the rules of the programming language forbids taking advantage of certain assumptions or optimizations), there is indeed an overhead which cannot be removed. Also, certain optimizations e.g. vectorization have data organization requirements (e.g. structure-of-arrays instead of array-of-structures) which OOP can either enhance or hinder. (I recently just worked on an std::vector optimization task.) –  rwong Dec 18 '11 at 1:32

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.
      *
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
did you mean O.O. Design applied with a procedural language, or O.O. Design & O.O. programming language ? –  umlcat Dec 20 '11 at 15:55
    
I am speaking of a C# application. Both the design and the language are O.O. Where as the O.O.-iness of the language will introduce some small performance hits (virtual method calls, object creation, member access via interface), the O.O. design helped me in creating a much faster application. What I want to say is: Forget performance hits due to O.O. (language and design). Unless you are doing heavy calculations with millions of iterations, O.O. will not harm you. Where you usually loose a lot of time is I/O. –  Olivier Jacot-Descombes Dec 20 '11 at 16:16

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.

share|improve this answer

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.