[Benchmark suckers and implementors only]
Chris writes ...
> While experimenting with the sorting algorithms that have been posted here
> recently I discovered that the benchmarks were being quite seriously distorted
> by the use of type classes to implement some of them. Even the use of `Ord a'
> contexts instead of passing the compare method explicitly was introducing some
> minor distortions. Here are the results with type classes eliminated, except
> for `pairingSort0', the original `pairingSort' as implemented with the
> `PriorityQueue' type class, and "nmsort'", a variant of `nmsort' using `Ord a'
> contexts.
Yes, you are right. I made the same observation. Here are my results
... [fastSort is actually pairingSort without classes, the other
functions are as in my previous posting.]
+---+
|ghc| And the winner is ... [you should probably enlarge your window]
+---+
100.000 | < | <= | > | >= | == | 1 2* |
1..100* | 2 1* | 100..1* | 1 2 2 1* | random
merge | 3.60 | 3.79 | 2.72 | 3.42 | 2.88 | 6.49 |
12.96 | 6.53 | 12.41 | 6.42 | --
bottom-up | 2.17 | 2.36 | 2.03 | 2.09 | 2.18 | 6.49 |
12.92 | 6.47 | 12.55 | 6.43 | --
heap | -- | -- | -- | -- | 22.12 | -- |
-- | -- | -- | -- | --
pairing | 1.50 | 1.64 | 2.24 | 2.37 | 1.47 | 2.46 |
4.01 | 2.43 | 4.40 | 2.36 | 10.65
Jon's | 1.07 | 1.31 | 1.12 | 1.20 | 2.21 | 2.93 |
3.43 | 2.88 | 3.48 | 2.81 | 8.24
braun | 26.14 | 22.31 | 21.95 | 21.64 | 7.72 | 14.73 |
20.97 | 14.69 | 20.96 | 14.54 | 23.24
smooth | 0.25 | 0.41 | 0.26 | 2.98 | 0.29 | 4.24 |
3.27 | 4.29 | 3.24 | 4.26 | --
splay | 0.77 | 0.84 | 0.79 | 1.84 | 0.72 | 2.34 |
8.92 | 3.16 | 6.11 | 2.25 | 17.24
hbcsort | 0.31 | 0.47 | 1.88 | 1.68 | 0.30 | 3.18 |
1.69 | 3.49 | 3.72 | 2.19 | 4.85
nmsort | 0.38 | 0.45 | 1.76 | 1.74 | 0.36 | 2.22 |
1.78 | 3.49 | 3.58 | 2.27 | 4.83
fastSort | 0.54 | 0.62 | 0.87 | 0.96 | 0.64 | 1.23 |
2.33 | 1.27 | 2.50 | 1.23 | 5.15
-- = heap or stack overflow
1. | smooth | smooth | smooth | fastSort | smooth | fastSort |
hbcsort | fastSort | fastSort | fastSort | nmsort
2. | hbcsort | nmsort | splay | Jon's | hbcsort | nmsort |
nmsort | pairing | smooth | hbcsort | hbcsort
3. | nmsort | hbcsort | fastSort | hbcsort | nmsort | splay |
fastSort | Jon's | Jon's | splay | fastSort
4. | fastSort | fastSort | Jon's | nmsort | fastSort | pairing |
smooth | splay | nmsort | nmsort | Jon's
5. | splay | splay | nmsort | splay | splay | Jon's |
Jon's | hbcsort | hbcsort | pairing | pairing
6. | Jon's | Jon's | hbcsort | bottom-up | pairing | hbcsort |
pairing | nmsort | pairing | Jon's | splay
7. | pairing | pairing | bottom-up | pairing | bottom-up | smooth |
splay | smooth | splay | smooth | braun
8. | bottom-up | bottom-up | pairing | smooth | Jon's | merge |
bottom-up | bottom-up | merge | merge | merge
9. | merge | merge | merge | merge | merge | bottom-up |
merge | merge | bottom-up | bottom-up | bottom-up
10. | braun | braun | braun | braun | braun | braun |
braun | braun | braun | braun | heap
11. | heap | heap | heap | heap | heap | heap |
heap | heap | heap | heap | smooth
Times were taken on a loaded Sun Ultra-1 Sparcstation (run time options
as above, *minimum* out of five runs). The `merge sorts' are in front
with pairing sort following hard on their heels. However, this is a
statement which is `ghc'-specific! Roughly speaking, `ghc' does not
like classes, and prefers higher-order functions instead.
If we increase the size of the input data
500.000 | < | <= | > | >= | == | 1 2* |
1..100* | 2 1* | 100..1* | 1 2 2 1* | random
Jon's | 20.15 | 29.03 | 20.18 | 19.92 | 20.49 | 27.52 |
30.98 | 27.48 | 30.96 | 25.26 | 80.36
hbcsort | 2.67 | 7.00 | 44.54 | 26.34 | 2.06 | 33.49 |
22.81 | 41.51 | 51.26 | 31.22 | 69.21
nmsort | 6.69 | 7.92 | 38.84 | 25.47 | 3.91 | 32.56 |
23.47 | 40.35 | 47.23 | 31.77 | 66.35
fastSort | 6.42 | 8.60 | 9.25 | 9.40 | 5.93 | 10.15 |
17.14 | 10.09 | 16.83 | 10.10 | 49.02
-- = heap or stack overflow
1. | hbcsort | hbcsort | fastSort | fastSort | hbcsort | fastSort |
fastSort | fastSort | fastSort | fastSort | fastSort
2. | fastSort | nmsort | Jon's | Jon's | nmsort | Jon's |
hbcsort | Jon's | Jon's | Jon's | nmsort
3. | nmsort | fastSort | nmsort | nmsort | fastSort | nmsort |
nmsort | nmsort | nmsort | hbcsort | hbcsort
4. | Jon's | Jon's | hbcsort | hbcsort | Jon's | hbcsort |
Jon's | hbcsort | hbcsort | nmsort | Jon's
`fastSort' wins, hence its name ;-).
+---+
|hbc| And the winner is ... [again, you should probably enlarge your window]
+---+
100.000 | < | <= | > | >= | == | 1 2* |
1..100* | 2 1* | 100..1* | 1 2 2 1* | random
merge | 2.77 | 2.88 | 2.80 | 2.95 | 2.62 | 3.83 |
4.02 | 3.73 | 3.94 | 3.73 | 5.32
bottom-up | 2.09 | 2.12 | 2.09 | 2.17 | 2.02 | 3.09 |
3.23 | 3.15 | 3.34 | 2.98 | 4.71
heap | 7.61 | 7.56 | 7.70 | 7.57 | 5.05 | 6.23 |
6.92 | 6.20 | 6.89 | 6.21 | 8.31
pairing | 0.82 | 0.98 | 1.41 | 1.38 | 0.88 | 1.49 |
2.73 | 1.52 | 2.88 | 1.53 | 5.42
Jon's | 1.32 | 1.39 | 1.35 | 1.40 | 2.64 | 3.70 |
4.51 | 3.70 | 4.46 | 3.54 | 10.07
braun | 9.63 | 9.49 | 9.83 | 9.63 | 5.28 | 7.76 |
8.97 | 7.86 | 8.94 | 7.86 | 10.26
smooth | 0.35 | 0.43 | 0.31 | 2.28 | 0.32 | 2.91 |
2.12 | 2.90 | 2.07 | 2.87 | 4.52
splay | 0.85 | 1.07 | 1.23 | 2.34 | 0.82 | 3.32 |
-- | 4.38 | 7.67 | 3.09 | --
hbcsort | 0.31 | 0.41 | 2.29 | 1.97 | 0.26 | 2.86 |
2.08 | 3.11 | 3.42 | 2.85 | 4.44
nmsort | 0.57 | 0.72 | 3.38 | 3.08 | 0.58 | 4.47 |
3.41 | 4.94 | 5.07 | 4.40 | 6.40
fastSort | 0.55 | 0.64 | 1.01 | 1.12 | 0.56 | 1.33 |
2.26 | 1.28 | 2.47 | 1.29 | 4.95
-- = heap or stack overflow
1. | hbcsort | hbcsort | smooth | fastSort | hbcsort | fastSort |
hbcsort | fastSort | smooth | fastSort | hbcsort
2. | smooth | smooth | fastSort | pairing | smooth | pairing |
smooth | pairing | fastSort | pairing | smooth
3. | fastSort | fastSort | splay | Jon's | fastSort | hbcsort |
fastSort | smooth | pairing | hbcsort | bottom-up
4. | nmsort | nmsort | Jon's | hbcsort | nmsort | smooth |
pairing | hbcsort | bottom-up | smooth | fastSort
5. | pairing | pairing | pairing | bottom-up | splay | bottom-up |
bottom-up | bottom-up | hbcsort | bottom-up | merge
6. | splay | splay | bottom-up | smooth | pairing | splay |
nmsort | Jon's | merge | splay | pairing
7. | Jon's | Jon's | hbcsort | splay | bottom-up | Jon's |
merge | merge | Jon's | Jon's | nmsort
8. | bottom-up | bottom-up | merge | merge | merge | merge |
Jon's | splay | nmsort | merge | heap
9. | merge | merge | nmsort | nmsort | Jon's | nmsort |
heap | nmsort | heap | nmsort | Jon's
10. | heap | heap | heap | heap | heap | heap |
braun | heap | splay | heap | braun
11. | braun | braun | braun | braun | braun | braun |
splay | braun | braun | braun | splay
We have roughly the same situation, but `hbc' appears to be more class
friendly, `hbcsort' is faster than `nmsort'.
Something interesting happens when we increase the size of the input.
500.000 | < | <= | > | >= | == | 1 2* |
1..100* | 2 1* | 100..1* | 1 2 2 1* | random
heap | 171.37 | 112.11 | 172.19 | 112.34 | 48.34 | 83.53 |
81.36 | 83.49 | 81.31 | 83.43 | 168.32
braun | 185.20 | 128.01 | 191.04 | 129.49 | 66.54 | 95.56 |
97.30 | 95.63 | 97.34 | 95.75 | 194.74
hbcsort | -- | 3.78 | -- | -- | 2.39 | 23.59 |
14.42 | -- | -- | 22.59 | --
nmsort | -- | 15.06 | -- | -- | 8.09 | 40.70 |
28.20 | -- | -- | 39.58 | --
-- = heap or stack overflow
1. | heap | hbcsort | heap | heap | hbcsort | hbcsort |
hbcsort | heap | heap | hbcsort | heap
2. | braun | nmsort | braun | braun | nmsort | nmsort |
nmsort | braun | braun | nmsort | braun
3. | | heap | | | heap | heap |
heap | | | heap |
4. | | braun | | | braun | braun |
braun | | | braun |
Believe it, or not, only `heap sort' and `braun sort' pass the test putting tears
of joy in my eyes ;-).
> (Incidentally, I would have rather that all the bench marking were done under
> Haskell rather than the shell script, that way one could factor out the start
> up cost and possibly the overhead of generating the test data; a simple potable
> interface to the system clock would have been useful here.)
I used to do this, but my benchmark shell had a (compiler generated?)
speak leak.
Ralf
Appendix
~~~~~~~~
> fastSort :: (Ord a) => [a] -> [a]
> fastSort = toOrderedList . fromList
> where
> fromList [] = Nil
> fromList [a] = Node a []
> fromList (a:b:x)
> | a <= b = meld (Node a [Node b []]) (fromList x)
> | otherwise = meld (Node b [Node a []]) (fromList x)
> toOrderedList Nil = []
> toOrderedList (Node a ts) = a : toOrderedList (meldAll ts)
> meld Nil u = u
> meld t@(Node _ _) Nil = t
> meld t@(Node a ts) u@(Node b us)
> | a <= b = Node a (u:ts)
> | otherwise = Node b (t:us)
> meldAll [] = Nil
> meldAll [t] = t
> meldAll (t:u:ts) = meld (meld t u) (meldAll ts)
