William Lee Irwin III
Ugh, lousy cache properties... try rank-ordered B+ trees. There are probably better choices than that even. It's probably best Simon point us to references to what's actually useful here.
On Fri, Oct 08, 2004 at 03:55:05PM +0200, Ketil Malde wrote:
I'm as dumb as anybody, but it seems to me that one could read a lazy chain (list) of buffers as UArray Int Word8, and tack a list-type interface (head, tail, cons...) interface on top.
I had in mind a more general attack on things like e.g. list concatenation, reversal, indexing (!!), and so on in addition to cache locality, packing, and reducing space overhead of list linkage. As Keith Wansbrough mentioned in another post, these kinds of arrangements tend to spoil other useful properties of the more naive-looking lists. -- wli