Re: [boost] [review] Review of Unordered library begins today December 7

From: Daniel James (daniel_james_at_[hidden])
Date: 2007-12-08 05:11:40

Ion Gaztañaga wrote:
> Thorsten Ottosen wrote:
>   
>> I vote to accept this library. The documentation is very nice.
>>     
>
> Thanks for the vote.
>   

Thank you from me as well.

>> One thing puzzled me though:
>> (see http://igaztanaga.drivehq.com/unordered/unordered/comparison.html)
>>
>> "The containers hash or predicate function can throw exceptions from erase"
>>
>> Under what cicumstances can/should/would I construct a ahsh or predicate 
>> that throws? I mean, the hash computes an integer, and comparisons reads 
>> data to determine its answer.
>>
>> This migth be what the standard requires, but it certainly seems 
>> non-intuitive. Why not just require that neither hash nor predicates can 
>> throw?
>>     
>
> The same could be said about Predicate for ordered containers like 
> std::set/map. I haven't seen a practical case where the comparison could 
> throw. But standard library experts should answer this better than me.
>   

One example where they could throw is if the hash function used a 
numeric type which throws an exception when it overflows (which does 
suggest a buggy hash function but there you go). Another is that the 
data required to evaluate the hash function or check for equality is 
expensive and is lazily evaluated. For example, if you had a class which 
represents file, and based your equality test on calculating the SHA-1 
signature then you might only calculate it when required - which could 
be a call to the hash or equality function.

> Certainly, Daniel has tried to achieve strong exception guarantees and 
> the implementation becomes quite complicated if comparison/hash throws. 
> Double buffering and other tricks are needed. I think this is a very 
> good question both for boosters and people from the LWG.
>   

Dealing with a call to comparison and hash isn't that bad - the 
implementation of the insert functions is a little intricate because of 
the exception requirements. The main problem is if the copy constructor, 
assignment or swap calls. (Ion knows all of this, it's for the benefit 
of everyone else).

If either objects throw an exception while swapping or assigning a 
container it could leave the hash and comparison in an unknown state 
which would make the object invalid. To avoid this I store two of each, 
and a pointer to the current functions. And manipulation is done on the 
ones that aren't in use and when finished the pointer is switched to the 
new functions, making the operation atomic.

The main cost is the memory use of the main container object. Instead of 
containing 2 small objects, it contains 4 small objects and a pointer - 
on 32-bit x86 this typically means an extra 6 bytes, although if the 
hash or equality object has members it can be more. I don't see this as 
a significant problem because the memory required for the container's 
buckets and nodes is typically much larger.

Without doing something like this, I don't think the container could use 
a boost::function for its hash or comparison object and meet the current 
standard's requirements. The requirements could be weakened to say that 
after such an exception the only thing you could with the container is 
destruct it, but that would be inconsistent with the rest of the 
standard library.

Daniel