[mercury-users] 234-Trees vs alternatives in the compiler
fjh at cs.mu.OZ.AU
Wed Dec 16 00:06:50 AEDT 1998
On 15-Dec-1998, Ralph Becket <rwab1 at cam.sri.com> wrote:
> Reading through Simon Taylor's dissertation "Optimization of Mercury
> Programs" it seems that many of the optimisations performed by the
> compiler have little benefit when applied to the compiler itself due
> to the nature of 234-trees and their pervasive use in the compiler
> code (via the map ADT I presume).
> While 234-trees have great properties in the limit, I reckon they
> introduce quite a large constant factor. Has anybody tried
> benchmarking the compiler changing the map ADT to use binary trees or
> even plain lists?
Actually the very first implementation of `map' used association lists,
and the second one used binary trees. The changes from association
lists to binary trees and then to 234-trees were done to improve
performance. We did some measurements at the time; I don't
recall the figures off-hand, but the changes did indeed succeed
in improving performance.
On the other hand, the `set' data type still uses lists rather than trees,
because lists performed better for that case.
[If you're interested, the measurement results may be documented
somewhere in the cvs log messages
(<ftp://turiel.cs.mu.oz.au/pub/mercury/cvs-logs/>) or on the Mercury
developers mailing list archives.]
I think red-black trees might be better than 234-trees,
if only the compiler would do a better job of optimizing
rbtree__search -- currently it's not smart enough to combine
the code for the "red" case with the (identical) code for
the "black" case.
Fergus Henderson <fjh at cs.mu.oz.au> | "Binaries may die
WWW: <http://www.cs.mu.oz.au/~fjh> | but source code lives forever"
PGP: finger fjh at 126.96.36.199 | -- leaked Microsoft memo.
More information about the users