[mercury-users] 234-Trees vs alternatives in the compiler

Fergus Henderson 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        |     -- leaked Microsoft memo.

More information about the users mailing list