madler@piglet.caltech.edu (Mark Adler) (04/10/90)
I ran further tests on the sort programs. SORT is my quicksort with my insertion sort used for sublists of length 20 or less. ASORT is Alonzo's quicksort with my insertion sort for sublists of length 24 or less. QSORT is Alonzo's original quicksort with no insertion sort. Each test was 100 runs, where each run was with a different list of "Size" random reals, generated by RAND. The tests were done with about 17K of free memory (before the random list is generated), and with last args disabled (-55 SF). The first number of each result is the mean and the second number is the standard deviation, both in seconds. For 100 runs, the mean is accurate to 1/10 the standard deviation, and the standard deviation is itself accurate to 10% (this assumes a normal distribution, which the results appeared to be, except for the sorts of lists of length 2, for which the distribution was strongly bimodal---basically whether the list was in order or not to begin with). Size SORT ASORT QSORT 500 167.9 (2.7) 193.8 (14.3) 227.5 (15.5) 200 49.75 (1.21) 56.89 (4.72) 64.94 (4.72) 100 19.37 (0.23) 22.21 (2.35) 25.85 (2.21) 50 7.289 (0.312) 7.920 (0.976) 9.984 (0.996) 20 1.980 (0.204) 1.934 (0.198) 2.777 (0.253) 10 0.642 (0.074) 0.613 (0.085) 1.130 (0.128) 5 0.267 (0.026) 0.238 (0.027) 0.448 (0.068) 2 0.116 (0.007) 0.092 (0.007) 0.133 (0.009) The first observation is that SORT is faster than ASORT is faster than QSORT, except for Size <= 20 where ASORT is slightly faster than SORT. This consistent 0.03 second advantage for ASORT is because it decides to skip the quicksort and go straight to the insertion sort, whereas SORT calls QPART, and QPART then decides to do nothing and return to SORT which then does the same insertion sort. It would be easy to modify SORT to do the check first, but for 0.03 seconds, I haven't bothered. For long lists, SORT is about 15% faster than ASORT. Second, using insertion sort for small sublists increases the speed of QSORT by 15 to 25% for lists long enough to do quicksorting on, and insertion sort is as much as 80% faster than quicksort for short lists. Third, the standard deviations of QSORT and ASORT are 3 to 10 times those of SORT. This is because QSORT picks the partition element randomly (using RAND), whereas SORT uses a deterministic median of three method to pick a good partition element. Lastly, and this one is not obvious from looking at the data, is that none of the sorts had the (naively) expected n*log(n) behavior, nor did they fit any power law (i.e. n^p). Instead, the data for all the sorts fit quite well to n*(log(n)^2). Though I have not done an analysis, I believe this is because stack based operations are order n instead of order 1 when a list of length n is on the stack. This doesn't make them bad operations to use, since the coefficient is very small, but it does show up in the asymptotic behavior. In particular, DUP, DUP2, ROLL, ROLLD, putting anything on the stack, taking anything off the stack, etc., all move n (or at least an average of n/2) 20-bit pointers in memory, when there are n items on the stack. It is also possible that garbage collection entered into it, since there was less free memory for the longer lists. There is actually one more interesting observation---I am now getting LowBat(S) Warning. This testing involved approximately 24 hours of continuous running (done automatically over a few nights---control alarms are pretty neat). I remember my HP-28S batteries lasting over a year, but then I didn't run any programs like this either. Mark Adler madler@tybalt.caltech.edu