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
>> > modulus of the hash by the number of buckets, locking the bucket
>> > 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
>> values have equal probability? What happens if a real item does end
>> 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 .
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.
(Sent from my portable computation engine)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk