Re: C++ hash map container

From: Dave O'Hearn (daveoh77_at_pobox.com)
Date: 12/01/04 

Date: 30 Nov 2004 17:41:55 -0800

jcoffin@taeus.com (Jerry Coffin) wrote in message news:<b2e4b04.0411292215.48eb3354@posting.google.com>...
> Matthias Käppler <nospam@digitalraid.com> wrote in message news:<cog48r$s0m$02$1@news.t-online.com>...
>
> [ ... ]
>
> > As far as I know, std::map does not hash its entries (I guess it takes
> > O(nlogn) time to find an entry).
>
> No -- it's O(log N). Given that containers are (intended to be)
> contained entirely in addressable memory, the difference between
> logarithmic and constant time is small enough that in real life the
> difference will depend on the details of the implementation as much as
> the computational complexity.
>
> Just for example, if we assume a million items in the collection, a
> map should require roughly 20 operations for a search. A million items
> suggests about four characters to distinguish between items, so we'll
> average comparing 2 bytes for most of those comparisons, meaning we
> look at about 38 bytes plus the length of the key being searched for.

What about page faults? A tree can cause a page fault on every one of
those 20 operations. Most likely, the first couple will be cached, but
once you get down several levels in the tree, you will start getting
page faults.

There are special tree implementations that reduce page faults, by
making B-Trees where each node has many children, like hundreds of
children, instead of just a 'left' and a 'right'. It's very unlikely
that std::set is going to use that optimization, as it only makes
sense on large data sets.

I would take advantage of generic programming, and implement the
application first using std::set, and then with whichever hash_set
extension you like, and profiling which actually behaves better in
practice. With generic code and a few typedefs, possibly only one line
of code will have to be changed to try out another container type. 

-- 
Dave O'Hearn

Relevant Pages