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

[Fergus Henderson]

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).

Yes.

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