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

Subject: Re: [boost] GSOC 2015 : Project on Concurrent Hash Tables
From: Amarnath V A (me_at_[hidden])
Date: 2015-03-06 23:36:28

On Fri, Mar 6, 2015 at 7:00 PM, Niall Douglas <s_sourceforge_at_[hidden]> wrote:
>
> Move construction of the map != move construction of the buckets.
>

Okay. I am trying to achieve move construction in the same spirit. And
I am piggybacking on Niall's implementation of _rehash().

      concurrent_unordered_map(concurrent_unordered_map &&old_map)
BOOST_NOEXCEPT :
          _hasher(std::move(old_map._hasher)),
          _key_equal(std::move(old_map._key_equal)),
          _allocator(std::move(old_map._allocator)),
          _max_load_factor(std::move(old_map._max_load_factor)),
          _min_bucket_capacity(std::move(old_map._min_bucket_capacity))
      {
        typedef decltype(_rehash_lock) rehash_lock_t;
        lock_guard<rehash_lock_t> guard(old_map._rehash_lock,
adopt_lock_t());
        buckets_type
&old_buckets=*(old_map._buckets.load(memory_order_consume));
        size_t n = old_buckets.size();
        if(n)
        {
          // Lock all existing buckets
          for(auto &b : old_buckets)
            b.lock.lock();
        }

        buckets_type *tempbuckets=new buckets_type(13);
        auto untempbuckets=undoer([&tempbuckets]{ delete tempbuckets; });

        buckets_type *buckets=new buckets_type(n);

        // Swap old buckets with new buckets
        tempbuckets=old_map._buckets.exchange(tempbuckets,
memory_order_acq_rel);
        // Tell all threads using old buckets to start reloading the bucket list
        for(auto &b : *tempbuckets)
          b.lock.store(2);

        // Simply move the old buckets into new buckets as-is
        for(auto obit=tempbuckets->begin(), bit=buckets->begin();
obit!=tempbuckets->end(); ++obit, ++bit)
        {
          auto &ob=*obit;
          auto &b=*bit;
          if(ob.count.load(memory_order_relaxed))
          {
            b.items=std::move(ob.items);
            b.count.store(ob.count.load(memory_order_consume),
memory_order_release);
            ob.count.store(0, memory_order_release);
          }
        }

Is this the right direction?

>
> Old buckets go into a fixed size ring buffer, and get deleted
> eventually.
>

I couldn't really figure out where the ring buffer is which you are
mentioning here. What am I missing?

And another question, when I use the above implementation of move
constructor and later call empty() on the newly created object, I land
in a segfault. I see that the empy() checks on if the lock state is 2
and continues to check the next bucket. But, I think here I have all
buckets set to lock state 2. Why did the swap I performed with the
tempbuckets and oldmap._buckets not help me? Any pointers will be
really helpful.

Thanks,
Amarnath