Abstraction penalties are complex

Programmers often talk about the "abstraction penalty" -- the extra cost that one takes on in order to be able to think abstractly about a problem. How expensive is it really? The answer is complex--in the sense that it has a real part and an imaginary part.

For example, consider calling a subroutine. On most computers, if the compiler actually generates a subroutine-call instruction, the cost can be quite substantial. I once used a computer on which I estimated that half of its total execution time was spent in subroutine call or return instructions.

That's the real part. On the other hand, from its inception C++ has let the programmer ask the compiler to generate code inline rather than using hardware subroutine-call instructions. Moreover, many compilers these days generate inline code for small subroutines even if you don't explicitly ask for it.

So the penalty for using subroutines as abstractions can be substantial, or it can be zero, depending on your compiler.

Sometimes the penalty is even negative. For example, if you have a library routine available that does something in N log N time that you would do in quadratic time if you were writing it yourself, you can make your programs run much faster by using the library, even if you have to pay for subroutine calls.

I like a simple approach: Avoid gross inefficiencies (such as choosing bad algorithms) when you come across them; if the program is still too slow, measure it and figure out why. If it's not too slow, don't worry about it.

Posted by Andrew Koenig at 05:00 PM  Permalink