contification transformation & benchmarks

Matthew Fluet Matthew Fluet <fluet@CS.Cornell.EDU>
Thu, 8 Feb 2001 11:44:07 -0500 (EST)


I wrote up an alternate transformation routine to work with the alternate
definition of safety using A*.  It's very similar to what I described
yesterday, and does indeed allow contification of those two functions in
logic.  The downside is that it's probably more expensive (time/space) 
than the current implementation.  But I'm thinking about ways of
"batching" all of the contifications at once, so maybe I can get that to
go away. 

I ran through the benchmarks with this new transformation, mostly to see
if the deeper lexical nesting made any appreciable difference.  Nothing
obvious, and it may even have hurt merge. 

Here are the benchmark results.  The first batch was run using the current
transformation, with new using the ancestor based dominator analysis.  The
second batch was run using the new transformation, with new using the
parent based dominator analysis. 

                        none    both    new     new/both
barnes-hut              9.98    7.44    8.52    1.15
checksum                15.57   7.80    7.81    1.00
count-graphs            14.62   10.69   10.70   1.00
fft                     32.55   31.53   30.04   0.95
fib                     6.52    6.52    6.52    1.00
knuth-bendix            11.39   12.33   12.29   1.00
lexgen                  27.61   21.33   21.63   1.01
life                    44.77   34.76   38.42   1.11
logic                   35.95   35.55   35.55   1.00
mandelbrot              56.11   13.02   13.02   1.00
matrix-multiply         14.13   6.74    6.84    1.01
merge                   80.52   77.12   77.10   1.00
mlyacc                  20.31   13.23   13.19   1.00
mpuz                    61.41   26.60   26.60   1.00
nucleic                 12.98   11.24   11.23   1.00
ratio-regions           21.13   13.52   13.56   1.00
raytrace                12.30   12.07   12.80   1.06
simple                  11.95   10.65   10.70   1.00
smith-normal-form       1.67    1.63    1.62    1.00
tak                     15.77   15.77   15.77   1.00
tensor                  53.43   10.85   12.62   1.16
tsp                     25.55   18.44   18.45   1.00
vliw                    16.18   10.94   10.91   1.00
wc                      5.48    3.87    3.86    1.00
zern                    27.97   12.85   11.47   0.89
avg                     25.43   17.06   17.25

                        new     both    new     new/both
barnes-hut              10.05   7.45    8.54    1.15
checksum                15.67   7.81    7.81    1.00
count-graphs            14.77   10.76   10.76   1.00
fft                     32.90   32.15   30.66   0.95
fib                     6.52    6.52    6.51    1.00
knuth-bendix            11.40   12.33   12.30   1.00
lexgen                  27.70   21.36   21.31   1.00
life                    45.08   34.95   38.58   1.10
logic                   36.17   35.76   35.77   1.00
mandelbrot              57.07   13.01   13.02   1.00
matrix-multiply         14.19   6.73    6.76    1.01
merge                   81.56   77.66   81.89   1.05
mlyacc                  20.50   13.27   13.28   1.00
mpuz                    61.65   26.59   26.60   1.00
nucleic                 13.05   11.27   11.26   1.00
ratio-regions           21.18   13.55   13.58   1.00
raytrace                12.27   12.06   12.85   1.07
simple                  11.99   10.68   10.73   1.00
smith-normal-form       1.66    1.63    1.62    1.00
tak                     15.78   15.77   15.77   1.00
tensor                  53.83   10.85   12.63   1.16
tsp                     25.56   18.45   18.45   1.00
vliw                    16.25   10.97   10.88   0.99
wc                      5.48    3.94    3.86    0.98
zern                    28.17   12.84   11.47   0.89
avg                     25.62   17.13   17.48