What is the performance penalty of operator overloading STL

Question

I like STL a lot. It makes coding algorithms very convenient since it provides you will all the primitives like parition, find, binary_search, iterators, priority_queue etc. Plus you dont have to worry about memory leaks at all.

My only concern is the performance penalty of operator overloading that is necessary to get STL working. For comparison, I think it relies that == provides the needed semantics. We need to overload ==operator if we are adding our classes to a container.

How much efficiency am I losing for this convenience?

Another aside question regarding memory leaks:

1. Can memory leak ever happen when using STL containers?
2. Can a memory leak ever happen in Java?

Answer 1

When using stl algortithms on generic types, you have to supply the comparison logic in some way. Operator overloading has no performance penalty over any other function and may (like any other function) be inlined to remove any function call overhead.

Many standard containers and algorithms also use std::less and hence by default < rather than ==.

The standard containers don't themselves leak, but you can use them to hold objects (such as pointers) which don't necessarily clean up memory that they 'own'.

It's difficult to leak memory in java, but that doesn't mean you can't get into trouble by failing to have good object ownership semantics and it doesn't mean that you can't use up all the available memory and crash.

Answer 2

I'll leave the C++ answers to the previous posters, but 100% yes you can memory leak in Java. It tends to be really difficult to find too unless you have some good memory profiling tools to look at. In general, memory leaks in automated garbage collection languages (e.g. Java, Python, etc.) occur when you repeatedly instantiate objects, but either A. don't clean them up when you're done with them (e.g. calling "close" on a database connection) or B. continue to persist other objects that point to them (e.g. Hashtables) so that the automated garbage collector can never garbage collect them.

If your application is in what you think should be a stable state and you get one of these:

http://java.sun.com/javase/6/docs/api/java/lang/OutOfMemoryError.html

You're in for some fun debuggin ;)

Answer 3

Since operator overloading simply results in a function call, and you would have to write a function to do the work anyways, the overhead is zero. Operator overloading is just a convenience so you can do things like x == y instead of x.equals(y) or x < y instead of x.compaterTo(y). The compiler essentially generates something like: x.==(y) or x.<(y) (that won't compile, but you get the idea).

Answer 4

The "penalty" is actually a bonus.

Let's take the most typical of algorithms, sorting. C does not have operator overloading. As a result, qsort takes a function pointer. Each comparison uses an indirect function call (at runtime). C++ does have operator overloading. For std::sort, each comparison is a direct call (fixed by linker) or inlined (by compiler). This is far mroe effective. It's not uncommon for std::sort to be 6 times faster than qsort.

In general, operator overloading makes it a lot easier to express the "default" functions for a type, in a way that can be exploited by other code and compilers. The alternatives are far less efficient. Either they rely on macros (which hurt programmers) or they rely on function pointers (which hurt optimizers and CPUs.)

Answer 5

My only concern is the performance penalty of operator overloading that is necessary to get STL working. For comparison, I think it relies that == provides the needed semantics. We need to overload ==operator if we are adding our classes to a container.

It is nonexistent. Your overloaded operator is implemented as a function call. And if you didn't overload the operator, you'd need to define a function to use instead. So the performance is exactly the same, just with a cleaner syntax.

Answer 6

http://stackoverflow.com/questions/1800423/what-is-the-performance-penalty-of-operator-overloading-stl/1803143#1803143

In addition to this you can always have your operators inline this will not even have the penalty of a function call.