Abstraction and performance -- a bit of history, part 3

I had an algorithm that I knew would be relatively slow on small inputs and relatively fast on large ones. The question was how large was large enough?

When I tried it on inputs of a few dozen lines, the results were horrendous--I think it ran 100 times more slowly than the C version. So I went looking around the machine to see if I could find a sample input that was both realistic and large enough to let the inherent superiority of my algorithm overcome the inefficiencies of the I/O library.

The problem I was trying to solve--topological sorting--had a common use: Determining the order of modules in a link library. I was using an operating system with a linker that made a single pass over each library it encountered, which meant that every module in a library had to follow every module that used it. Therefore, to create a library, there was a program that looked at each module and prepared a list of dependencies, each of the form "X calls Y". A topological sort of those dependencies would yield an appropriate order for the library.

What I needed, then, was a library with lots of entries. Looking around the machine, I found one: A package of Fortran subroutines for mathematical computations. If I remember correctly, it had several hundred modules and several thousand dependencies.

Indeed, it was large enough that just reading it took about a minute with the horrendously inefficient I/O library I had available at the time. Nevertheless, when I ran the C program for topological sorting, I found that it took four times longer to run than the C++ version, I/O inefficiencies and all.

Posted by Andrew Koenig at 05:06 PM  Permalink