debug mode performance patch

[François Dumont]

Hi

     Here is a new proposition with the deadlock issue fixed. I use 
auto_ptr to acquire it even if it is deprecated because unique_ptr is 
only available in gnu++0x mode and the library is not built in this 
mode, is it fine ? I also created a test to show the problem before the 
fix. In fact I even had to add a sleep between the 2 locks in debug.cc 
to reproduce the deadlock temporarily, it shows that the problem existed 
and that it has been removed now.

     Just in case you agree to apply the patch there are new files in 
it, especially the safe_sequence.tcc one. Has it to be added in some 
files ? I ask because to run tests I had to manually create a link to 
this file in x86_64-unknown-linux-gnu/libstdc++-v3/include/debug. Will 
it be generated automatically once commited ?

François

On 11/11/2010 10:06 PM, François Dumont wrote:
> 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
>

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: performance.patch
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20101116/66d5afc5/attachment.ksh>