There was some critique on the performance of the sorting component. I had absolutely no idea about the exact performance of my component.  Therefore I sat down and wrote some benchmarks.  Needless to say, I never even doubted that my component would be slower than a hand-made solution. The real question was : how much slower ?

BenchMark 1 : sorting strings

Benchmarks aren’t fun to invent. Whatever you invent, people will always say you tuned them in your favor.  I therefore took the words of the sorting article, put them in a large file and used them as a sample for my sorting routines.

Turns out there are 2972 words in the file.  I read them into a global array variable, to minimize the passing around for the hand-crafted routine.  Here are the runtimes (on my machine - a Pentium III 933Mhz with 512Mb internal memory)  The units of all tables are ticks.

Sorting strings from words.txt What IDE Compiled Reading the array 10 40 QuickSort from component 330 350 Handcrafted string quicksort on global data 51 40

So if we take the worst ratio then we can see that the handcrafted solution outperforms the generic solution by 8 or 10. This seems to indicate that the price we pay for using a generic component is an order of magnitude.  This seems to apply with one of my motto’s :

Most of the time, abstraction’s penalty is performance.

Am I disappointed now ? No.  In fact I was happy to see the results. Allthough performance is indeed much worse than the handcrafted solution, at the same time the figures show that the result is certainly not bad. A sub-half a second performance is certainly worse than 50 milliseconds, but is is acceptable nevertheless. Now let’s compare the number of lines we had to write for both solutions. 

What IDE Compiled Reading the array 5 N/A QuickSort from component 1 N/A Handcrafted string quicksort on global data 42 N/A

As you can see, the figures are now much in favor of the component solution. You might say “ wait a minute - and the lines in the component themselves ? ”. I don’t count  these for the same reasons I don’t count lines in something like Scrrund.dll or a flexgrid or whatever.

The component approach beats the handcrafted solution by a factor 42.  You may dismiss this easily but the point is that the major cost of software is not the performance you loose by a less-than-optimal generic solution. The point is that by reducing the number of lines, you also reduced the maintenance on your program.  The likelyhood for a bug in the sorting components is relatively small.  The likelyhood for a bug in your own sorting routine is actually quite big. (see also “Programming pearls” by Jon Louis Bentley or try to write a quicksort right now without a book)

BenchMark 2 : sorting doubles

For the second benchmark, I initialized an array of 10000 doubles in the range of 0-1 (using Rnd). I used a fixed Randomize statement to make sure I got the same array over and over again.

Sorting 10000 pseudo-random doubles What IDE Compiled Generating the array 0 0 QuickSort from component 420 430 Handcrafted double quicksort on global data 70 10

Now look at this sample ! As by miracle the handcrafted solution outperforms the generic component 43 to 1, while the exact inverse occurs when you look at the number of source code lines. It seems that what you loose in performance, you gain in coding.

First Conclusion

The performance of the component is typically an order of magnitude worse than that of a handcrafted solution. Believe it or not but this is pretty much what I expected.

I guess I could tune the component so that this performance gap becomes smaller. But I will never be able to close the gap or even do better than a manually coded solution.

So the real question is rather : do I want to write my own code for every kind of thing I can imagine (maybe you only need to sort strings) ?  Or do I want a reusable component and let the profiler point the direction where the real bottlenecks are ?  Do I want to reuse or copy-paste ? 

I guess it really depends on the situation you are facing and there really is no a prioiri dimissing this component.  But everyone is entitled to her own opinion.

Download the benchmarking code

Optimizing the component

cSortableArrayNonObject

Just out of curiosity, I started opimimizing the code in the component.  My fingerspitzengefhül told me that I lost a lot of performance in dealing with objects and built-in types at the same time (the varAssign function).  So I wrote a cSortableArrayNonObject. This is exactly the same as an object array but it uses the built-in vb assignment instead of varAssign.

Here is what it did to the performance :

Effects of cSortableArrayNonObject   Before After Quicksort strings 330 290 Quicksort doubles 430 340

As you can see, the performance gain is enormous. (10%- 20% off)

cQuickSortNonObject

Now, if the result is so spectacular optimizing the container, we may expect similar results when doing the same the cQuickSort.  That is exactly what I did and here are the results :

Effects of cSortableArrayNonObject and cQuickSortNonObject Combined   Before After Quicksort strings 330 190 Quicksort doubles 430 191

These two optimizations virtually half the time spent in the component.  This is a spectacular result and IMHO puts the component straight before the hand-crafted solution.

[BenchMarks]
[Sorting Remarks]
[James Barbetti Implementations]