[MLton-devel] common argument optimization
Matthew Fluet
MLton@mlton.org
Thu, 27 Mar 2003 15:52:36 -0500 (EST)
If anyone is interested, here are a few more results. Bottom line:
putting commonArg after flatten can be a little better; commonArg using
dominators is better than commonArg using "exactly one syntactic actual"
(i.e., the analogy of the contification call analysis).
I built MLton with the SSA optimization pipeline like:
("loopInvariant", LoopInvariant.loopInvariant),
("localRef", LocalRef.eliminate),
("commonArg1", CommonArg.eliminate),
("flatten", Flatten.flatten),
("localFlatten3", LocalFlatten.flatten),
("commonArg2", CommonArg.eliminate),
("commonSubexp", CommonSubexp.eliminate),
("commonBlock", CommonBlock.eliminate),
The benchmarks with the (improved) dominator analysis look like the
following. Note that the hamlet benchmark has no slowdown in compile time
(in fact, simplifications opened up by commonArg resulted in a faster
(backend and codegen presumably) compile time). In most cases, using
commonArg1 or commonArg2 result in identical code, but occassionally
(notably hamlet, knuth-bendix, and raytrace), using commonArg2 is better
than commonArg1.
The benchmarks with an improved argument analysis are further below. In
the majority of cases, they aren't significantly worse than with the
dominator anlaysis, although count-graphs is notably slower with argument.
Also, looking at the program sizes shows that often argument is just as
good as dominator.
** Dominator **
MLton0 -- mlton -drop-pass commonArg1 -drop-pass commonArg2
MLton1 -- mlton -drop-pass commonArg1
MLton2 -- mlton -drop-pass commonArg2
compile time
benchmark MLton0 MLton1 MLton2
barnes-hut 2.03 2.11 2.05
boyer 3.92 3.98 4.02
checksum 0.62 0.65 0.61
count-graphs 1.41 1.37 1.40
DLXSimulator 3.29 3.19 3.18
fft 1.09 1.06 1.07
fib 0.61 0.63 0.62
hamlet 46.47 45.41 45.47
imp-for 0.65 0.65 0.66
knuth-bendix 1.97 1.98 2.00
lexgen 4.48 4.46 4.43
life 1.24 1.27 1.20
logic 2.47 2.45 2.41
mandelbrot 0.66 0.64 0.67
matrix-multiply 0.70 0.71 0.68
md5 1.05 1.08 1.07
merge 0.63 0.69 0.63
mlyacc 19.70 19.87 19.45
model-elimination 19.44 19.41 19.14
mpuz 0.82 0.80 0.78
nucleic 78.89 79.02 79.15
peek 0.93 0.90 0.86
psdes-random 0.64 0.66 0.66
ratio-regions 1.98 1.94 1.99
ray 3.16 3.02 3.04
raytrace 9.17 7.65 7.52
simple 5.30 5.34 5.40
smith-normal-form 6.17 6.15 6.15
tailfib 0.64 0.61 0.60
tak 0.68 0.59 0.62
tensor 2.51 2.44 2.45
tsp 1.28 1.30 1.31
tyan 3.15 3.17 3.22
vector-concat 0.70 0.73 0.68
vector-rev 0.66 0.64 0.64
vliw 11.69 11.39 11.47
wc-input1 1.25 1.29 1.34
wc-scanStream 1.27 1.32 1.30
zebra 3.21 3.30 3.23
zern 0.99 0.95 0.95
run time
benchmark MLton0 MLton1 MLton2
barnes-hut 49.17 48.09 48.06
boyer 55.79 55.85 55.84
checksum 47.34 47.28 47.28
count-graphs 43.10 40.10 40.12
DLXSimulator 91.84 93.81 93.50
fft 34.67 34.87 34.58
fib 49.51 49.51 49.50
hamlet 53.50 51.45 51.87
imp-for 51.62 51.62 51.62
knuth-bendix 39.88 38.34 39.87
lexgen 41.16 41.05 41.10
life 55.01 52.42 52.42
logic 60.04 59.88 60.01
mandelbrot 54.77 54.77 54.77
matrix-multiply 31.15 31.14 31.18
md5 143.25 143.16 143.22
merge 84.47 83.60 83.44
mlyacc 39.12 39.30 39.31
model-elimination 72.26 72.64 72.67
mpuz 38.94 38.94 38.94
nucleic 41.61 41.51 41.67
peek 39.83 39.84 39.83
psdes-random 24.12 24.12 24.12
ratio-regions 36.98 37.05 36.73
ray 28.93 28.84 28.94
raytrace 42.73 40.73 41.16
simple 51.98 51.93 52.02
smith-normal-form 51.99 52.03 52.09
tailfib 46.29 46.29 46.30
tak 89.04 89.04 89.03
tensor 32.06 32.06 32.06
tsp 66.98 66.91 66.91
tyan 58.66 58.87 58.69
vector-concat 92.52 92.74 94.17
vector-rev 110.98 110.89 110.56
vliw 46.43 46.09 46.17
wc-input1 100.69 100.57 100.59
wc-scanStream 92.21 92.21 92.22
zebra 48.35 48.34 48.35
zern 41.92 41.65 41.68
run time ratio
benchmark MLton1 MLton2
barnes-hut 0.98 0.98
boyer 1.00 1.00
checksum 1.00 1.00
count-graphs 0.93 0.93
DLXSimulator 1.02 1.02
fft 1.01 1.00
fib 1.00 1.00
hamlet 0.96 0.97
imp-for 1.00 1.00
knuth-bendix 0.96 1.00
lexgen 1.00 1.00
life 0.95 0.95
logic 1.00 1.00
mandelbrot 1.00 1.00
matrix-multiply 1.00 1.00
md5 1.00 1.00
merge 0.99 0.99
mlyacc 1.00 1.01
model-elimination 1.01 1.01
mpuz 1.00 1.00
nucleic 1.00 1.00
peek 1.00 1.00
psdes-random 1.00 1.00
ratio-regions 1.00 0.99
ray 1.00 1.00
raytrace 0.95 0.96
simple 1.00 1.00
smith-normal-form 1.00 1.00
tailfib 1.00 1.00
tak 1.00 1.00
tensor 1.00 1.00
tsp 1.00 1.00
tyan 1.00 1.00
vector-concat 1.00 1.02
vector-rev 1.00 1.00
vliw 0.99 0.99
wc-input1 1.00 1.00
wc-scanStream 1.00 1.00
zebra 1.00 1.00
zern 0.99 0.99
size
benchmark MLton0 MLton1 MLton2
barnes-hut 116,588 116,492 116,492
boyer 137,555 137,595 137,571
checksum 51,187 51,187 51,187
count-graphs 69,475 68,891 68,891
DLXSimulator 108,068 105,876 105,876
fft 59,711 58,567 58,567
fib 51,187 51,187 51,187
hamlet 1,234,900 1,173,740 1,174,572
imp-for 51,179 51,179 51,179
knuth-bendix 92,508 92,380 92,412
lexgen 164,785 161,921 161,953
life 71,187 71,083 71,043
logic 110,411 110,411 110,411
mandelbrot 51,299 51,299 51,299
matrix-multiply 51,755 51,755 51,755
md5 60,300 60,300 60,300
merge 52,507 52,507 52,507
mlyacc 481,105 472,833 472,897
model-elimination 607,972 600,572 600,716
mpuz 56,227 56,195 56,195
nucleic 198,003 198,003 198,035
peek 58,748 58,612 58,612
psdes-random 51,891 51,891 51,891
ratio-regions 69,587 69,587 69,587
ray 114,724 111,780 111,460
raytrace 279,201 213,153 213,313
simple 193,551 193,599 193,599
smith-normal-form 192,592 191,472 191,480
tailfib 50,987 50,987 50,987
tak 51,395 51,395 51,395
tensor 114,895 114,735 114,735
tsp 65,220 65,156 65,156
tyan 111,764 111,556 111,588
vector-concat 52,355 52,355 52,355
vector-rev 51,563 51,563 51,563
vliw 324,813 313,517 313,725
wc-input1 71,809 71,681 71,649
wc-scanStream 72,457 72,313 72,313
zebra 123,836 123,836 123,836
zern 56,982 56,918 56,918
** Argument **
MLton0 -- mlton -drop-pass commonArg1 -drop-pass commonArg2
MLton1 -- mlton -drop-pass commonArg1
MLton2 -- mlton -drop-pass commonArg2
compile time
benchmark MLton0 MLton1 MLton2
barnes-hut 2.10 2.04 2.12
boyer 3.97 3.88 4.01
checksum 0.63 0.63 0.61
count-graphs 1.42 1.40 1.38
DLXSimulator 3.34 3.12 3.15
fft 1.08 1.09 1.08
fib 0.61 0.64 0.60
hamlet 46.26 45.99 45.87
imp-for 0.62 0.62 0.68
knuth-bendix 1.99 1.95 2.00
lexgen 4.47 4.48 4.49
life 1.27 1.30 1.29
logic 2.47 2.46 2.41
mandelbrot 0.62 0.67 0.67
matrix-multiply 0.67 0.68 0.71
md5 1.08 1.09 1.06
merge 0.66 0.64 0.67
mlyacc 19.45 19.89 19.45
model-elimination 19.45 19.48 19.79
mpuz 0.83 0.78 0.81
nucleic 79.18 78.76 78.83
peek 0.91 0.89 0.91
psdes-random 0.64 0.65 0.70
ratio-regions 2.01 1.98 1.94
ray 3.13 3.11 3.13
raytrace 9.23 8.68 8.85
simple 5.39 5.46 5.34
smith-normal-form 6.06 6.06 6.13
tailfib 0.67 0.62 0.63
tak 0.64 0.59 0.63
tensor 2.42 2.44 2.44
tsp 1.30 1.31 1.28
tyan 3.13 3.15 3.13
vector-concat 0.69 0.69 0.71
vector-rev 0.64 0.66 0.69
vliw 11.67 11.45 11.48
wc-input1 1.30 1.27 1.23
wc-scanStream 1.35 1.30 1.30
zebra 3.21 3.24 3.30
zern 0.97 0.99 0.97
run time
benchmark MLton0 MLton1 MLton2
barnes-hut 49.09 48.19 48.10
boyer 55.66 55.91 55.80
checksum 47.28 47.34 47.28
count-graphs 43.13 42.52 42.85
DLXSimulator 91.90 93.83 93.40
fft 36.02 36.12 36.62
fib 49.50 49.50 49.50
hamlet 53.48 53.77 53.60
imp-for 51.62 51.62 51.62
knuth-bendix 39.88 39.84 39.86
lexgen 41.17 41.05 41.04
life 55.00 52.52 52.51
logic 59.98 60.13 60.11
mandelbrot 54.77 54.77 54.77
matrix-multiply 31.58 31.38 31.50
md5 143.17 143.14 143.18
merge 84.58 84.04 83.61
mlyacc 39.02 39.48 38.36
model-elimination 72.39 72.75 72.49
mpuz 38.94 38.94 38.94
nucleic 41.59 41.62 41.50
peek 39.83 39.84 39.83
psdes-random 24.12 24.12 24.12
ratio-regions 36.94 36.51 36.81
ray 28.90 28.91 29.02
raytrace 42.77 42.04 42.64
simple 52.07 51.94 51.95
smith-normal-form 52.00 51.84 52.12
tailfib 46.28 46.28 46.29
tak 89.03 89.04 89.04
tensor 32.06 32.06 32.06
tsp 66.86 67.13 66.89
tyan 58.60 58.80 58.74
vector-concat 92.68 93.63 92.44
vector-rev 110.17 110.82 110.44
vliw 46.17 46.20 46.22
wc-input1 100.43 100.64 100.53
wc-scanStream 91.83 91.61 91.63
zebra 48.34 48.49 48.34
zern 41.66 41.91 41.74
run time ratio
benchmark MLton1 MLton2
barnes-hut 0.98 0.98
boyer 1.00 1.00
checksum 1.00 1.00
count-graphs 0.99 0.99
DLXSimulator 1.02 1.02
fft 1.00 1.02
fib 1.00 1.00
hamlet 1.01 1.00
imp-for 1.00 1.00
knuth-bendix 1.00 1.00
lexgen 1.00 1.00
life 0.95 0.95
logic 1.00 1.00
mandelbrot 1.00 1.00
matrix-multiply 0.99 1.00
md5 1.00 1.00
merge 0.99 0.99
mlyacc 1.01 0.98
model-elimination 1.00 1.00
mpuz 1.00 1.00
nucleic 1.00 1.00
peek 1.00 1.00
psdes-random 1.00 1.00
ratio-regions 0.99 1.00
ray 1.00 1.00
raytrace 0.98 1.00
simple 1.00 1.00
smith-normal-form 1.00 1.00
tailfib 1.00 1.00
tak 1.00 1.00
tensor 1.00 1.00
tsp 1.00 1.00
tyan 1.00 1.00
vector-concat 1.01 1.00
vector-rev 1.01 1.00
vliw 1.00 1.00
wc-input1 1.00 1.00
wc-scanStream 1.00 1.00
zebra 1.00 1.00
zern 1.01 1.00
size
benchmark MLton0 MLton1 MLton2
barnes-hut 116,588 116,492 116,492
boyer 137,555 137,595 137,571
checksum 51,187 51,187 51,187
count-graphs 69,475 69,011 69,011
DLXSimulator 108,068 105,876 105,876
fft 59,711 58,567 58,567
fib 51,187 51,187 51,187
hamlet 1,234,900 1,208,156 1,208,684
imp-for 51,179 51,179 51,179
knuth-bendix 92,508 92,412 92,412
lexgen 164,785 162,129 162,129
life 71,187 71,083 71,043
logic 110,411 110,411 110,411
mandelbrot 51,299 51,299 51,299
matrix-multiply 51,755 51,755 51,755
md5 60,300 60,300 60,300
merge 52,507 52,507 52,507
mlyacc 481,105 472,945 472,161
model-elimination 607,972 602,076 602,156
mpuz 56,227 56,195 56,195
nucleic 198,003 198,003 198,035
peek 58,748 58,612 58,612
psdes-random 51,891 51,891 51,891
ratio-regions 69,587 69,587 69,587
ray 114,724 111,828 111,604
raytrace 279,201 269,457 269,601
simple 193,551 193,599 193,599
smith-normal-form 192,592 191,472 191,480
tailfib 50,987 50,987 50,987
tak 51,395 51,395 51,395
tensor 114,895 114,735 114,735
tsp 65,220 65,156 65,156
tyan 111,764 111,556 111,588
vector-concat 52,355 52,355 52,355
vector-rev 51,563 51,563 51,563
vliw 324,813 313,853 314,077
wc-input1 71,809 71,681 71,649
wc-scanStream 72,457 72,313 72,313
zebra 123,836 123,836 123,836
zern 56,982 56,918 56,918
-------------------------------------------------------
This SF.net email is sponsored by:
The Definitive IT and Networking Event. Be There!
NetWorld+Interop Las Vegas 2003 -- Register today!
http://ads.sourceforge.net/cgi-bin/redirect.pl?keyn0001en
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel