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

As a demonstration, I had written a topological-sorting program in C++, using my newly written associative-array library. How did its performance compare with the C version that came with the system?

If the performance turned out to be as good, or even close, that would be wonderful. After all, the C version was much more code than the C++ version, and programmer time is more important than computer time.

However, the C++ version had two major arguments against it.

First, it used classes for all of its string processing, which meant that every time a string was allocated or deallocated, the string library made a trip to the system's memory allocator. The C version could allocate memory in big chunks, pick off what it needed, and then not bother to give it back to the system at all. After all, its authors knew that it would consume only a limited amount of string memory, and that all of that memory would automatically go back to the operating system when the program finished.

The second drawback of the C++ version was that the I/O library was quite unsophisticated at the time. In particular, it did no input buffering at all--instead, it called the operating system for each character of input. This system call executed hundreds of instructions; I don't remember how many. The effect of this strategy was to make any C++ program that did input run much more slowly on the input part than did its C counterpart.

I had known about these drawbacks of the C++ library, but hadn't thought that much about them when I was working on the associative-array library. After all, that was someone else's code, and the author was sure to improve it eventually, as users began clamoring for better performance.

Still, here I was, being asked about performance of a program that was being bogged down by two parts of the library that I did not write. Was there anything I could do to offset the disadvantage?

There was one thing: The C topological-sort program used singly-linked lists instead of associative arrays. Therefore, in the cases where I expected order n log(n) performance, the C program could be expected to run in quadratic time. In principle, therefore, if I could find a realistic excuse to give the two programs large enough input, the intrinsically slower performance of the C algorithm would overtake the less refined implementation of that early C++ library.

(to be continued)

Posted by Andrew Koenig at 02:56 PM  Permalink