AsproSort - Performance Numbers

We have run thousands of performance tests using the various AsproSort algorithms and have had some very surprising results. Here are some performance numbers for Asprosort's two most performant algorithms done under what can could be called average conditions. They were run on very similar hardware, all the tests had similar speed processors though the 64 bit machines had larger on-board cache sizes. All test machines had 4GB of RAM (though, of course, the x86 machines could not fully use it all). The machines were not running any high need (either CPU or disk) applications but they were not artificially barren of any running apps, they were, hopefully, your average low-power server type setup.

All the trials were performed on arrays using the Array.Sort<T> method for the .Net sort and the obvious Sort<T> method from the appropriate algorithm class; except the 256 byte struct - pointer column which uses the unsafe sorting method and the last column which is a generic list sorted using the OrderBy<T, K> extension method for the .Net sort. All trials were done with the number of elements specified in the second row and the results are all given in seconds.


Element Type   Int32 Double 16 byte struct 256 byte struct 256 byte struct - pointer SmallClass (32 bytes) IList <Class>
Number of Elements   0x1000000 0x1000000 0x1000000 0x100000 0x100000 0x1000000 0x400000
                 
x86 - 1 processor .Net sort 3.789 4.312 9.773 4.271 4.390 24.814 10.167
Quicksort 3.101 3.543 8.282 4.374 2.397 22.590 7.575
Mergesort 3.471 4.573 13.074 7.076 5.014 22.859 9.274
                 
x86 - 2 processors .Net sort 3.748 4.296 9.921 4.339 4.343 24.186 10.203
Quicksort 1.996 2.562 5.489 3.408 1.733 17.159 5.643
Mergesort 2.003 2.848 7.511 4.814 3.936 13.790 7.047
                 
x64 - 1 processor .Net sort 3.241 3.511 11.571 4.560 4.565 22.548 9.139
Quicksort 2.265 2.479 10.361 4.355 2.074 21.096 7.203
Mergesort 3.003 3.541 13.024 6.260 4.001 20.135 12.509
                 
x64 - 2 processors .Net sort 3.245 3.521 11.580 4.540 4.527 22.457 9.294
Quicksort 1.456 1.614 6.673 2.878 1.677 14.968 6.263
Mergesort 1.621 2.214 7.116 4.213 3.277 12.894 8.762
                 
x64 - 4 processors .Net sort 3.273 3.497 11.213 4.602 4.589 22.504 9.270
Quicksort 1.031 1.114 4.758 2.133 1.429 11.196 5.799
Mergesort 0.972 1.269 4.391 3.156 2.726 9.001 6.598


The results show that there is a significant gain to be had using AsproSort's sorting routines over the builtin .Net routines even on a single processor machine. And huge gains to be had on multi-processor machines. But perhaps the most important result is that it demonstrates that there is no one size fits all sorting strategy - different type sizes, different data bus sizes and different processor numbers often need diffent strategies.