234-Trees vs alternatives in the compiler

[Ralph Becket]

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?  I'd be interested to see what the difference was.
I suspect that there might be a speed increase since (i) the code for
these structures can be easier to optimise (this was the impression I
got from Simon's dissertation) and (ii) there will be a smaller
constant factor in front of the big O's, even though lots of log(n)'s
will become n's, and (iii) many of the files comprising the compiler
and library are relatively small and hence using 234-trees may be
overkill.

I'm interested in this because a friend in the know informs me that
Alta Vista *isn't* based around clever trie type structures at all,
but rather plain old lists and arrays!

Ralph

-- 
Ralph Becket  |  rwab1 at cam.sri.com  |  http://www.cam.sri.com/people/becket.html