Re: tr1::unordered_set<double> bizarre rounding behavior (x86)

[Michael Veksler <VEKSLER at il dot ibm dot com>]

Paolo Carlini <pcarlini@suse.de> wrote on 05/07/2005 16:33:12:
> Michael Veksler wrote:
>
> >The behavior of the second run does not look right. What does it mean?
> >1. Is it forbidden by tr1 to define unordered_set<double> ?
> >2. Is it a bug in the tr1 document (which should have forbidden this).
> >3. Is it OK to have repetitions in unordered_set?
> >4. Is it a bug in gcc, for handling double the way it does?
> >5. Is it a bug in the implementation of tr1 in libstdc++ ?
> >    Maybe handling of double should move to a different
> >    translation unit, to avoid aggressive inlining. Or maybe
> >    there should be a specialization for equal_to<double>,
> >    where error bands will be used.
> >
> >
> I can see two possibilites here. Either:
>     1. You know the answer. Then you should probably discuss it,
> preferably comparing gcc to other compilers and mentioning specific
> sections of the Standard, TR1, LIA*, and so on.

The only tr1 compilers I have access only to are xlC7 and gcc-4.0.
Unfortunately, xlC7 works on PPC an architecture for which gcc's double
should work just fine (as expected, always insert one element).

As for TR1, 6.3.4.3 describes unordered_set and gives no restriction
on type, and says "... container that supports unique keys...". Obviously,
gcc-4.0 does not meet this criteria.

Looking at 6.3.3, you can see the description of class template hash:
"This class template is only required to be instantiable for integer types
(3.9.1), floating point types (3.9.1.), ......"
This indicates that unordered_set<double> should work fine, and contain
no duplicates.

Looking at 6.3.1 "Unordered associative container requirements" does
not give any indication for illegality of unordered_set<double>. Yet,
there is some text that makes it problematic for double.

"Each unordered associative container is parameterized by Key, ....,
 and on a binary predicate Pred that induces an equivalence relation on
values of type Key".
"Two values k1 and k2 of type Key are considered equal if the container's
equality function object returns true when passed those values.
If k1 and k2 are equal, the hash function shall return the same value for
both."

Please note that it requires an "equivalence relation". It is impossible
with
gcc on x86, with or without error bounds to meet this criterion for double.
Also, the requirement to return the same hash value for k1 and k2
(if Pred()(k1,k2)), is very problematic due to the way gcc handles double.

Nothing in TR1 seems to indicate that unordered_XXX<double> is
undefined or otherwise to be avoided.

>     2. You don't know the answer. In that case you are supposed to file
> a PR and trust bug-masters and maintainers about the issue.
>
> >   std::tr1::hash<dobule> is implemented in a very bad way.
> >   it casts double to size_t, which of course does a very poor job on
big
> >   values (is the result of 1.0e100 cast to size_t defined ?).
> >
> >
> Thanks. Patches welcome, as usual: contributions are certainly
> encouraged, especially so from IBM - I would say - generally committed
> to the project in a constructive, high quality, and friendly way.

Sorry, I am not on the gcc team (I am working on constraint solvers rather
than compilers). I performed this review purely voluntarily. Besides, I
don't
have clearance to contribute GPL code (too much paperwork).

  Michael