debug mode performance patch

[François Dumont]

Ok I will integrate a test showing the deadlock issue with current patch 
based on your code and then will fix the patch.

Thanks for the code !

On 11/10/2010 11:02 PM, Jonathan Wakely wrote:
> On 10 November 2010 21:55, François Dumont wrote:
>    
>> Well, this is not something my change introduce. For the moment the debug
>> mode is using a single mutex for all synchronizations. To keep binary
>> compatibility I haven't been able to add a mutex instance to the safe
>> sequence so I introduce a small mutex pool to limit contention.
>>      
> Sorry if my review sounded negative, I think the general idea is very
> good.  But with a single mutex there is no chance for deadlock, it
> just means only one swap can take place at a time.
>
> By introducing multiple mutexes without some checking you make it easy
> to deadlock.  Slow and correct is better than fast and deadlock  ;-)
>
>    
>>> There are two problems with _M_swap in your patch:
>>>
>>> 1) if two objects are swapped whih share the same mutex then it will
>>> try to lock the same mutex twice.  You should be able to reproduce
>>> this like so (untested):
>>>
>>> __gnu_debug::vector<int>    v[17];
>>> swap(v[0], v[16]);
>>>
>>> If I'm not mistaken, v[0] and v[16] should get the same mutex from
>>> get_mutex and so should lock it twice. That's bad, even in a
>>> single-threaded program.
>>>
>>>        
>> Yes, this is why I asked if mutex are guarantied to be reentrant even if I
>> agree that even if it is so it is still bad practice.
>>      
> When your mail arrived I had just finished some examples to
> demonstrate the problems, maybe these should go in the testsuite.
>
> This deadlocks for me:
>
> #include<mutex>
> #include<iostream>
>
> std::mutex&  get_mutex(void* p)
> {
>    const uintptr_t mask = 0xf;
>    static std::mutex mutexes[ mask + 1 ];
>    uintptr_t index = (reinterpret_cast<uintptr_t>(p) / sizeof(void*))&  mask;
>    std::cerr<<  index<<  std::endl;
>    return mutexes[ index ];
> }
>
> struct A { void* p; };
>
> void swap(A&  a, A&  b)
> {
>    std::lock_guard<std::mutex>  l1(get_mutex(&a));
>    std::lock_guard<std::mutex>  l2(get_mutex(&b));
> }
>
> int main()
> {
>    A a[17];
>    swap(a[0], a[16]);  // distinct objects, but "share" a mutex
> }
>
>    
>>> 2) consider four sequences, A, B, C and D. They happen to have
>>> addresses such that:
>>>
>>> &A.get_mutex() ==&C.get_mutex()
>>> and
>>> &B.get_mutex() ==&D.get_mutex()
>>>
>>> now, in my multithreaded program I do this concurrently:
>>> swap(A, B);   swap(D, C);
>>> I'm not accessing any single object in more than one thread, but it
>>> will deadlock.
>>>
>>>        
>> Indeed
>>      
> e.g this deadlocks for me:
>
> // same definition of A, get_mutex and swap:
> #include<thread>
>
> A a[32];
>
> void f(int i, int j) { for (int k=0; k<10; ++k) swap(a[i], a[j]); }
>
> int main()
> {
>    // swap distinct objects in two threads
>    std::thread t1(f, 0, 1);
>    std::thread t2(f, 17, 16);
>    t1.join();
>    t2.join();
> }
>
>
>    
>>> The solution is to ensure that you don't lock the same mutex twice and
>>> you always lock in a consistent order
>>>
>>>        
> e.g. this fixes both deadlocks
>
> void swap(A&  a, A&  b)
> {
>    std::mutex&  m1 = get_mutex(&a);
>    std::mutex&  m2 = get_mutex(&b);
>    if (&m1<  &m2)
>      std::lock_guard<std::mutex>  l(m1);
>    else
>    {
>      std::lock_guard<std::mutex>  l1(&m1<  &m2 ? m1 : m2);
>      std::lock_guard<std::mutex>  l2(&m1<  &m2 ? m2 : m1);
>    }
> }
>
>    
>> Ok, so except fixing this lock issue you seem to agree on the modified debug
>> mode lock model, great. I will fix this issue and submit a new proposition.
>>      
> Great - thanks for working on this!
>
> Jonathan
>