Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #4956

Re: g++ unordered_multimap buggy?

Followups directed to: comp.lang.c++

Show all headers | View raw

Ralf Goertz wrote:

> Kai-Uwe Bux wrote:
> 
>> Ralf Goertz wrote:
>> 
>>> Hi,
>>> 
>>> I have now spent a day to track down a segmentation fault in a program
>>> of mine that used to work. This time it crashed always exactly at the
>>> same place (I was running it with new data). The program uses
>>> unordered_multimap<string, SomeClass> and I repeatedly call a subroutine
>>> with two const SomeClass & elements obtained from iterators of that map.
>>> gdb told me that the segfault occured at the line where I called the
>>> subroutine.
>> 
>> Hm, that sounds like you could be invalidating the references somewhere
>> between obtaining them and passing them to the subroutine. But without
>> seeing the code, we are limited to guesswork.
>> 
>> 
>>> Only after switching off optimization (which in this case is
>>> very expensive because the map contains millions of elements and
>>> execution time increased from 20 minutes to over an hour) I got a
>>> different source line where the error occured:
>>> 
>>> Program terminated with signal 11, Segmentation fault.
>>> #0  0x000000000041f642 in std::_Rb_tree<std::string, std::string,
>>> #std::_Identity<std::string>, std::less<std::string>,
>>> std::allocator<std::string> >::_M_insert_unique (
>>>     this=0x7fff600cf070, linknodes=...) at
>>>     /usr/include/c++/4.5/bits/stl_tree.h:1181
>>> 
>>> In that file we have
>>> 
>>> 1171   template<typename _Key, typename _Val, typename _KeyOfValue,
>>> 1172            typename _Compare, typename _Alloc>
>>> 1173     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
>>> 1174                _Compare, _Alloc>::iterator, bool>
>>> 1175     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
>>> 1176     _M_insert_unique(const _Val& __v)
>>> 1177     {
>>> 1178       _Link_type __x = _M_begin();
>>> 1179       _Link_type __y = _M_end();
>>> 1180       bool __comp = true;
>>> 1181       while (__x != 0)
>>> 1182     {
>>> 1183       __y = __x;
>>> 1184       __comp = _M_impl._M_key_compare(_KeyOfValue()(__v),
>>> _S_key(__x));
>>> 1185       __x = __comp ? _S_left(__x) : _S_right(__x);
>>> 1186     }
>>> 1187       iterator __j = iterator(__y);
>>> 1188       if (__comp)
>>> 1189     {
>>> 1190       if (__j == begin())
>>> 1191         return pair<iterator, bool>(_M_insert_(__x, __y, __v),
>>> true);
>>> 1192       else
>>> 1193         --__j;
>>> 1194     }
>>> 1195       if (_M_impl._M_key_compare(_S_key(__j._M_node),
>>> _KeyOfValue()(__v)))
>>> 1196     return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
>>> 1197       return pair<iterator, bool>(__j, false);
>>> 1198     }
>>> 
>>> 
>>> I still don't see where there should be a problem but after switching to
>>> boost::unordered_multimap every thing works fine again.
>>> 
>>> I don't want to exclude the possibility that my program is buggy but
>>> given that
>>> 
>>> * it had worked previously,
>>> * works fine with boost,
>>> * crashes only with specific input after many executions of that line
>>> * doesn't use any pointers at all
>>>
>>> what are the odds that the g++ implementation is the culprit?
>> 
>> Close to 0 :-)
>> 
> 
> :(
>  
> Thanks for taking a look.
> 
>>> Maybe there is something wrong with the hashing?
>> 
>> I would rather suspect that your code has undefined behavior:
>> 
>> a) it crashes
>> b) randomly
>> c) and at different places depending on the optimization level
> 
> No that is not true. It crashes at the same point regardless of
> optimization. The reason I see a different sourceline is ? I suppose ?
> that some calls are optimized away.
> 
>> d) swapping the implementation of unordered_multimap changes the behavior
>> 
>> and, as mentioned above, invalidation of references seems a probable
>> cause of undefined behavior; in particular as your program does not use
>> pointers.
> 
> How can that be? This is the relevant part of the code
>  
>  for (;ii!=itp.first;){
>      AIterator a1=nodes.getIterator(ii->second,0);
>      AIterator a2=nodes.getIterator(ii->second,1);
>      AIterator const &ai1(ii->second < itp.first->second ? a2 : a1),
>                           &ai2(ii->second > itp.first->second ? a2 : a1);
>      if(isEqual(ai1->second, ai2->second) && merge(ai2,ai1)) {
>      }
> 
> So I declare AIterators a1 and a2 (getIterator returns a valid
> iterator!=end()) and then I declare ai1 and ai2 to be const references
> to a1 and a2 repectively depending on some sort criterion. The program
> crashes at isEqual (when compiled with -O3) but in the stl-header
> without optimization. But in both cases it is the same run in the loop.

Hm, indeed: there is nothing invalidating references that jumps right at me. 
Here are some suggestions / observations:

a) If the AIterator objects are small, it probably does not pay off to use 
AIterator const references. So, I would try:

  AIterator ai1 = ii->second < itp.first->second ? a2 : a1;
  AIterator ai2 = ii->second > itp.first->second ? a2 : a1;

and see if that changes anything.

b) Also: the cases

  ii->second < itp.first->second

and

  ii->second > itp.first->second

have the common false ii->second == itp.first->second. I cannot see whether 
that is intentional, but it sure would be a _rare_ condition, and I would 
check whether the spurious crashed might be related to that case.

c) A remark on style: Is the short circuit evaluation

      if(isEqual(ai1->second, ai2->second) && merge(ai2,ai1)) {
      }

just a result of trimming down the example? I would condent that

      if( isEqual(ai1->second, ai2->second) ) {
         merge(ai2,ai1);
      }

expresses more clearly what happens.


Best,

Kai-Uwe Bux

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

g++ unordered_multimap buggy? Ralf Goertz <r_goertz@usenet.arcornews.de> - 2011-05-13 16:40 +0200
  Re: g++ unordered_multimap buggy? Leigh Johnston <leigh@i42.co.uk> - 2011-05-13 16:14 +0100
    Re: g++ unordered_multimap buggy? Ralf Goertz <r_goertz@usenet.arcornews.de> - 2011-05-13 17:35 +0200
  Re: g++ unordered_multimap buggy? Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-05-13 18:21 +0200
    Re: g++ unordered_multimap buggy? Ralf Goertz <r_goertz@usenet.arcornews.de> - 2011-05-14 16:07 +0200
      Re: g++ unordered_multimap buggy? Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-05-14 16:32 +0200
        Re: g++ unordered_multimap buggy? Ralf Goertz <r_goertz@usenet.arcornews.de> - 2011-05-15 10:29 +0200
          Re: g++ unordered_multimap buggy? "Balog Pal" <pasa@lib.hu> - 2011-05-15 11:11 +0200
      Re: g++ unordered_multimap buggy? Ralf Goertz <r_goertz@usenet.arcornews.de> - 2011-05-17 09:17 +0200
      Re: g++ unordered_multimap buggy? Ruben Safir <mrbrklyn@panix.com> - 2011-06-09 18:26 +0000

csiph-web