ESI: The Impact on Efficiency
[Page last updated on 2001/02/19 10:29:56.]
Here are the efficiency results
on the impact of structural information for mode analysis.
The experiments were conducted on a PC equipped with an AMD Athlon clocked
at 700 MHz, with 256 MB of main memory, and running
the GNU/Linux operating system (kernel version 2.2.14).
Timings are given in seconds of CPU time as provided by the
getrusage system call.
For those looking at this page through color-enabled devices:
table entries in red indicate that
the integration of explicit structural information led
to a higher fixpoint computation time;
green indicates an improvement;
brown indicates that no such qualitative
conclusion could be drawn (because both analyses timed out).
If you wonder how can we possibly have efficiency improvements
in a non negligible number of cases, you may want to go back
to the explanations.
The symbol * appears near the name of a program
in those cases where CHINA indicates possible incorrectness
of the analysis' results.
See the page on
questions and answers
if this shocks you.
The effect of explicit structural information on efficiency:
fixpoint computation time in seconds.
| goal-independent | goal-dependent |
Program | w/o s.i. | w/ s.i. | w/o s.i. | w/ s.i. |
4colors.pl | 0.09 | 0.09 | 0.10 | 0.10 |
4men.pl | 0.10 | 0.09 | 0.10 | 0.10 |
8puzzle.pl | 0.10 | 0.43 | 0.10 | 0.10 |
LeanTaP.pl | 0.14 | 0.15 | 0.70 | 1.03 |
QG5-7_mg4.pl | 0.25 | 0.28 | -- | -- |
aaaaa.pl | 20.40 | 7.19 | -- | -- |
ac_fix.pl | 0.10 | 0.10 | 0.14 | 0.18 |
action.pl | 0.36 | 0.20 | 3.07 | 2.10 |
aircraft.pl | 0.18 | 0.28 | 0.47 | 1.62 |
ale_hpsg.pl | 142.16 | 582.65 | -- | -- |
all_permutations.pl | 0.09 | 0.10 | 0.14 | 0.36 |
altappend.pl | 0.10 | 0.09 | 0.10 | 0.10 |
ann.pl | 0.25 | 0.37 | 0.61 | 0.62 |
append.pl | 0.09 | 0.09 | 0.10 | 0.10 |
apprevlast.pl | 0.09 | 0.10 | 0.10 | 0.10 |
aqua_c.pl | 35.22 | 12.05 | 58.86 | 482.42 |
arch1.pl | 0.25 | 0.37 | -- | -- |
astar.pl | 0.10 | 0.11 | 0.10 | 0.11 |
attractions.pl | 0.12 | 0.67 | 0.23 | 2.54 |
attractions2.pl | 0.09 | 0.10 | 0.10 | 0.15 |
autoc.pl * | 0.11 | 0.11 | -- | -- |
back52.pl * | 15.68 | 32.45 | -- | -- |
barnes_hut.pl | 0.10 | 0.11 | 0.17 | 0.52 |
bid.pl | 0.10 | 0.10 | 0.10 | 0.10 |
bigot.pl | 0.10 | 0.10 | 0.11 | 0.10 |
bintrees.pl | 0.10 | 0.10 | 0.10 | 0.12 |
birds.pl | 0.10 | 0.10 | 0.10 | 0.11 |
bmtp.pl | 2.00 | 1.65 | -- | -- |
bnet.pl | 0.12 | 0.14 | 0.14 | 0.15 |
bnet2.pl | 0.12 | 0.14 | 0.14 | 0.17 |
boyer_wamcc.pl | 0.10 | 0.11 | 0.34 | 0.30 |
bp0-6.pl | 0.12 | 0.15 | 0.11 | 0.15 |
browse_wamcc.pl | 0.10 | 0.10 | 0.11 | 0.12 |
bryant.pl | 0.20 | 0.20 | 0.81 | 0.82 |
bup-all.pl | 0.15 | 0.11 | -- | -- |
cal_wamcc.pl | 0.09 | 0.10 | 0.10 | 0.10 |
cardsol.pl | 0.10 | 0.10 | 0.10 | 0.11 |
caslog.pl | 10.31 | 4.48 | 25.68 | 55.18 |
cg_parser.pl | 0.18 | 0.21 | -- | -- |
chartgraph.pl | 0.83 | 0.37 | -- | -- |
chasen-all.pl | 0.10 | 0.11 | 0.30 | 0.20 |
chat80.pl | 2.19 | 1.75 | 8.42 | 8.39 |
chat_parser.pl | 0.68 | 0.52 | 1.34 | 1.86 |
chess.pl | 0.11 | 0.37 | 0.20 | 2.63 |
chillin.pl | 1.24 | 1.49 | -- | -- |
circan.pl | 5.15 | 4.17 | 73.80 | 68.59 |
classic.pl | 0.10 | 0.14 | -- | -- |
cobweb.pl | 0.67 | 0.28 | -- | -- |
colan-all.pl * | 9.10 | 1.50 | -- | -- |
color.pl | 0.09 | 0.10 | 0.09 | 0.10 |
compound.pl | 0.09 | 0.09 | 0.10 | 0.07 |
conman.pl | 0.10 | 0.10 | 0.15 | 0.18 |
crip.pl | 0.12 | 0.15 | 0.12 | 0.18 |
cry_add.pl | 0.10 | 0.10 | 0.12 | 0.15 |
cry_mult.pl | 0.10 | 0.10 | 0.14 | 0.23 |
crypt_wamcc.pl | 0.10 | 0.10 | 0.10 | 0.11 |
cs2.pl | 0.12 | 0.34 | 0.10 | 0.12 |
cselcomp.pl | 9.71 | 3.82 | -- | -- |
cugini_utilities.pl | 0.18 | 0.20 | -- | -- |
curry2indy.pl * | 0.33 | 0.33 | 0.41 | 0.72 |
curry2prolog.pl | 1.36 | 1.25 | -- | -- |
custord.pl | 0.09 | 0.10 | 0.09 | 0.10 |
cycles.pl * | 0.14 | 0.18 | 0.68 | 0.73 |
dbqas.pl * | 0.12 | 0.14 | -- | -- |
dcg1.pl | 0.10 | 0.10 | 0.10 | 0.10 |
dcg_jp.pl | 0.10 | 0.10 | -- | -- |
dcg_ok.pl | 0.11 | 0.11 | -- | -- |
demo_fsa2.pl | 0.10 | 0.10 | 0.10 | 0.10 |
dfid.pl | 0.10 | 0.10 | 0.10 | 0.10 |
dfsscc.pl | 0.14 | 0.15 | 0.33 | 0.62 |
dialog.pl | 0.10 | 0.10 | -- | -- |
difflists.pl | 0.10 | 0.10 | -- | -- |
diffsimpsv.pl | 0.15 | 0.15 | 0.28 | 0.25 |
dioph.pl | 0.10 | 0.09 | 0.09 | 0.10 |
disj_r.pl | 0.10 | 0.12 | 0.12 | 0.12 |
dlists.pl | 0.10 | 0.10 | 0.23 | 0.43 |
dposan.pl | 0.15 | 0.23 | 0.60 | 0.70 |
draw.pl | 0.10 | 0.10 | 0.15 | 0.20 |
eliza.pl | 0.12 | 0.17 | 0.50 | 0.68 |
english.pl | 0.10 | 0.10 | 0.11 | 0.14 |
esfm.pl | 0.10 | 0.10 | -- | -- |
essln.pl * | 0.37 | 0.34 | -- | -- |
exp.pl | 0.09 | 0.09 | -- | -- |
ezan.pl | 1.03 | 0.81 | 6.71 | 3.00 |
factors.pl | 0.09 | 0.09 | 0.10 | 0.09 |
famtree_lguzik.pl | 0.11 | 0.11 | 0.10 | 0.10 |
fecht.pl | 0.10 | 0.10 | 0.11 | 0.11 |
fft.pl | 0.10 | 0.10 | 0.11 | 0.14 |
files.pl | 0.15 | 0.14 | -- | -- |
flatten.pl | 0.10 | 0.10 | 0.10 | 0.10 |
foil.pl | 0.15 | 0.20 | -- | -- |
fraction.pl | 0.10 | 0.10 | 0.10 | 0.10 |
french.pl | 0.10 | 0.10 | 0.11 | 0.11 |
fst.pl | 0.10 | 0.09 | 0.10 | 0.10 |
ftfsg.pl | 0.18 | 0.20 | -- | -- |
ftfsg2.pl | 0.18 | 0.20 | -- | -- |
ga.pl | 0.11 | 0.18 | 0.15 | 0.15 |
gauss.pl | 0.09 | 0.10 | 0.10 | 0.10 |
gcd.pl | 0.10 | 0.09 | 0.10 | 0.10 |
gene.pl | 0.10 | 0.10 | -- | -- |
genlang-2.5.pl * | 1.25 | 1.21 | -- | -- |
gilberto.pl | 0.09 | 0.10 | 0.10 | 0.10 |
gnup-1.1.0_pl2wam.pl | 1.70 | 1.70 | 4.86 | 2.67 |
grammar.pl | 0.09 | 0.10 | 0.10 | 0.10 |
grips.pl * | 0.15 | 0.17 | -- | -- |
gulp.pl * | 0.12 | 0.14 | -- | -- |
gulp3.pl | 0.14 | 0.14 | -- | -- |
ham_bshort.pl | 0.11 | 0.11 | 0.18 | 0.18 |
hamiltonian.pl | 0.09 | 0.10 | 0.09 | 0.10 |
hanoiapp.pl | 0.09 | 0.09 | 0.10 | 0.10 |
hebtrans.pl | 0.10 | 0.11 | 0.12 | 0.14 |
idt.pl | 0.11 | 0.18 | -- | -- |
ilap.pl | 0.10 | 0.10 | 0.23 | 0.23 |
ileanTAP.pl | 0.23 | 0.61 | 2.58 | 5.01 |
ili.pl | 0.36 | 0.40 | -- | -- |
ime_v2-2-1.pl | 0.12 | 0.15 | 0.25 | 0.33 |
index.pl * | 2.79 | 0.58 | -- | -- |
indy2curry.pl | 0.10 | 0.14 | 0.15 | 0.18 |
indyv1.8.pl | 1.20 | 1.23 | -- | -- |
intervals.pl | 0.11 | 0.14 | 0.25 | 0.31 |
jugs.pl | 0.10 | 0.11 | 0.27 | 0.23 |
kalah_r.pl | 0.10 | 0.14 | 0.12 | 0.18 |
kilimanjaro-all.pl | 28.18 | 16.05 | -- | -- |
kipeg.pl | 0.10 | 0.10 | 0.10 | 0.34 |
knight.pl | 0.10 | 0.11 | 0.15 | 0.25 |
kore-ie.pl * | 8.18 | 1.63 | -- | -- |
lc.pl | 0.11 | 0.15 | 0.25 | 0.18 |
ldl-all.pl | 10.42 | 8.60 | -- | -- |
leantap_small.pl | 0.11 | 0.10 | 0.15 | 0.18 |
lg_sys.pl | 11.22 | 7.51 | -- | -- |
lgt20.pl * | 2.04 | 0.51 | -- | -- |
life.pl | 0.10 | 0.11 | 0.10 | 0.12 |
lilp.pl | 0.52 | 0.68 | -- | -- |
linTAP.pl | 0.31 | 0.46 | 1.58 | 1.75 |
lin_reg.pl | 0.10 | 0.10 | 0.09 | 0.10 |
linger_old.pl * | 11.60 | 2.36 | -- | -- |
linking1.pl | 0.09 | 0.10 | -- | -- |
linking2.pl | 0.10 | 0.09 | 0.09 | 0.10 |
linloss.pl | 0.09 | 0.10 | 0.09 | 0.09 |
linsys.pl | 0.10 | 0.10 | 0.09 | 0.09 |
linus.pl * | 1.04 | 0.75 | -- | -- |
ljt.pl | 0.56 | 0.54 | 0.12 | 0.15 |
llprover.pl | 0.23 | 0.28 | -- | -- |
lnprolog.pl * | 0.15 | 0.17 | -- | -- |
log_interpreter.pl | 0.44 | 0.37 | -- | -- |
lojban.pl | 1.87 | 0.82 | 4.15 | 1.01 |
lookup.pl | 0.10 | 0.10 | 0.09 | 0.10 |
loops.pl | 0.10 | 0.10 | 0.11 | 0.12 |
lowest.pl | 0.09 | 0.10 | 0.10 | 0.10 |
lpe.pl | 0.18 | 0.20 | -- | -- |
lptp-1.05.pl | 3.36 | 2.89 | 10.05 | 12.65 |
lptp-1.06.pl | 3.35 | 2.85 | 10.02 | 12.68 |
magicex.pl | 0.09 | 0.10 | 0.09 | 0.09 |
map.pl * | 4.40 | 4.73 | -- | -- |
maps.pl | 0.10 | 0.09 | 0.09 | 0.10 |
markus.pl | 23.84 | 2.64 | -- | -- |
mastermind.pl | 0.10 | 0.10 | 0.11 | 0.17 |
math.pl | 0.10 | 0.11 | -- | -- |
mathlib.pl | 0.10 | 0.11 | 0.14 | 0.15 |
matrix.pl | 0.10 | 0.09 | 0.10 | 0.11 |
maze.pl | 0.09 | 0.10 | 0.10 | 0.10 |
mdgtools-1.0.pl | 8.47 | 3.27 | -- | -- |
medic4.pl | 0.10 | 0.10 | -- | -- |
medic5.pl | 0.10 | 0.10 | -- | -- |
meta_qsort_wamcc.pl | 0.10 | 0.10 | 0.11 | 0.10 |
metutor.pl | 0.43 | 0.28 | -- | -- |
mfoil.pl | 2.66 | 0.34 | -- | -- |
mgpl4.pl | 5.57 | 1.84 | 0.73 | 1.12 |
mgtp-g-I-temp.pl | 0.95 | 0.31 | 0.44 | 0.57 |
mixtus-all.pl | 2.40 | 1.85 | -- | -- |
mm.pl | 0.40 | 0.50 | 2.22 | 6.19 |
motel.pl * | 22.31 | 27.51 | -- | -- |
mpuzzle.pl | 0.10 | 0.07 | 0.10 | 0.11 |
mt-all.pl * | 20.50 | 26.46 | -- | -- |
multagnt.pl | 1.72 | 0.14 | -- | -- |
music.pl | 0.47 | 0.23 | 0.67 | 5.40 |
nand_wamcc.pl | 4.92 | 4.36 | 0.20 | 0.40 |
nani.pl | 0.10 | 0.11 | 0.12 | 0.12 |
nbody.pl | 0.12 | 0.17 | 0.34 | 0.87 |
ncDP.pl | 0.11 | 0.14 | 0.10 | 0.12 |
negoplan.pl * | 6.92 | 1.75 | -- | -- |
neural.pl | 0.11 | 0.11 | 0.17 | 0.10 |
newexpobdd.pl | 19.05 | 17.62 | -- | -- |
newton.pl | 0.10 | 0.10 | 0.10 | 0.10 |
nladb.pl | 0.10 | 0.10 | -- | -- |
noughts_and_crosses.pl | 0.10 | 0.10 | 0.10 | 0.12 |
npuzzle.pl | 0.10 | 0.10 | -- | -- |
occ.pl | 0.09 | 0.09 | 0.10 | 0.10 |
ocheck0.pl | 0.10 | 0.09 | 0.10 | 0.09 |
ocheck1.pl | 0.10 | 0.09 | 0.09 | 0.10 |
ocheck2.pl | 0.09 | 0.09 | 0.09 | 0.07 |
ocheck3.pl | 0.09 | 0.10 | 0.09 | 0.09 |
ocheck4.pl | 0.09 | 0.10 | 0.10 | 0.10 |
ocheck5.pl | 0.10 | 0.09 | 0.10 | 0.09 |
ochecklin.pl | 0.09 | 0.10 | 0.09 | 0.07 |
oldchina.pl | 4.71 | 1.86 | 12.46 | 19.12 |
ordsets.pl | 0.10 | 0.10 | 0.10 | 0.11 |
othello.pl | 0.10 | 0.12 | 0.15 | 0.37 |
pairs.pl | 0.09 | 0.09 | 0.11 | 0.10 |
palindrome.pl | 0.09 | 0.10 | 0.10 | 0.10 |
pappiall.pl | 2.50 | 1.59 | -- | -- |
pappienglishall.pl | 1.48 | 1.09 | -- | -- |
parser_dcg.pl | 0.17 | 0.20 | 0.41 | 0.46 |
path.pl | 0.09 | 0.10 | 0.10 | 0.10 |
peephole1.pl | 0.15 | 0.17 | 0.66 | 0.75 |
peg.pl | 0.10 | 0.10 | 0.10 | 0.10 |
pentomino.pl | 0.14 | 0.12 | 0.17 | 0.20 |
permute.pl | 0.10 | 0.10 | 0.10 | 0.12 |
petsan.pl | 1.62 | 5.63 | 14.96 | 9.72 |
peval.pl | 0.37 | 0.61 | -- | -- |
pg.pl | 0.10 | 0.10 | 0.10 | 0.10 |
pillow-1.1.pl | 0.37 | 0.37 | -- | -- |
piza-0.9.22.pl * | 8.46 | 8.50 | -- | -- |
pl2wam.pl | 1.70 | 1.69 | -- | -- |
plaiclp.pl | 1.80 | 0.95 | -- | -- |
plcafe_lib.pl | 0.18 | 0.20 | -- | -- |
pljava.pl | 0.80 | 1.08 | -- | -- |
pmatch.pl | 0.46 | 1.91 | 4.38 | 8.31 |
poly10.pl | 0.10 | 0.11 | 0.10 | 0.10 |
powers.pl | 0.10 | 0.09 | 0.09 | 0.09 |
powerset.pl | 0.09 | 0.09 | 0.10 | 0.10 |
press.pl | 0.18 | 0.40 | 0.56 | 1.23 |
primefactors.pl | 0.09 | 0.10 | 0.10 | 0.10 |
primes.pl | 0.07 | 0.09 | 0.10 | 0.10 |
primes2.pl | 0.09 | 0.10 | 0.10 | 0.10 |
primes3.pl | 0.09 | 0.10 | 0.09 | 0.10 |
prism-1.1.pl * | 0.37 | 0.49 | -- | -- |
prointrp.pl | 0.09 | 0.09 | 0.10 | 0.10 |
prolog.pl | 0.10 | 0.10 | -- | -- |
protein.pl * | 8.72 | 1.26 | -- | -- |
puzzle.pl | 0.44 | 10.00 | 7.61 | 730.61 |
pythagoras.pl | 0.09 | 0.10 | 0.10 | 0.10 |
q8.pl | 0.10 | 0.11 | 0.12 | 0.38 |
qdjanus.pl * | 1.88 | 1.10 | -- | -- |
qmlattice.pl * | 0.34 | 0.41 | -- | -- |
qplan.pl | 0.17 | 0.21 | 0.18 | 0.23 |
queens.pl | 0.10 | 0.10 | 0.10 | 0.10 |
queens8_wamcc.pl | 0.10 | 0.10 | 0.10 | 0.10 |
queens_wamcc.pl | 0.10 | 0.10 | 0.10 | 0.10 |
quotan.pl | 0.34 | 0.37 | 2.85 | 2.36 |
raytrace.pl | 0.14 | 0.18 | 0.28 | 0.46 |
raytrace2.pl | 0.14 | 0.17 | 0.20 | 0.38 |
raytrace_inst.pl | 0.15 | 0.18 | 0.30 | 0.47 |
rdtok.pl | 0.11 | 0.11 | 0.15 | 0.15 |
reach.pl | 0.07 | 0.12 | -- | -- |
read.pl | 0.15 | 0.18 | 0.74 | 0.66 |
reducer.pl | 0.14 | 0.18 | 0.93 | 0.54 |
reform_compiler.pl * | 20.57 | 30.71 | 43.20 | 302.85 |
reg.pl | 1.30 | 1.25 | -- | -- |
river.pl * | 0.10 | 0.09 | -- | -- |
river1.pl * | 0.10 | 0.09 | -- | -- |
robot.pl | 0.10 | 0.10 | 0.15 | 0.18 |
rsp.pl | 0.18 | 0.18 | 0.25 | 0.21 |
rubik.pl | 0.12 | 24.22 | 0.28 | 68.66 |
salvini.pl * | 0.25 | 0.50 | -- | -- |
sax.pl | 4.76 | 3.64 | -- | -- |
sb_asm.pl | 0.15 | 0.15 | 0.67 | 1.05 |
scc.pl | 0.67 | 0.98 | 0.12 | 0.18 |
schedule.pl | 0.10 | 0.09 | 0.10 | 0.10 |
sdda.pl | 0.23 | 0.15 | 2.56 | 0.81 |
search_lguzik.pl | 0.10 | 0.14 | 0.10 | 0.10 |
semi.pl | 0.10 | 0.11 | 0.18 | 0.31 |
semigroup.pl | 76.55 | 26.80 | 2.51 | 2.17 |
sets.pl | 0.10 | 0.10 | 0.10 | 0.11 |
sg_mc_big.pl | 0.15 | 0.18 | 0.79 | 1.42 |
shape.pl | 0.10 | 0.10 | 0.10 | 0.15 |
sharing_enum.pl | 0.15 | 0.17 | 0.30 | 0.31 |
shortest.pl | 0.10 | 0.09 | 0.10 | 0.11 |
sieve.pl | 0.09 | 0.10 | 0.10 | 0.10 |
sim.pl | 0.51 | 0.52 | -- | -- |
sim_v5-2.pl | 0.25 | 0.81 | 0.25 | 0.33 |
simple_analyzer.pl | 0.25 | 0.52 | 2.05 | 1.83 |
slice-all.pl | 0.72 | 1.04 | -- | -- |
som4.pl | 0.10 | 0.10 | -- | -- |
sorts.pl | 0.10 | 0.12 | 0.14 | 0.17 |
sprftp.pl * | 1.59 | 0.54 | 10.68 | 1.79 |
spsys.pl | 1.53 | 1.30 | -- | -- |
stack-opt.pl | 0.10 | 0.10 | 0.11 | 0.10 |
staticcalls.pl | 0.10 | 0.10 | 0.10 | 0.11 |
stats.pl | 0.09 | 0.10 | 0.10 | 0.10 |
strings_texts.pl | 0.15 | 0.17 | -- | -- |
strips.pl | 0.93 | 0.46 | 4.13 | 1.47 |
synth.pl | 1.29 | 0.79 | 14.93 | 5.84 |
tak_wamcc.pl | 0.09 | 0.09 | 0.10 | 0.10 |
ternary.pl | 0.10 | 0.10 | 0.10 | 0.12 |
tictactoe.pl | 0.10 | 0.36 | 0.11 | 0.18 |
trees1.pl | 0.10 | 0.10 | -- | -- |
trees2.pl | 0.10 | 0.10 | -- | -- |
trs.pl | 0.33 | 0.63 | 2.13 | 15.75 |
tsp.pl | 0.10 | 0.11 | 0.14 | 0.15 |
unify.pl | 0.15 | 0.18 | 1.01 | 0.63 |
untupler.pl * | 0.12 | 0.10 | -- | -- |
vhdl97_parser.pl | 1.22 | 1.21 | 15.69 | 12.30 |
vsp.pl | 0.10 | 0.10 | 0.15 | 0.18 |
warplan.pl | 0.10 | 0.10 | -- | -- |
wumpus1.pl | 0.10 | 0.10 | -- | -- |
wumpus2.pl * | 0.15 | 0.18 | -- | -- |
yaqueens.pl | 0.09 | 0.09 | 0.09 | 0.10 |
yasmm.pl | 0.10 | 0.10 | 0.10 | 0.12 |
zebra.pl | 0.09 | 0.09 | 0.10 | 0.11 |
|