[m-dev.] Sorting results

[Ralph Becket]

Insomnia is a wonderful thing...  I implemented Richard O'Keefe's
smooth applicative mergesort (samsort) and added it to the suite.

Here are the results (I've noted the overheads for samsort wrt msort
on randomized data; the ratios are speedups wrt list msort (list__sort/1)):

starting sorting benchmark on 10 items over 100000 iterations

100000 x           list msort on  ascending data:     1659ms (ratio  1.00)
100000 x          array hsort on  ascending data:     1470ms (ratio  1.13)
100000 x          array qsort on  ascending data:     1960ms (ratio  0.85)
100000 x          array msort on  ascending data:      900ms (ratio  1.84)
100000 x        array samsort on  ascending data:      420ms (ratio  3.95)

100000 x           list msort on descending data:     1800ms (ratio  1.00)
100000 x          array hsort on descending data:     1080ms (ratio  1.67)
100000 x          array qsort on descending data:     1950ms (ratio  0.92)
100000 x          array msort on descending data:      730ms (ratio  2.47)
100000 x        array samsort on descending data:      390ms (ratio  4.62)

100000 x           list msort on randomized data:     1970ms (ratio  1.00)
100000 x          array hsort on randomized data:     1440ms (ratio  1.37)
100000 x          array qsort on randomized data:     2020ms (ratio  0.98)
100000 x          array msort on randomized data:      920ms (ratio  2.14)
100000 x        array samsort on randomized data:      920ms (ratio  2.14)

starting sorting benchmark on 100 items over 10000 iterations

10000 x           list msort on  ascending data:     3069ms (ratio  1.00)
10000 x          array hsort on  ascending data:     3340ms (ratio  0.92)
10000 x          array qsort on  ascending data:     2960ms (ratio  1.04)
10000 x          array msort on  ascending data:     1140ms (ratio  2.69)
10000 x        array samsort on  ascending data:      320ms (ratio  9.59)

10000 x           list msort on descending data:     3280ms (ratio  1.00)
10000 x          array hsort on descending data:     2190ms (ratio  1.50)
10000 x          array qsort on descending data:     2850ms (ratio  1.15)
10000 x          array msort on descending data:      920ms (ratio  3.57)
10000 x        array samsort on descending data:      290ms (ratio 11.31)

10000 x           list msort on randomized data:     4260ms (ratio  1.00)
10000 x          array hsort on randomized data:     2670ms (ratio  1.60)
10000 x          array qsort on randomized data:     2940ms (ratio  1.45)
10000 x          array msort on randomized data:     1280ms (ratio  3.33)
10000 x        array samsort on randomized data:     1600ms (ratio  2.66)
(-25%)

starting sorting benchmark on 1000 items over 1000 iterations

1000 x           list msort on  ascending data:     6020ms (ratio  1.00)
1000 x          array hsort on  ascending data:     5460ms (ratio  1.10)
1000 x          array qsort on  ascending data:     3850ms (ratio  1.56)
1000 x          array msort on  ascending data:     1430ms (ratio  4.21)
1000 x        array samsort on  ascending data:      370ms (ratio 16.27)

1000 x           list msort on descending data:     6090ms (ratio  1.00)
1000 x          array hsort on descending data:     3500ms (ratio  1.74)
1000 x          array qsort on descending data:     3730ms (ratio  1.63)
1000 x          array msort on descending data:     1260ms (ratio  4.83)
1000 x        array samsort on descending data:      320ms (ratio 19.03)

1000 x           list msort on randomized data:     8950ms (ratio  1.00)
1000 x          array hsort on randomized data:     3990ms (ratio  2.24)
1000 x          array qsort on randomized data:     3810ms (ratio  2.35)
1000 x          array msort on randomized data:     1850ms (ratio  4.84)
1000 x        array samsort on randomized data:     2090ms (ratio  4.28)
(-13%)

starting sorting benchmark on 10000 items over 100 iterations

100 x           list msort on  ascending data:    13090ms (ratio  1.00)
100 x          array hsort on  ascending data:     7660ms (ratio  1.71)
100 x          array qsort on  ascending data:     4870ms (ratio  2.69)
100 x          array msort on  ascending data:     2080ms (ratio  6.29)
100 x        array samsort on  ascending data:      540ms (ratio 24.24)

100 x           list msort on descending data:    12440ms (ratio  1.00)
100 x          array hsort on descending data:     4840ms (ratio  2.57)
100 x          array qsort on descending data:     4700ms (ratio  2.65)
100 x          array msort on descending data:     1800ms (ratio  6.91)
100 x        array samsort on descending data:      490ms (ratio 25.39)

100 x           list msort on randomized data:    18970ms (ratio  1.00)
100 x          array hsort on randomized data:     5470ms (ratio  3.47)
100 x          array qsort on randomized data:     4840ms (ratio  3.92)
100 x          array msort on randomized data:     2530ms (ratio  7.50)
100 x        array samsort on randomized data:     2780ms (ratio  6.82)
(-10%)

starting sorting benchmark on 100000 items over 10 iterations

10 x           list msort on  ascending data:    20760ms (ratio  1.00)
10 x          array hsort on  ascending data:     9810ms (ratio  2.12)
10 x          array qsort on  ascending data:     7020ms (ratio  2.96)
10 x          array msort on  ascending data:     2840ms (ratio  7.31)
10 x        array samsort on  ascending data:      690ms (ratio 30.09)

10 x           list msort on descending data:    19930ms (ratio  1.00)
10 x          array hsort on descending data:     6210ms (ratio  3.21)
10 x          array qsort on descending data:     6140ms (ratio  3.25)
10 x          array msort on descending data:     2520ms (ratio  7.91)
10 x        array samsort on descending data:      650ms (ratio 30.66)

10 x           list msort on randomized data:    30770ms (ratio  1.00)
10 x          array hsort on randomized data:     7010ms (ratio  4.39)
10 x          array qsort on randomized data:     5650ms (ratio  5.45)
10 x          array msort on randomized data:     3600ms (ratio  8.55)
10 x        array samsort on randomized data:     3380ms (ratio  9.10) (+6%)

I suspect quite a lot of what we sort is already in fairly good order
so I'd be inclined to use samsort in array.m.

Ralph

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 


-------------- next part --------------
A non-text attachment was scrubbed...
Name: array_sort.m
Type: application/octet-stream
Size: 16552 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/developers/attachments/20010209/863cd88b/attachment.obj>