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

[Andrew Bromage]

G'day all.

Fergus Henderson wrote:

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

The 234-tree implementation has changed somewhat since these experiments
were run.  There have been some performance hits (due to a bug being found)
and some performance improvements (partly due to the compiler being
profiled on the library).

It would be interesting to try the experiments again with one or two
more exotic data structures.

Cheers,
Andrew Bromage