[Bug libstdc++/18633] New: resource allocation problem with __gnu_cxx::hash_map

[Bug libstdc++/18633] New: resource allocation problem with __gnu_cxx::hash_map

[work at paul dot dubuc dot org]

The operator[] method on hash_map will unnecessarily resize the container when
used to access an existing element when the container size is at any of the
values in the __stl_prime_list table (ext/hashtable.h).  This unnecessarily
causes the container capacity to double in size and the elements to be rehashed.

There is also a more serious consequence when using operator[] access in a
multithreaded environment which I think adds further justification for the
change.  This caused some controversy on the libstdc++ which I won't repeat
here.  See the following messages (and follow-ups) for details:

http://gcc.gnu.org/ml/libstdc++/2004-11/msg00132.html
http://gcc.gnu.org/ml/libstdc++/2004-11/msg00150.html
http://gcc.gnu.org/ml/libstdc++/2004-11/msg00156.html

The problem could be fixed in ext/hashtable.h by moving the call to resize() to
be after the first return statement:

template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::find_or_insert(const value_type& __obj)
{
  resize(_M_num_elements + 1);	// <- FROM HERE


  size_type __n = _M_bkt_num(__obj);
  _Node* __first = _M_buckets[__n];


  for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
    if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
      return __cur->_M_val;
				// <-- TO HERE
  _Node* __tmp = _M_new_node(__obj);
  __tmp->_M_next = __first;
  _M_buckets[__n] = __tmp;
  ++_M_num_elements;
  return __tmp->_M_val;
}

-- 
           Summary: resource allocation problem with __gnu_cxx::hash_map
           Product: gcc
           Version: 3.4.3
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: work at paul dot dubuc dot org
                CC: gcc-bugs at gcc dot gnu dot org
  GCC host triplet: sparc-sun-solaris2.8


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18633

[Bug libstdc++/18633] resource allocation problem with __gnu_cxx::hash_map

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2004-11-23 19:49 -------
Thanks.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pcarlini at suse dot de
                   |dot org                     |
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-11-23 19:49:44
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18633

[Bug libstdc++/18633] resource allocation problem with __gnu_cxx::hash_map

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2004-11-26 10:58 -------
Actually, just moving down the resize is not ok, since __n and __first would need
to be recomputed too, with a non-trivial overhead in case of insert. Also, the
memory doubling happens only when one of the thresholds is encountered, not in
the common case. Add to this that these are basically legacy and non-portable
facilities (new ISO-mandated unordered containers will be provided soon). All
in all, better not touching find_or_insert, sorry.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |INVALID


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18633

[Bug libstdc++/18633] resource allocation problem with __gnu_cxx::hash_map

[work at paul dot dubuc dot org]

------- Additional Comments From work at paul dot dubuc dot org  2004-11-29 14:41 -------
OK.  I wondered if the change was really as easy as it looked.
Thanks for looking into this, Paolo.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18633