Re: std::map per-node overhead (Was: [boost] Re: shared_ptr doubts)

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2005-02-15 16:08:04

On Feb 15, 2005, at 2:41 PM, Peter Dimov wrote:

> You could have pretended that you had in mind an implementation where 
> pointers are always even and one of the least-significant bits is used 
> as a color bit. ;-)

Actually the Metrowerks implementation does this, although it turns 
that optimization off if:

1.  The client requests it.
2.  Alignment is 1.

I just had a hard time dealing with all of those bits wasted. :-)

> Are there std::maps that store a next and previous pointer to optimize 
> traversal at the expense of per-node overhead?

I haven't heard of one.  Along those lines I did do an analysis of the 
cost of traversal though.  If you have a perfectly balanced tree of 2^N 
- 1 elements (a full, balanced tree), and if you iterate from begin() 
to end(), then the number of pointer links you chase is 
2*distance(begin(),end()).  I.e. for my money your speed gain would be 
no greater than a factor of two, and due to the fact that your nodes 
are now up to 50% bigger, you could well realize a slow down just from 
the extra level-2 cache flush.  But I haven't actually coded it up and 
performance tested it.

If optimized iteration is really what you need, std::map probably isn't 
the container you want.  A sorted vector, deque or list (or cdeque or 
slist) may be a better fit.  map is good for the requirements of a 
strictly bounded log(N) lookup and insert/erase, plus 
iterator/reference stability.  Iteration and per-element overhead are 
secondary concerns and therefore sacrificed.

-Howard