polyvariance costs
Stephen Weeks
sweeks@research.nj.nec.com
Wed, 24 Feb 1999 14:54:59 -0500
Here are the polyvariance thresholds for the benchmark runs from last
night. For each benchmark, there are two rounds of polyvariance,
which occur immediately after monomorphisation. Each round outputs a
list of the higher-order functions sorted in increasing order of cost,
where cost is (numOccurrences - 1) * (size - 30). Each line is of the
form:
function-name size numOccurrences cost
The first and second rounds of polyariance are separated by a blank
line. For many benchmarks, the second round encountered no higher
order functions, hence there is no data for the second round.
The cost cutoff used for running the benchmarks was 300, i.e., a
higher-order function is duplicated everywhere if its cost is <= 300.
--------------------------------------------------------------------------------
barnes-hut
wrap_0 0 4 ~60
tabulate_0 10 2 ~10
foldl_0 22 2 2
foldl_1 22 2 2
foldl_2 22 2 2
makeTest_0 24 3 8
app_0 29 2 9
--------------------------------------------------------------------------------
count-graphs
wrap_0 0 3 ~40
fold_0 22 2 2
foldl_0 22 2 2
foldl_1 22 2 2
makeTest_0 24 3 8
naturalFold_0 35 2 15
tabulate_0 40 2 20
memoize_0 88 2 68
--------------------------------------------------------------------------------
fft
wrap_0 0 4 ~60
foldl_0 22 2 2
foldl_1 22 2 2
makeTest_0 24 3 8
tabulate_0 36 2 16
--------------------------------------------------------------------------------
knuth-bendix
wrap_0 0 2 ~20
x_0 5 2 ~15
exists_0 15 4 ~15
app_0 10 2 ~10
gt_ord_0 11 2 ~9
ge_ord_0 11 2 ~9
map_0 12 2 ~8
map_1 12 2 ~8
map_2 12 2 ~8
map_3 12 2 ~8
for_all_0 15 2 ~5
it_list_0 15 2 ~5
foldl_0 22 2 2
foldl_1 22 2 2
makeTest_0 24 3 8
app_1 29 2 9
it_list2_0 33 2 13
--------------------------------------------------------------------------------
lexgen
wrap_0 0 3 ~40
create_0 3 3 ~34
create_1 3 3 ~34
MakeString_0 15 2 ~5
foldl_0 22 2 2
foldl_1 22 2 2
foldl_2 22 2 2
foldl_3 22 3 4
app_0 29 2 9
flushGen_0 30 2 10
makeTest_0 24 4 12
tabulate_0 36 2 16
tabulate_1 36 2 16
modifyi_0 49 2 29
MakeString_1 15 1 0
MakeString_2 15 1 0
--------------------------------------------------------------------------------
life
accumulate_0 15 8 ~35
wrap_0 0 2 ~20
o_0 9 2 ~11
map_0 16 2 ~4
foldl_0 22 2 2
foldl_1 22 2 2
makeTest_0 24 4 12
filter_0 24 7 24
map_1 16 1 0
map_2 16 1 0
--------------------------------------------------------------------------------
logic
exists_0 5 66 ~975
unify_0 10 39 ~380
x_0 1 3 ~38
x_1 8 3 ~24
wrap_0 0 2 ~20
x_2 1 2 ~19
x_3 8 2 ~12
solitaire_0 225 1 0
x_4 224 1 0
x_5 346 1 0
x_6 1306 1 0
x_7 85 1 0
x_8 37 1 0
makeTest_0 24 2 4
trail_0 21 14 13
x_9 94 5 296
unify_REF_0 95 5 300
rotate_0 347 4 981
move_horiz_0 1307 3 2574
unifys_0 124 39 3952
solitaire_1 378 1 0
x_10 377 1 0
x_11 388 1 0
x_12 1705 1 0
x_13 35 1 0
x_14 525 1 0
rotate_1 389 4 1107
move_horiz_1 1706 3 3372
unifyP_0 562 39 20596
--------------------------------------------------------------------------------
mandelbrot
wrap_0 0 4 ~60
makeTest_0 24 4 12
--------------------------------------------------------------------------------
matrix-multiply
wrap_0 0 3 ~40
foreach_0 33 2 13
--------------------------------------------------------------------------------
mlyacc
o_0 9 8 ~77
o_1 9 5 ~44
wrap_0 0 3 ~40
foldr_0 12 2 ~8
foldr_1 12 2 ~8
foldr_2 12 2 ~8
foldr_3 12 2 ~8
foldr_4 12 2 ~8
foldr_5 12 2 ~8
make_0 15 2 ~5
make_1 15 2 ~5
app_0 18 2 ~2
closureP_0 50 1 0
closureP_1 50 1 0
map_0 20 2 0
foldl_0 22 2 2
foldl_1 22 2 2
foldl_2 22 2 2
foldl_3 22 2 2
foldl_4 22 2 2
foldl_5 22 2 2
foldl_6 22 2 2
foldl_7 22 2 2
foldl_8 22 2 2
foldl_9 22 2 2
foldl_10 22 2 2
foldl_11 22 2 2
foldl_12 22 2 2
foldl_13 22 2 2
foldl_14 22 2 2
foldl_15 22 2 2
foldl_16 22 2 2
foldl_17 22 2 2
foldl_18 22 2 2
fold_0 24 2 4
foldl_19 22 3 4
foldl_20 22 3 4
foldl_21 22 3 4
foldl_22 22 3 4
foldl_23 22 3 4
foldl_24 22 3 4
printTable_0 26 2 6
foldl_25 22 4 6
scanRhs_0 27 2 7
exists_0 27 2 7
exists_1 27 2 7
exists_2 27 2 7
app_1 29 2 9
app_2 29 2 9
app_3 29 2 9
app_4 29 2 9
app_5 29 2 9
app_6 29 2 9
foldr_6 29 2 9
foldr_7 29 2 9
foldr_8 29 2 9
flushGen_0 30 2 10
x_0 32 2 12
makeTest_0 24 4 12
map_1 32 2 12
tabulate_0 36 2 16
tabulate_1 36 2 16
tabulate_2 36 2 16
x_1 37 2 17
catList_0 38 2 18
foldr_9 29 3 18
app_7 29 4 27
modifyi_0 49 2 29
app_8 29 5 36
app_9 29 6 45
prAction_0 70 2 50
x_2 77 2 57
prItem_0 101 2 81
map_2 32 8 84
printSummary_0 191 2 171
x_3 62 6 210
catList_1 63 6 215
closureP_2 71 1 0
closureP_3 71 1 0
--------------------------------------------------------------------------------
nucleic
wrap_0 0 4 ~60
atom_pos_0 11 2 ~9
search_aux_0 84 1 0
x_0 21 1 0
x_1 20 1 0
x_2 61 1 0
x_3 60 1 0
foldl_0 22 2 2
foldl_1 22 2 2
makeTest_0 24 3 8
search_aux_1 101 1 0
x_4 21 1 0
x_5 20 1 0
x_6 78 1 0
x_7 77 1 0
--------------------------------------------------------------------------------
ratio-regions
wrap_0 0 3 ~40
foldl_0 22 2 2
makeTest_0 24 4 12
for_each_0 33 2 13
tabulate_0 36 2 16
every_n_0 27 4 21
tabulate_1 49 2 29
doo_0 22 21 40
--------------------------------------------------------------------------------
simple
reflect_0 9 16 ~165
o_0 9 8 ~77
wrap_0 0 4 ~60
for_north_zones_0 14 8 ~42
for_west_zones_0 18 8 ~14
for_south_zones_0 18 8 ~14
r_area_vol_den_0 16 4 ~12
u2_0 17 4 ~9
for_interior_nodes_0 18 3 ~4
for_west_ward_interior_zones_0 25 1 0
for_north_ward_interior_zones_0 25 1 0
x_0 63 1 0
foldl_0 22 2 2
foldl_1 22 2 2
foldl_2 22 2 2
foldl_3 22 2 2
do_zones_0 22 4 6
app_0 29 2 9
flushGen_0 30 2 10
makeTest_0 24 4 12
for_east_zones_0 22 8 14
fold_0 28 3 16
tabulate_0 36 2 16
make_theta_0 37 2 17
boundary_p_0 26 4 18
map_interior_zones_0 29 3 18
for_interior_zones_0 25 13 60
map_0 32 6 60
make_gamma_0 94 2 74
map_1 32 8 84
make_ab_0 106 2 86
map_2 57 4 111
map_3 57 8 259
make_position_matrix_0 289 2 269
reflect_node_0 101 24 1863
for_0 64 81 3520
x_1 63 1 0
reflect_node_1 137 12 1287
reflect_node_2 137 12 1287
for_1 64 81 3520
--------------------------------------------------------------------------------
tsp
wrap_0 0 4 ~60
make_0 15 2 ~5
make_1 15 2 ~5
foldl_0 22 2 2
foldl_1 22 2 2
foldl_2 22 2 2
makeTest_0 24 3 8
app_0 29 2 9
--------------------------------------------------------------------------------
vliw
makeEQ_0 3 7 ~102
newdag_0 1 5 ~76
wrap_0 0 4 ~60
o_0 9 5 ~44
debug_0 16 9 ~32
foldr_0 12 5 ~32
fold_0 10 4 ~30
updt_sel_0 12 4 ~24
o_1 9 3 ~22
o_2 9 3 ~22
x_0 1 2 ~19
x_1 1 2 ~19
x_2 1 2 ~19
makeEQ_1 3 2 ~17
x_3 4 2 ~16
x_4 5 2 ~15
time_0 6 2 ~14
fold_1 17 5 ~12
o_3 9 2 ~11
o_4 9 2 ~11
o_5 9 2 ~11
o_6 9 2 ~11
o_7 9 2 ~11
o_8 9 2 ~11
o_9 9 2 ~11
foldr_1 12 2 ~8
foldr_2 12 2 ~8
make_0 15 2 ~5
make_1 15 2 ~5
read_write_debug_0 16 2 ~4
live_dbg_0 20 2 0
write_dbg_0 20 7 0
cp_debug_0 20 4 0
mt_debug_0 20 6 0
del_debug_0 20 6 0
dead_debug_0 20 4 0
p_n_debug_0 20 3 0
map_0 20 4 0
map_1 20 5 0
x_5 21 2 1
mapOpt_0 22 2 2
foldl_0 22 2 2
foldl_1 22 2 2
foldl_2 22 2 2
foldl_3 22 2 2
foldl_4 22 2 2
foldl_5 22 3 4
app_0 29 2 9
flushGen_0 30 2 10
foldl_6 22 6 10
foldl_7 22 6 10
makeTest_0 24 4 12
map_2 32 2 12
map_3 32 2 12
map_4 32 2 12
foldl_8 22 7 12
fold_2 34 2 14
foldl_9 22 8 14
listToSetEQ_0 36 2 16
wrap_1 24 5 16
tabulate_0 36 2 16
tabulate_1 36 2 16
tabulate_2 36 2 16
listUnionEQ_0 40 2 20
map_5 32 3 24
app_1 29 5 36
x_6 59 2 39
digitsExact_0 60 2 40
fold_3 34 4 42
fold_4 34 4 42
map_6 32 5 48
memoize_0 72 2 52
map_7 32 6 60
chk_0 86 2 66
map_8 32 8 84
mop_debug_0 27 15 98
fold_5 34 10 126
--------------------------------------------------------------------------------
zern
wrap_0 0 4 ~60
unop_0 20 3 0
foldl_0 22 2 2
foldl_1 22 2 2
x_0 21 5 4
dotimes_0 22 5 8
makeTest_0 24 3 8
tabulate_0 36 2 16
--------------------------------------------------------------------------------