From: Greg Colvin (greg_at_[hidden])
Date: 2001-01-08 22:21:00
> On Mon, 8 Jan 2001, Matthew Austern wrote:
> > In principle, the advantage of open addressing is that you can get
> > some space saving. I don't know if that's a big enough advantage to
> > be worth the pain.
> Agreed. IIRC, it was the basis of indexed sequential files. Not
> nice to be chasing linked lists around the diskpack. The fixed
> size table in memory could afford the search time since it was
> much less than the disk reads. Just as a b-tree is a fine external
> data structure and not much good in memory.
I think a b-tree can be an excellent in-memory structure, since
the cache-to-RAM relationship is similar to the RAM-to-disk
relationship: the speed discrepency between cache and RAM is
high, and there are advantages to reading entire cache lines.
For the same reasons, large in-memory hash tables can thrash
the cache and perform much worse that expected.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk