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

From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2007-12-10 21:26:59

Daniel:  First, thanks for your reply.  And sorry if I came across as  
overly critical.  I think your library is excellent.  The point of  
the review process is to try to make it even better :)  In fact, if  
we could make the C++ standard better in the process, I'd be delighted.

As I've said in my review, but to be clear I'll say once again, none  
of these items under discussion below are contingent to my  
(enthusiastic) vote in favor of your library.  They are merely for  
your consideration.

On Dec 10, 2007, at 3:54 PM, Daniel James wrote:
>> I find it unfortunate that it's not defined in the standard.  Howard
>> gives the same implementation I would have given, which works in O(N)
>> time.
>
> And only works for unordered_set. How would you define equality for
> unordered_multimap? Do you compare the mapped values, does the order
> of the values matter? If it doesn't then the comparison becomes more
> expensive, if it does then it's a bit odd for an 'unordered' container
> (although this implementation does preserve insertion order, if it
> didn't then things would be worse). Is it okay to define equality in
> terms of the equality predicate for keys, but operator== for values?

It works equally well with a little tweak if you require equality of  
count(key) for the multiset.  I didn't think about map/multimap,  
thanks for pointing this out.  But Daniel, what exactly does  
operator== for std::multimap do???  In fact, because insertion in  
std::multimap inserts at the end of the range, the value of  
std::multimap depends on the insertion order.  You wouldn't be doing  
anything different with unordered_multimap.  And as you mention, your  
implementation does already preserve insertion order, so you wouldn't  
have any problem to supply these extensions, and they'd be well- 
defined.   Isn't it better if you can provide stronger guarantees  
than the current draft standard, just as you already do for exceptions?

Now the standard should really define what happens when inserting  
equivalent keys in unordered_multimap, just as it does for multimap,  
but we're not fixing the standard.  I'll raise that point on another  
mailing list if I get around it.  As I understand, it depends on  
whether you use singly- or doubly-linked lists for chaining, and I  
buy your argument as to why use doubly-linked lists for multiset.  I  
think you made good points there.

As for the equality comparison vs predicate, the same again is true  
for operator== for the standard associative containers, defined as  
a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()   
[sic] (no, *I* didn't forget the final paren, it's not on page 671  
either).  Nowhere in that makes use of the "equivalence" implied by  
operator<, which is used for uniqueness in set/map and equivalence in  
multiset/multimap.  So by defining equality in terms of the equality  
predicate for keys in order to check for the uniqueness property, but  
operator== for both keys and values in the implementation of  
operator== for unordered_map/multimap, you wouldn't exactly break new  
ground.

Or am I missing some subtle implications or other clause in the  
standard?

>>  I found also the following bogus note in the Working Draft:
>>
>>> 10 Unordered associative containers are not required to support the
>>> expressions a == b or a != b. [ Note: This is because the container
>>> requirements define operator equality in terms of equality of
>>> ranges. Since the elements of an unordered associative container
>>> appear in an arbitrary order, range equality is not a useful
>>> operation. — end note]
>>>
>
> That's not bogus at all. An equality operator for unordered containers
> would have completely different semantics to all other containers
> (especially when using custom comparisons, comparing associative
> containers can have surprising results).

Why not? As I argue above, the same is already true of the ordered  
associative containers.  I don't think you'd be providing anything  
more surprising than already present in the standard.

As for surprising semantics, a set and multiset have well-defined  
notions of value (in a mathematical sense), i.e., a subset from a  
ground set of key, which is exactly what operator== compares.  For  
map and multimap, the value is a function from a ground set of keys  
to a value for map, sequence of values for multimap (sequence means  
that order matters).  The operational definition in terms of range is  
simply an algorithm for comparing those values.  Exactly the same is  
true for the values of unordered containers;  operator== as Howard  
and I've defined them precisely perform this comparison of value.  I  
find nothing surprising in that.  The fact that operator== is defined  
in terms of ranges for sequences and ordered associative containers,  
and is defined/implemented differently for unordered containers, is  
not surprising, it's necessary.  Again, I believe the standard could  
be improved on this, and wouldn't your library be the natural vector  
to provide a reference implementation for a proposal to define  
operator== for unordered containers?

> "Right now, I'm trying to limit myself to obvious design decisions for
> extensions so I don't really want to go into this area.

Fair enough.  You gave good points.  I hope my counter-arguments are  
equally relevant, but you're of course free to not implement them.   
Still, as boost explores possibilities for later standardization, it  
could be hoped that you would provide an implementation that provides  
prior art for future discussion in the committee.  Whether you or  
someone else (perhaps me, I really would like to) would make the  
proposal, is for the future.

Still, I think there's only one sensible definition for  
unordered_set, and unordered_multiset, and the multiset version isn't  
trivial either.  Would be nice if at least those werre in the  
library, perhaps with a named function instead of an operator.  Would  
it be a problem if you at least provided those?

>> The prime number list is too short, it roughly doubles every time.
>> On the other hand, I understand that it wouldn't do that have a
>> *much* larger list, as this static array is included in every
>> translation unit.

> I think it can actually cause an ODR violation so I probably should
> change that anyway. David Abrahams recently posted a way to avoid this
> by including the value in a template, so I'll try that.

In theory, yes.  In practice, linkers don't really enforce it, I  
hear.  Having it as a template doesn't solve the basic problem, which  
is the replication of identical data in many translation units.  In  
fact, it might exacerbate it by having the same table defined  
multiple times in the same translation unit!   Where I work, we're  
trying to curb executable sizes (which can be enormous, like you  
wouldn't believe).  This is precisely what would get a frown at the  
code review.

> How much of a difference would it make? The memory requirements for
> the array of buckets is typically smaller than the memory required for
> the nodes (unless you have a small number of nodes or increase the
> maximum load factor). T

You're correct, unless people like to have very large maps of small  
types (unordered_map<int, some_type*> with 10M elements) where it  
starts to really matter.  On the other end, it also matters if a user  
has lots of small maps.  I think it can really be a problem, in fact  
I have been in that situation myself (having to fix the prime number  
table of our implementation of hash table, by request of one user  
with performance-critical needs).  So here I actually speak from  
practical experience.

I believe the best thing, is to move the table to the .cpp, but I  
also I totally understanding the appeal of header-only libraries.   
Would you consider a configuration flag, whereby unless explicitly  
defined, your table is in the header, but for a user which controls  
its own site installation, a table can be generated into a .cpp and  
compiled into a library to be linked into programs using  
Boost.Unordered?  I actually did write such a piece of code, it isn't  
hard, and you can specify the step (30% or 100%) and the range of the  
desired table. If you include this code into the example section and  
make the flag public, your users can choose what they prefer based on  
their requirements.

Then again, if they're that sophisticated, maybe they can do it  
themselves.

>> Re: swap:  I really think you should be following the committee's
>> current advice (I'm looking at the code of hash_table_impl.hpp, lines
>> 1194 -- 1219), sooner rather than later.  But my opinion is biased.
>
> Why is your opinion biased?

My boss is John Lakos, and my colleague Pablo Halpern.  They both  
have strong opinions on allocators and value-semantic types.  In  
fact, they're arguing exactly about these issues with the committee  
(N2436, N2387, N1850 ).  I've been converted myself :)

> That works both ways, as the committee could change its mind. Since we
> don't have concepts, following their current decision means slow
> swaps. Which isn't that bad since it's only for the rare occasions
> when the allocators aren't equal. I haven't got a strong preference
> here either, but this was discussed before and the general consensus
> seemed to be for what I've done.

What I hear from Pablo and John is that they're getting good support  
around their proposal (ok, they're biased too :)...  Maybe you're  
right to wait and see what the committee will do.  Hopefully, won't  
take long as C++0x is around the horizon and there'll be two meetings  
in Jan. and June.  Somehow, I didn't think that Pablo's proposal  
(N2436) required concepts, but required traits instead.  But I'm not  
intimately familiar.
--
Hervé Brönnimann
hervebronnimann_at_[hidden]