Re: [boost] Container suggestions (was: Re: BOOST_NO_HASH)

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.