Re: [boost] Request for feedback on design of concurrent_unordered_map, plus notes on use of memory transactions

Subject: Re: [boost] Request for feedback on design of concurrent_unordered_map, plus notes on use of memory transactions
From: Rob Stewart (robertstewart_at_[hidden])
Date: 2014-07-28 07:21:09

On July 28, 2014 6:08:26 AM EDT, Niall Douglas <s_sourceforge_at_[hidden]> wrote:
>On 28 Jul 2014 at 13:26, Gavin Lambert wrote:
>
>> On 28/07/2014 03:20, Niall Douglas wrote:
>
>> > * To insert or find an item involves determining the bucket from
>the
>> > modulus of the hash by the number of buckets, locking the bucket
>and
>> > scanning the linear list for an empty item or the right item as
>> > appropriate. We know empty items from a magic hash value which is
>> > defined to some magic constant (advice on the best magic hash value
>> > least likely to turn up from std::hash is welcome).
>> 
>> Isn't it by definition (admittedly reality is less ideal) that all
>hash 
>> values have equal probability?  What happens if a real item does end
>up 
>> with the magic "empty" hash value?  I think it'd be safer to have a 
>> separate flag for this case.
>
>Firstly, if the magic hash value ever turns up during insert the 
>program aborts :) It should, hopefully, be exceedingly rare on 64 bit 
>to the point that we don't care [1].

I'd be hard pressed to trust a library that aborts if the possible, but exceedingly rare occurs.

>Secondly, a separate flag costs another 8 bytes, and it ruins the 
>cache line symmetry for AFIO where items size out to 32 bytes which 
>is a lovely multiple.

A separate flag only costs one bit. You might yet be able to rethink your current data structure to free one.

The worst case, add I see it, is that you simply increment (or decrement) a computed hash value should the magic value ever arise. That is, you increase the odds of a collision so that no value ever uses the magic value.

___
Rob

(Sent from my portable computation engine)