Abstraction and performance -- a bit of history -- summary

What have we learned from this algorithm story?

In the early days of C++, I wanted to show prospective users what C++ might be able to do for them. To that end, I wanted to write a program that would show off some recently available libraries that handled variable-length strings, lists, and associative arrays.

I chose topological sorting as my problem, because it had a practical application (although a slightly obscure one), and because it was small enough that I could explain it without boring the audience. The sorting program was much smaller than its C counterpart. Would it be faster too?

The answer was "it depends." Each of the C++ libraries had an abstraction penalty. For example, inserting an element in an associative array takes longer than appending an element to a built-in array. Moreover, in the case of this early version of the I/O library, the abstraction penalty could be described only as horrendous.

To counterbalance this overhead, the C topological-sorting program had quadratic execution time, which meant that in theory, the C++ version would be faster when the input was large enough.

In practice, "large enough" was still small enough to be encountered in practice. Which meant that I could find real data on which the C++ version of the program ran four times as quickly as the C version.

This let me claim, legitimately, that even at this early stage of development, there was an existing C program that, when rewritten in C++, was not only dramatically shorter but also faster on large data.

This example shows that there is often no easy answer to the question: "How much slower is C++ than C?" If the higher level of abstraction available in C++ gives a programmer the time to use a fast algorithm instead of a slow one, a C++ program can sometimes be much faster than its C counterpart.

Are such comparisons fair? After all, the programs being compared aren't really the same--although they solve the same program, they do so in different ways. Your answer to that question will depend on whether you care about theory or practice.

In theory, you should be able to translate any C program into an equivalent C++ program that runs just as fast. In practice, there is a tension that is caused by the difference in abstraction ability between C and C++. This difference encourages C++ programmers to write different programs from their C counterparts. Often, there is no theoretically meaningful way to compare such programs.

Posted by Andrew Koenig at 09:42 AM  Permalink