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