Hi
I just stumbled upon this paper. While i just skimmed over it it seems as if
the authors say that their algorithm is more efficient than the llvm 2.3
algorithm? So i thought that might be interesting?
Disclaimer: I have no affiliation with the authors and stumbled in a slightly
unrelated search over this paper.
ST
Don't trust it. The abstract clearly states they're counting the number of
dynamic spills. That has almost nothing to do with performance.
Someone would have to reproduce their experiment to verify that performance
indeed improves.
And alas, our field is notoriously unscientific in this respect.
Reproducability of experiments is nonexistant.
-Dave
> Hi
>
> I just stumbled upon this paper. While i just skimmed over it it seems as
> if the authors say that their algorithm is more efficient than the llvm 2.3
> algorithm? So i thought that might be interesting?
>
> http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun09cc.pdf
As the author of this paper I have to defend it now (of course 
Don't trust it. The abstract clearly states they're counting the number of
dynamic spills. That has almost nothing to do with performance.
So if not the number of dynamic spills/reloads and rematerialisations.
What else can you do to measure the quality of your spilling algorithm?
I admit that the impressive numbers in spill translate to smaller gains
in the range of 1-5% also it's hard to compare 2 different compilers.
Nonetheless we produce faster x86 code than llvm-2.3 for several spec
benchmarks (and produce way slower code for some others where I suspect
missing architecture neutral optimisations in firm).
Someone would have to reproduce their experiment to verify that performance
indeed improves.
You can easily download libfirm-1.17.0 and cparser-0.9.9 from
http://www.libfirm.org and see for yourself.
If you're interested in the valgrind hacks to count the spills/reloads,
I uploaded them here:
pp.info.uni-karlsruhe.de/~matze/valgrind-3.5.0-countmem.tgz (there's a
new valgrind plugin called 'countmem' in it).
Greetings,
Matthias Braun
As the author of this paper I have to defend it now (of course
I hope you don't take my comments personally. They are directed to all
research organizations. The fact that our field doesn't demand
reproducability is a scandal. Hard sciences require independent verification
for publication and we should do the same.
We should also publish negative results. The fact that such papers are
rejected outright is another pet peeve of mine. So many cycles wasted
chasing after things other people already found aren't useful...
> Don't trust it. The abstract clearly states they're counting the number
> of dynamic spills. That has almost nothing to do with performance.So if not the number of dynamic spills/reloads and rematerialisations.
What else can you do to measure the quality of your spilling algorithm?
Run time. We have to measure run time.
I admit that the impressive numbers in spill translate to smaller gains
in the range of 1-5% also it's hard to compare 2 different compilers.
Why not compare a single compiler on a single machine using two different
allocation algorithms?
Nonetheless we produce faster x86 code than llvm-2.3 for several spec
benchmarks (and produce way slower code for some others where I suspect
missing architecture neutral optimisations in firm).
Are there any plans to try this with LLVM? Do you have an LLVM version
of your algorithm? Of a firm version of LLVM's algorithm?
> Someone would have to reproduce their experiment to verify that
> performance indeed improves.You can easily download libfirm-1.17.0 and cparser-0.9.9 from
http://www.libfirm.org and see for yourself.
That's good! Too few research groups release their code and experiment
setup. I applaud you for doing so.
Much experience has taught me not to trust register allocation papers.
They never actually talk about performance. If I were reviewer, I
might accept a paper based on novelty of the algorithm (far too
many papers are rejected simply because they can't show a 20% speedup)
but I wouldn't give points for reducing the number of spills and
reloads. Those counts simply don't mean anything in the real world.
-Dave