redundant tests
Stephen Weeks
MLton@sourcelight.com
Fri, 3 Aug 2001 11:50:36 -0700
I ran benchmarks last night for the simple dominator-based redundant-tests
algorithm that I implemented. If the edge leading out of a conditional test
(e.g x < y) dominates another instance of the same test, then the subsequent
test is eliminated. Following are the resuls. No benchmarks were hurt, and a
few (fft, tsp, zern) sped up a little. In all of those cases, the speedup was
probably due to repeated bounds checks from code like
Array.update (a, i, 1 + Array.sub (a, i)).
run time ratio
benchmark stable MLton
barnes-hut 1.0
checksum 1.0
count-graphs 1.0
DLXSimulator 1.0
fft 1.1
fib 1.0
hamlet 1.0
knuth-bendix 1.0
lexgen 1.0
life 1.0
logic 1.0
mandelbrot 1.0
matrix-multiply 1.0
md5 1.0
merge 1.0
mlyacc 1.0
mpuz 1.0
nucleic 1.0
peek 1.0
psdes-random 1.0
ratio-regions 1.0
ray 1.0
raytrace 1.0
simple 1.0
smith-normal-form 1.0
tailfib 1.0
tak 1.0
tensor 1.1
tsp 1.0
vector-concat 1.0
vector-rev 1.0
vliw 1.0
wc-input1 1.0
wc-scanStream 1.0
zebra 1.0
zern 1.1
compile time
benchmark MLton stable MLton
barnes-hut 2.7 2.7
checksum 0.8 0.8
count-graphs 1.9 1.9
DLXSimulator 4.6 4.5
fft 1.4 1.4
fib 0.7 0.7
hamlet 54.5 53.1
knuth-bendix 2.5 2.5
lexgen 5.8 5.6
life 1.4 1.4
logic 7.8 7.7
mandelbrot 0.8 0.8
matrix-multiply 0.8 0.8
md5 2.9 2.9
merge 0.8 0.8
mlyacc 20.4 20.1
mpuz 1.0 1.0
nucleic 4.3 4.3
peek 1.1 1.1
psdes-random 0.8 0.8
ratio-regions 3.1 3.1
ray 3.5 3.5
raytrace 10.4 10.4
simple 7.0 7.0
smith-normal-form 8.0 7.9
tailfib 0.7 0.7
tak 0.7 0.7
tensor 3.0 2.9
tsp 1.8 1.8
vector-concat 0.8 0.8
vector-rev 0.8 0.8
vliw 13.2 12.9
wc-input1 1.6 1.6
wc-scanStream 1.7 1.7
zebra 5.3 5.3
zern 1.1 1.1
run time
benchmark MLton stable MLton
barnes-hut 5.3 5.3
checksum 4.5 4.5
count-graphs 6.2 6.0
DLXSimulator 14.0 13.9
fft 8.9 9.4
fib 4.7 4.7
hamlet 10.0 10.1
knuth-bendix 8.5 8.4
lexgen 13.5 14.1
life 10.7 10.7
logic 27.6 27.6
mandelbrot 10.4 10.4
matrix-multiply 6.2 6.3
md5 5.0 5.0
merge 40.9 41.0
mlyacc 11.0 10.9
mpuz 6.8 6.8
nucleic 8.4 8.4
peek 4.9 4.9
psdes-random 5.6 5.6
ratio-regions 9.5 9.6
ray 5.3 5.3
raytrace 6.5 6.5
simple 7.4 7.4
smith-normal-form 1.1 1.1
tailfib 25.1 25.1
tak 10.5 10.5
tensor 7.3 8.2
tsp 12.6 12.6
vector-concat 7.6 7.6
vector-rev 3.2 3.2
vliw 7.3 7.3
wc-input1 3.0 3.0
wc-scanStream 4.4 4.4
zebra 3.2 3.2
zern 42.7 44.8
size
benchmark MLton stable MLton
barnes-hut 65,544 65,544
checksum 23,964 23,964
count-graphs 45,884 45,932
DLXSimulator 98,932 99,444
fft 31,840 32,816
fib 23,932 23,932
hamlet 1,120,135 1,120,199
knuth-bendix 68,101 68,101
lexgen 139,484 139,724
life 38,836 38,836
logic 161,356 161,356
mandelbrot 23,948 23,948
matrix-multiply 24,460 24,476
md5 37,805 37,805
merge 25,252 25,252
mlyacc 468,068 469,820
mpuz 29,780 29,780
nucleic 62,020 62,020
peek 30,653 30,685
psdes-random 24,988 24,988
ratio-regions 62,412 64,348
ray 76,087 76,103
raytrace 192,028 192,732
simple 175,288 175,288
smith-normal-form 141,180 142,508
tailfib 23,636 23,636
tak 23,988 23,988
tensor 66,755 67,091
tsp 40,901 40,901
vector-concat 24,660 24,660
vector-rev 24,500 24,500
vliw 304,136 304,872
wc-input1 40,669 40,685
wc-scanStream 43,293 43,309
zebra 119,253 119,253
zern 28,087 28,231