Subtle MT problem with __gnu_cxx::hash_map

[Paul Dubuc]

Jonathan Wakely wrote:
> On Mon, Nov 22, 2004 at 05:43:03PM -0500, Paul Dubuc wrote:
>>>>If one can be sure that the elements that are accessed using 
>>>>operator[] do
>>>>exist, I would also tend to assume it should behave like a read only 
>>>>access.
>>>
>>>But it isn't.  Read-only accesses are things you can perform on a const
>>>object.
>>
>>Not ONLY on a const object.  You can also perform them on non-const 
>>objects. Isn't any access that doesn't actually do a write a read-only 
>>access?
> 
> 
> Would you say ::write(STDOUT_FILENO,"",0) was a read-only file operation ?

No, but operator[] always does a read, whether it inserts or not. So this is not 
a relevant comparison.  Can't you see the ambiguity here?  There is no analogy 
to operator[] because it is a find() which will insert and return an empty 
element is one is not already there.

>>>You can't use operator[] on a const hash_map.  (Or on a const
>>>map, for that matter.
>>
>>True, but at least the compiler catches it when you do.  operator[] can't 
>>be a const method because it MAY do an insert.  That's playing it safe 
>>where the interface is concerned.  So?
> 
> 
> There's no "playing it safe" - operator[] is not a const operation,
> therefore is not a read-only operation, therefore requires explicit
> locking. Even if the library was changed as you suggest, other standard
> library implementations may not be, so you would be relying on
> non-portable, unsafe assumptions.
> 
> 
>>>You'll be unhappy if you try to think of 
>>>operator[] on maps as a read-only operation in a multithreaded 
>>>environment.)
>>
>>I'll agree with you here.  You're right.  I guess this is an unfortunate 
>>consequence of operator[] being BOTH a find() and an insert().  It's easy 
> 
> 
> No, it's an insert, which might not actually insert anything.

Think about why insert() doesn't work this way.  operator[] is not just an 
insert().  It's more accurate to say that it's a find() which always returns 
something because it's allowed to insert an element if it doesn't find one with 
the index used.

> 
> 
>>to see the insert() as a convenient side-effect that you can avoid if you 
>>know what you're doing.  (Especially since it bears so much resemblance in 
>>its use to array subscripting in C which doesn't have this side-effect).  
>>After all, the programmer KNOWS he's not doing an insert in this case.  And 
> 
> 
> Then he should use find().

Which piece of code is easier to read:

	z = map1[x].map2[y]->q;

or
	(rewrite this using find() and you'll get the idea.  Remember the programmer 
knows that all elements in each map do exist.  He's designed it that way.  He 
knows that an insert should never be necessary.  If it is it's a bug in his 
design and he deserves what he gets.)

> 
> 
>>it's true that NOTHING was actually inserted.  It's just that the hash_map 
>>implementation decided to reallocate anyway, unnecessarily, based on an 
>>arbitrary container size.
>>
>>What is wrong with removing the unnecessary and wasteful reallocation and 
>>taking the view that, if the programmer knows what he's (not) doing, let 
>>him (not) do it without some arbitrary penalty?  Can you think of any a 
>>good reason why a container should reallocate itself (or change itself in 
>>anyway) if it's not going to insert a new element?  Wouldn't we normally 
>>call that a bug?
> 
> 
> You've called a mutating member function, so the container is allowed to
> modify it's state. If you don't want that, use find().

It's a mutating function only in the "legal" sense.  Practically it's a 
combination of a non-mutating operation and a mutating one (as a side-effect for 
convenience).  So the interface makes in a non-const operation.  That's fine. 
But any container that changes itself when an operation that its ACTUALLY 
non-mutating is performed on it is of a poor design.  Wouldn't you agree?

> As an aside, am I right in thinking that the call to resize() that is
> under discussion might change the ordering of elements in the container?
> c.f. http://www.sgi.com/tech/stl/HashedAssociativeContainer.html#3
> 
> That would seem to be another argument against using operator[] when you
> want a read-only find operation.

The call to resize() actually doubles the capacity of the container.  If it's 
not going to do in insert, this is a tremendous waste of memory and overhead. 
Especially with a hash_map since all existing elements have to be rehashed.  On 
these grounds alone, it's worth making the simple one line change I originally 
proposed.  The resize() shouldn't be done until the container has done the 
find() and finds nothing.  Then it should be done before the insert.

-- 
Paul M. Dubuc