Re: [boost] GSOC 2015 : Project on Concurrent Hash Tables

Subject: Re: [boost] GSOC 2015 : Project on Concurrent Hash Tables
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2015-02-15 11:05:12

On 15 Feb 2015 at 19:24, Amarnath V A wrote:

> 1. I could not make out the use of _oldbuckets in the code. What purpose
> does it serve?

Implementing a thread safe rehash of a concurrent unordered map is 
tricky without losing a lot of performance. The assumption is that 
rehashing is infrequent, so to rehash we mark all old buckets as 
being "dead and please go reload the bucket list" and push the old, 
now emptied bucket list into a FIFO queue such that it hangs around 
for a while to make sure all threads currently using it get a chance 
to spot that it is now dead, and to reload the bucket list.

Purists wil remark this isn't 100% thread safe if you rehash 
frequently enough. Correct, but it's good for 1000 rehashs per second 
for a 24 hour soak test on ARMv7 and Intel. The unit testing tests 
100 rehashs per second for a period as a quick smoke test.

In real world code, as rehashing is manual, simply don't rehash more 
than once a second. This is mentioned in bold font in the class 
documentation.

> 2. I see a swap() function which is not used anywhere in the codebase. Is
> it dead code?

Consider it untested inspirational code which may or may not be 
correct.

> 3. And I have a generic question regarding std::atomic. I was trying to
> code the move constructor and finally ended up failing miserably to move
> the reference of _bucket. I could not figure out how to do it. Could you
> point me to some documentation which would help me to achieve the same.

You might have a hint now above about what to do with old buckets.

> To give a fair idea about my last question, let me elaborate what I was
> trying to do. I have got the reference of _buckets and have assigned it to
> new variable using store and load methods of atomic. But, I am not
> confident if that is the right way to go about. And secondly, I see that I
> am not able to reset the reference of original.

For thread safety to be present, you can never relocate a bucket in 
memory after its construction, otherwise threads using it would see 
memory vanish out from underneath them during use. That is what 
oldbuckets is for.

Niall

-- 
ned Productions Limited Consulting
http://www.nedproductions.biz/ 
http://ie.linkedin.com/in/nialldouglas/