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