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-03-10 10:58:58

On 10 Mar 2015 at 18:43, Amarnath V A wrote:

> But I have peculiar issue. When I run basic unit test for the copy
> constructor, it fails saying it encountered a SIGABRT to memory
> corruption. The unit test is pretty basic and is as follows:

I think you may still be trying to copy and paste parts of the 
existing implementation into something which works rather than 
creating your own implementation based on a sufficient understanding 
of how the algorithm works.

This last skill - self confidence in C++ - is probably the biggest 
thing we try to instill in GSoC students during a summer. It is 
exactly why I chose this test, indeed I got into a little hot water 
six months ago on this list by explicitly not finishing 
concurrent_unordered_map precisely because I thought this test so 
worthwhile for a student.

Here's what I would suggest: get a whiteboard or equivalent and try 
drawing out the sequence of an insert operation on the left and an 
extract operation on the right. If you move the left up and down 
relative to the right, you can see how the concurrency can create 
problems if the sequence is not exactly in the right order.

>From there, try to write out what a whole container copy operation 
must do, again with an insert and extract operation on the other side 
and you moving it up and down to see concurrency problems. It will 
yield several design choices: Should the copy be a snapshot i.e. no 
concurrency at all? Should the copy allow concurrency with rehashing?

Regarding the move constructor, I am surprised you haven't noticed it 
can be written in two lines yet. It wouldn't be particularly 
efficient, but then I didn't ask for the most efficient solution - I 
asked for a solution which works and is correct. This programming 
competency test is actually much smaller than it looks as soon as you 
mentally grok it, and remember that correctness is far more important 
than efficiency.

BTW you might want to pull updates from the Boost.Spinlock git repo. 
I tried to get the thread sanitiser to not crash out during the unit 
testing over the weekend by trying to workaround a false positive it 
finds in _rehash() which is currently suppressed. The suppression 
means the sanitiser uses a lot of RAM, and it dies. Unfortunately I 
failed to achieve a workaround, but maybe the commented out printf's 
might be a hint to you as to how to go about debugging your 
implementation.

> BOOST_AUTO_TEST_CASE(works/concurrent_unordered_map/copyconstructor/basic,
> "Tests that concurrent_unordered_map works as expected")
> {
>   printf("\n=== concurrent_unordered_map basic copy constructor ===\n");
>   boost::spinlock::concurrent_unordered_map<int, int> map1;
>   map1.reserve(100);    // test dense map
>   BOOST_CHECK(map1.empty());
>   BOOST_CHECK(map1.size()==0);
>   for(int n=-200; n<=200; n+=2)
>   {
>     map1.emplace(n, n);
>   }
>   BOOST_CHECK(!map1.empty());
>   BOOST_CHECK(map1.size()==201);
>   printf("Load factor for map1 is %f\n", map1.load_factor());
> 
>   boost::spinlock::concurrent_unordered_map<int, int> map2(map1);
>   BOOST_CHECK(!map2.empty());
>   BOOST_CHECK(!map1.empty());
>   BOOST_CHECK(map2.size()==201);
>   BOOST_CHECK(map1.size()==201);
> 
>   printf("Load factor for map1 is %f\n", map1.load_factor());
>   printf("Load factor for map2 is %f\n", map2.load_factor());
> 
>   map1.clear();
>   map2.clear();
>   BOOST_CHECK(map1.empty());
>   BOOST_CHECK(map2.empty());
>   BOOST_CHECK(map1.size()==0);
>   BOOST_CHECK(map2.size()==0);
> }
> 
> The second last BOOST_CHECK is were I hit on this issue. And the error is
> 
> Error in `/home/amarnath/work/boost.spinlock/test/unittests_1':
> corrupted double-linked list: 0x0000000000689200 ***
> 
> But, when I remove the BOOST_CHECK and just run map1.size() and
> map2.size() calls, I have no issues.I tried to understand the problem
> but could not make out why it is failing? Any help is welcome.

Consider adding some printf()'s to your implementation and comparing 
the state they report to what you thought was going on.

Niall

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