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

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

[Michael Veksler]

Hello,

In previous discussions on rounding of double on x86 I wanted
to find an example that points to the absurdity of current
gcc behavior.
At last I found such an example:

---- t.cpp start ---
#include <tr1/unordered_set>
#include <iostream>

double x=3.0;

int main()
{
   std::tr1::unordered_set<double> myset;
   myset.insert(2/x);
   myset.insert(2/x);
   std::cout << myset.size() << " elements\n";
   if (myset.size() > 1)
      std::cout << "Are last and first equal?  "
                << std::boolalpha
                << ( *myset.begin() == *++myset.begin())
                << "\n";
   return 0;
}
--- t.cpp  end ---

Here is what I get (Pentium 4):

--- trace begin ---
test$ /opt/gcc-4.0-20050602/bin/g++ t.cpp
test$ ./a.out
1 elements
test$ /opt/gcc-4.0-20050602/bin/g++ -O3 -finline-limit=1000000 t.cpp
test$ ./a.out
2 elements
Are last and first equal?  true
--- trace end ---

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.


Using error bands will work fine for unordered_set<doble> insertion.
It may lead to the "loss" of close entries, but in case of double it sounds
reasonable.


P.S.
   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 ?).

  Michael

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

[Paolo Carlini]

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.
    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.

Paolo.

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

[Michael Veksler]

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

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

[Gabriel Dos Reis]

Michael Veksler <VEKSLER@il.ibm.com> writes:

[...]

| >     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.

And it is clearly welcome!  I hope more will follow :-)

-- Gaby

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

[Paolo Carlini]

Gabriel Dos Reis wrote:

>| Sorry, I am not on the gcc team (I am working on constraint solvers rather
>| than compilers). I performed this review purely voluntarily.
>
>And it is clearly welcome!  I hope more will follow :-)
>  
>
Indeed.

However, sorry, as a matter of politeness, in my opinion expressions
like "absurdity" or "very  bad way" are much better accepted if
accompanied by corresponding constructive contributions. Or,
alternately, just avoid such extreme statements and offer analyses
preferring technical terms and citations, as you basically just did,
thanks about that.

Paolo.

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

[Michael Veksler]

Paolo Carlini <pcarlini@suse.de> wrote on 05/07/2005 19:05:40:
>
> However, sorry, as a matter of politeness, in my opinion expressions
> like "absurdity" or "very  bad way" are much better accepted if
> accompanied by corresponding constructive contributions. Or,
> alternately, just avoid such extreme statements and offer analyses
> preferring technical terms and citations, as you basically just did,
> thanks about that.

No offense meant, it's only due to cultural differences...
I'll keep in mind to avoid such words, so that nobody is offended.
Unfortunately, the text is much more dry and boring that way.

  Michael

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

[Paolo Carlini]

Michael Veksler wrote:

>Paolo Carlini <pcarlini@suse.de> wrote on 05/07/2005 19:05:40:
>  
>
>>However, sorry, as a matter of politeness, in my opinion expressions
>>like "absurdity" or "very  bad way" are much better accepted if
>>accompanied by corresponding constructive contributions. Or,
>>alternately, just avoid such extreme statements and offer analyses
>>preferring technical terms and citations, as you basically just did,
>>thanks about that.
>>    
>>
>No offense meant, it's only due to cultural differences...
>I'll keep in mind to avoid such words, so that nobody is offended.
>  
>
No problem ;)

>Unfortunately, the text is much more dry and boring that way.
>  
>
Not necessarily: there are many different ways to deal with that
"serious" ;) problem: for instance you can make a funny link to a movie,
music you like, no? ;)

Paolo.

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

[Michael Veksler]

There is one more thing to consider: the ABI.
By changing the code in the header file will break the ABI
of tr1::unordered_set. Code compiled with older gcc and
newer and fixed-gcc will not interoperate.

I don't see an easy path to avoid ABI breakage this time,
however how about preparing for future breakage when
std::tr1::hash<T> changes again?
Maybe move all the specialized hash<T> code from
tr/functional into libstdc++.so? Maybe move specialized
hashtable<double>, unordered_XXX<float> and friends into
libstdc++.so? This way, when hash<T> and
std::equal_to<double> change again, the ABI will be not
as affected.


  Michael.

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

[Paolo Carlini]

Michael Veksler wrote:

>There is one more thing to consider: the ABI.
>By changing the code in the header file will break the ABI
>of tr1::unordered_set. Code compiled with older gcc and
>newer and fixed-gcc will not interoperate.
>  
>
No, no, there are no problems. First, I don't see how changing the
internals of a function like an hashing function would change the Binary
Interface. Second, in general, we make no guarantees as far as the tr1
bits are concerned, this is also *explicitely* stated in the release
notes. Really, please reconsider the issue, there are no problems.

Paolo.

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

[Paolo Carlini]

Paolo Carlini wrote:

>Michael Veksler wrote:
>
>>There is one more thing to consider: the ABI.
>>By changing the code in the header file will break the ABI
>>of tr1::unordered_set. Code compiled with older gcc and
>>newer and fixed-gcc will not interoperate.
>>
It occurs to me that by "ABI" you mean interoperability between
different object modules, what I call sometimes "ABI" in the wide sense.
Something much more difficult to obtain, which is not related to the
linked *.so. Anyway, we don't guarantee anything for tr1, as per the
release notes.

Paolo.

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

[Michael Veksler]

Paolo Carlini <pcarlini@suse.de> wrote on 05/07/2005 23:48:03:
> Paolo Carlini wrote:
>
> >Michael Veksler wrote:
> >
> >>There is one more thing to consider: the ABI.
> >>By changing the code in the header file will break the ABI
> >>of tr1::unordered_set. Code compiled with older gcc and
> >>newer and fixed-gcc will not interoperate.
> >>
> It occurs to me that by "ABI" you mean interoperability between
> different object modules, what I call sometimes "ABI" in the wide sense.

Exactly, yes this is what I meant.

> Something much more difficult to obtain, which is not related to the
> linked *.so. Anyway, we don't guarantee anything for tr1, as per the
> release notes.

You are right. Too bad, but very much understandable for a TR.
I hope that it will be stabilized in time for c++-0x.

  Michael

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

[Gabriel Dos Reis]

Michael Veksler <VEKSLER@il.ibm.com> writes:

| There is one more thing to consider: the ABI.
| By changing the code in the header file will break the ABI
| of tr1::unordered_set. Code compiled with older gcc and
| newer and fixed-gcc will not interoperate.

tr1 is very experimental and we don't guarantee anything.

-- Gaby

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

[Gabriel Dos Reis]

Michael Veksler <VEKSLER@il.ibm.com> writes:

| Hello,
| 
| In previous discussions on rounding of double on x86 I wanted
| to find an example that points to the absurdity of current
| gcc behavior.
| At last I found such an example:

Thanks for investing time in this and reporting.

| ---- t.cpp start ---
| #include <tr1/unordered_set>
| #include <iostream>
| 
| double x=3.0;
| 
| int main()
| {
|    std::tr1::unordered_set<double> myset;
|    myset.insert(2/x);
|    myset.insert(2/x);
|    std::cout << myset.size() << " elements\n";
|    if (myset.size() > 1)
|       std::cout << "Are last and first equal?  "
|                 << std::boolalpha
|                 << ( *myset.begin() == *++myset.begin())
|                 << "\n";
|    return 0;
| }
| --- t.cpp  end ---
| 
| Here is what I get (Pentium 4):
| 
| --- trace begin ---
| test$ /opt/gcc-4.0-20050602/bin/g++ t.cpp
| test$ ./a.out
| 1 elements
| test$ /opt/gcc-4.0-20050602/bin/g++ -O3 -finline-limit=1000000 t.cpp
| test$ ./a.out
| 2 elements
| Are last and first equal?  true
| --- trace end ---
| 
| 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.

The different behaviour do not look right to me, no matter how IBM
is committed to GCC :-)  

At the very least, there is a problem with GCC -- please, in case anybody
feels the need to read the standard to me; pause a minute :-)

I don't believe it is OK to have repetition in an unordered set.
However, there seems to be a need to clarifications.  In particular,
how an implementation is supposed to behave if it supported NaNs and
other curiosity.  I'll forward this to the LWG.

| 
| 
| Using error bands will work fine for unordered_set<doble> insertion.
| It may lead to the "loss" of close entries, but in case of double it sounds
| reasonable.
| 
| 
| P.S.
|    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 ?).
| 
|   Michael

-- 
                                                       Gabriel Dos Reis 
                                           gdr@integrable-solutions.net

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

[Paolo Carlini]

Michael Veksler wrote:

>   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 ?).
>  
>
A possible solution would be using frexp & co to extract the mantissa
and then work on it, one way or the other. You can find it proposed
around. Then, often the exponent is simply discarded.

What do you think?

In case, please add your comments to the audit trail of 21193. I mean to
work pretty soon on improving those hash functions.

Paolo.

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

[Gabriel Dos Reis]

Paolo Carlini <pcarlini@suse.de> writes:

| Michael Veksler wrote:
| 
| >   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 ?).
| >  
| >
| A possible solution would be using frexp & co to extract the mantissa
| and then work on it, one way or the other. You can find it proposed
| around. Then, often the exponent is simply discarded.
| 
| What do you think?

It is definitely a good thing to use the full bits of value
representation if we ever want to make all "interesting" bits part of
the hash value.  For reasonable or sane representations it suffices to
get your hand on the object representation, e.g.:

   const int objsize = sizeof (double);
   typedef unsigned char objrep_t[objsize];
   double x = ....;
   objrep_t& p = reintepret_cast<objrep_t&>(x);
   // ...

and let frexp and friends only for less obvious value representation.

-- Gaby

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

[Joe Buck]

On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote:
> It is definitely a good thing to use the full bits of value
> representation if we ever want to make all "interesting" bits part of
> the hash value.  For reasonable or sane representations it suffices to
> get your hand on the object representation, e.g.:
> 
>    const int objsize = sizeof (double);
>    typedef unsigned char objrep_t[objsize];
>    double x = ....;
>    objrep_t& p = reintepret_cast<objrep_t&>(x);
>    // ...
> 
> and let frexp and friends only for less obvious value representation.

I disagree; on an ILP32 machine, we pull out only 32 bits for the hash
value, and if you aren't careful, your approach will wind up using the
least significant bits of the mantissa.  This will cause all values that
are exactly representable as floats to collide.

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

[Gabriel Dos Reis]

Joe Buck <Joe.Buck@synopsys.COM> writes:

| On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote:
| > It is definitely a good thing to use the full bits of value
| > representation if we ever want to make all "interesting" bits part of
| > the hash value.  For reasonable or sane representations it suffices to
| > get your hand on the object representation, e.g.:
| > 
| >    const int objsize = sizeof (double);
| >    typedef unsigned char objrep_t[objsize];
| >    double x = ....;
| >    objrep_t& p = reintepret_cast<objrep_t&>(x);
| >    // ...
| > 
| > and let frexp and friends only for less obvious value representation.
| 
| I disagree; on an ILP32 machine, we pull out only 32 bits for the hash
| value, and if you aren't careful, your approach will wind up using the
| least significant bits of the mantissa.  This will cause all values that
| are exactly representable as floats to collide.

I'm not sure we're talking about the same thing.  With the
representations I'm talking about, value repsentation == object representation.

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

[Paolo Carlini]

Gabriel Dos Reis wrote:

>Joe Buck <Joe.Buck@synopsys.COM> writes:
>
>| On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote:
>| > It is definitely a good thing to use the full bits of value
>| > representation if we ever want to make all "interesting" bits part of
>| > the hash value.  For reasonable or sane representations it suffices to
>| > get your hand on the object representation, e.g.:
>| > 
>| >    const int objsize = sizeof (double);
>| >    typedef unsigned char objrep_t[objsize];
>| >    double x = ....;
>| >    objrep_t& p = reintepret_cast<objrep_t&>(x);
>| >    // ...
>| > 
>| > and let frexp and friends only for less obvious value representation.
>| 
>| I disagree; on an ILP32 machine, we pull out only 32 bits for the hash
>| value, and if you aren't careful, your approach will wind up using the
>| least significant bits of the mantissa.  This will cause all values that
>| are exactly representable as floats to collide.
>
>I'm not sure we're talking about the same thing.  With the
>representations I'm talking about, value repsentation == object representation.
>
... still, the hash functions for float, double and long double that we
need for TR1 must return a size_t (6.3.3). How do you get a size_t from
an objrep_t? (fulfilling the various requirements briefly reminded by
Joe in his first message)

Paolo.

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

[Gabriel Dos Reis]

Paolo Carlini <pcarlini@suse.de> writes:

| Gabriel Dos Reis wrote:
| 
| >Joe Buck <Joe.Buck@synopsys.COM> writes:
| >
| >| On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote:
| >| > It is definitely a good thing to use the full bits of value
| >| > representation if we ever want to make all "interesting" bits part of
| >| > the hash value.  For reasonable or sane representations it suffices to
| >| > get your hand on the object representation, e.g.:
| >| > 
| >| >    const int objsize = sizeof (double);
| >| >    typedef unsigned char objrep_t[objsize];
| >| >    double x = ....;
| >| >    objrep_t& p = reintepret_cast<objrep_t&>(x);
| >| >    // ...
| >| > 
| >| > and let frexp and friends only for less obvious value representation.
| >| 
| >| I disagree; on an ILP32 machine, we pull out only 32 bits for the hash
| >| value, and if you aren't careful, your approach will wind up using the
| >| least significant bits of the mantissa.  This will cause all values that
| >| are exactly representable as floats to collide.
| >
| >I'm not sure we're talking about the same thing.  With the
| >representations I'm talking about, value repsentation == object representation.
| >
| ... still, the hash functions for float, double and long double that we
| need for TR1 must return a size_t (6.3.3). How do you get a size_t from
| an objrep_t?

The same way you would get a hash value out of

  unsigned char [N * sizeof(size_t)]

?

| (fulfilling the various requirements briefly reminded by
| Joe in his first message)

I don't think Joe understood I was talking about hashing the value
representation of the floating point object.

If you regard the object representation as an array of bytes, does it
take long realize it is not much different from hashing a character
string? 

-- Gaby

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

[Paolo Carlini]

Gabriel Dos Reis wrote:

>If you regard the object representation as an array of bytes, does it
>take long realize it is not much different from hashing a character
>string?
>
It takes less if your proposal comes together with a specific one for
character string hashing: not, trivially, because in this way the
problem would be solved completely ;) but because, given the plethora of
different ways you can hash character strings, I'm not sure one
considered "good" for real text would be also good for
strings-from-floats, there are *lots* of subtle statistical issues
involved. For example, I'm not at all sure that the hash function
suggested by submitter of 21193 would also work statistically well for
floats (note that most of the real world succesful applications
mentioned in the linked web page are about *real* text). I don't think
laws like the famous ETAOINSHRDLU distribution of the english letters
apply also to the bytes of floats, do you? ;)

That said, I agree that reusing what we are going to have for strings
also for floats is in any case better than the present placeholder, at
the time certainly not considered by Matt the final production solution.

Paolo.

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

[Gabriel Dos Reis]

Paolo Carlini <pcarlini@suse.de> writes:

| Gabriel Dos Reis wrote:
| 
| >If you regard the object representation as an array of bytes, does it
| >take long realize it is not much different from hashing a character
| >string?
| >
| It takes less if your proposal comes together with a specific one for
| character string hashing:

You do have one already.  Start from there.  Measure, then we can
argue later.  Now that you realize it is same issue, we've made
significant progress. 

[...]

| involved. For example, I'm not at all sure that the hash function
| suggested by submitter of 21193 would also work statistically well for
| floats (note that most of the real world succesful applications
| mentioned in the linked web page are about *real* text). I don't think

Yes, but note also that those depend on some assumptions about
the distribution of some words.  Not every specific context would
equally benefit from that.  The point being that once you
have reduced the problem to one previously known solved problem,
it is only a matter of arguing about little details.  I think
that is far better than current situation.

-- Gaby

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

[Michael Veksler]

Joe Buck <Joe.Buck@synopsys.COM> wrote on 05/07/2005 21:10:25:

> On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote:
> > It is definitely a good thing to use the full bits of value
> > representation if we ever want to make all "interesting" bits part of
> > the hash value.  For reasonable or sane representations it suffices to
> > get your hand on the object representation, e.g.:
> >
> >    const int objsize = sizeof (double);
> >    typedef unsigned char objrep_t[objsize];
> >    double x = ....;
> >    objrep_t& p = reintepret_cast<objrep_t&>(x);
> >    // ...
> >
> > and let frexp and friends only for less obvious value representation.
>
> I disagree; on an ILP32 machine, we pull out only 32 bits for the hash
> value, and if you aren't careful, your approach will wind up using the
> least significant bits of the mantissa.  This will cause all values that
> are exactly representable as floats to collide.

For that you can do something like (or templated equivalent):
namespace Impl
{
 template <class T>
 size_t floating_point_hash(T in)
 {
   if (sizeof(in) <= sizeof(size_t))
    Use Gaby's solution, with zero padding;
   else
    frexp and friends using Joe Buck's ideas;
  }
}

Gaby's solution should be done with care - to avoid any
aliasing issues (never go directly from double& to size_t&).

Both Gaby's and Joe Buck's solutions do not take
the strangeness of IEEE (NNN?) into account.
As I remember it (I don't have the reference at home),
IEEE FP has many bit-representations for NaN, each
containing some bit-encoding of errors.
It has been years since I last saw the standard of IEEE FP,
so I may give wrong details, but the main idea should be
correct.

"There *should* be a specialization for equal_to<double> that
provides a strict weak ordering for NaNs as well as other
values." [quoted forwarded mail from P.J. Plauger]
Doing bit-wise conversions will not address this requirement.

  Michael

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

[Gabriel Dos Reis]

Michael Veksler <VEKSLER@il.ibm.com> writes:

| Joe Buck <Joe.Buck@synopsys.COM> wrote on 05/07/2005 21:10:25:
| 
| > On Tue, Jul 05, 2005 at 08:05:39PM +0200, Gabriel Dos Reis wrote:
| > > It is definitely a good thing to use the full bits of value
| > > representation if we ever want to make all "interesting" bits part of
| > > the hash value.  For reasonable or sane representations it suffices to
| > > get your hand on the object representation, e.g.:
| > >
| > >    const int objsize = sizeof (double);
| > >    typedef unsigned char objrep_t[objsize];
| > >    double x = ....;
| > >    objrep_t& p = reintepret_cast<objrep_t&>(x);
| > >    // ...
| > >
| > > and let frexp and friends only for less obvious value representation.
| >
| > I disagree; on an ILP32 machine, we pull out only 32 bits for the hash
| > value, and if you aren't careful, your approach will wind up using the
| > least significant bits of the mantissa.  This will cause all values that
| > are exactly representable as floats to collide.
| 
| For that you can do something like (or templated equivalent):
| namespace Impl
| {
|  template <class T>
|  size_t floating_point_hash(T in)
|  {
|    if (sizeof(in) <= sizeof(size_t))
|     Use Gaby's solution, with zero padding;
|    else
|     frexp and friends using Joe Buck's ideas;
|   }
| }
| 
| Gaby's solution should be done with care - to avoid any
| aliasing issues (never go directly from double& to size_t&).

The standard explicilty permit that you can regard any object as an
array of unsigned char.  Given that, and given no padding bits
(e.g. the "sane" representation assumption), hashing any object larger
than a size_t is no different from hashing a character string.

Now, the question is how to make sure we do not have padding bits.  For
most targets, that assumption is OK; only the one subject of this
discussion seems to pose problems ;-) 

| Both Gaby's and Joe Buck's solutions do not take
| the strangeness of IEEE (NNN?) into account.
| As I remember it (I don't have the reference at home),
| IEEE FP has many bit-representations for NaN, each
| containing some bit-encoding of errors.

My proposal explicilty takes that into account in the sense that it
looks at all bits of the value representation, therefore the encoding
bits of the NaNs too.


| "There *should* be a specialization for equal_to<double> that
| provides a strict weak ordering for NaNs as well as other
| values." [quoted forwarded mail from P.J. Plauger]
| Doing bit-wise conversions will not address this requirement.

I do not understand what you mean by that.

-- Gaby

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

[Avi Kivity]

On Tue, 2005-07-05 at 20:05 +0200, Gabriel Dos Reis wrote:
> Paolo Carlin
> It is definitely a good thing to use the full bits of value
> representation if we ever want to make all "interesting" bits part of
> the hash value.  For reasonable or sane representations it suffices to
> get your hand on the object representation, e.g.:
> 
>    const int objsize = sizeof (double);
>    typedef unsigned char objrep_t[objsize];
>    double x = ....;
>    objrep_t& p = reintepret_cast<objrep_t&>(x);
>    // ...
> 
> and let frexp and friends only for less obvious value representation.

most architectures have different bit representations for +0.0 and -0.0,
yet the two values compare equal.

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

[Michael Veksler]

Avi Kivity wrote on 06/07/2005 15:38:38:
> On Tue, 2005-07-05 at 20:05 +0200, Gabriel Dos Reis wrote:
> > Paolo Carlin
> > It is definitely a good thing to use the full bits of value
> > representation if we ever want to make all "interesting" bits part of
> > the hash value.  For reasonable or sane representations it suffices to
> > get your hand on the object representation, e.g.:
> >
> >    const int objsize = sizeof (double);
> >    typedef unsigned char objrep_t[objsize];
> >    double x = ....;
> >    objrep_t& p = reintepret_cast<objrep_t&>(x);
> >    // ...
> >
> > and let frexp and friends only for less obvious value representation.
>
> most architectures have different bit representations for +0.0 and -0.0,
> yet the two values compare equal.
>

Yet, their sign bit is observable through   things like
  assert(a == 0.0);
  assert(b == 0.0);
  1/(1/a+ 1/b)
which would give either NaN or 0 depending on the sign
of a and b.

So do you want one or two copies in the set?

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

[Avi Kivity]

On Wed, 2005-07-06 at 15:54 +0300, Michael Veksler wrote:

> > most architectures have different bit representations for +0.0 and -0.0,
> > yet the two values compare equal.
> >
> 
> Yet, their sign bit is observable through   things like
>   assert(a == 0.0);
>   assert(b == 0.0);
>   1/(1/a+ 1/b)
> which would give either NaN or 0 depending on the sign
> of a and b.
> 
> So do you want one or two copies in the set?
> 
what matters is whether the sign bit is observable through the equality
predicate. in the case of the operator==(double, double), it is not
observable, so there should be only one copy in a set.

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

[Gabriel Dos Reis]

Avi Kivity <avi@argo.co.il> writes:

| On Wed, 2005-07-06 at 15:54 +0300, Michael Veksler wrote:
| 
| > > most architectures have different bit representations for +0.0 and -0.0,
| > > yet the two values compare equal.
| > >
| > 
| > Yet, their sign bit is observable through   things like
| >   assert(a == 0.0);
| >   assert(b == 0.0);
| >   1/(1/a+ 1/b)
| > which would give either NaN or 0 depending on the sign
| > of a and b.
| > 
| > So do you want one or two copies in the set?
| > 
| what matters is whether the sign bit is observable through the equality
| predicate. in the case of the operator==(double, double), it is not
| observable, so there should be only one copy in a set.

Yes.

That logical framework has some "problems" though.  Assume x is  NaN,
then you would end up with as many xs as you insert in the set.

-- Gaby

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

[Gabriel Dos Reis]

Avi Kivity <avi@argo.co.il> writes:

| On Tue, 2005-07-05 at 20:05 +0200, Gabriel Dos Reis wrote:
| > Paolo Carlin
| > It is definitely a good thing to use the full bits of value
| > representation if we ever want to make all "interesting" bits part of
| > the hash value.  For reasonable or sane representations it suffices to
| > get your hand on the object representation, e.g.:
| > 
| >    const int objsize = sizeof (double);
| >    typedef unsigned char objrep_t[objsize];
| >    double x = ....;
| >    objrep_t& p = reintepret_cast<objrep_t&>(x);
| >    // ...
| > 
| > and let frexp and friends only for less obvious value representation.
| 
| most architectures have different bit representations for +0.0 and -0.0,
| yet the two values compare equal.

Indeed.  Paolo, Michael and I have been discussing that offline.
the signed zero representation is not the a serious one (say compare
to having padding bits or how to handle NaNs properly) -- just
compare to 0.0 and return hash value 0 before going mocking around
with bytes.

-- Gaby

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

[Joe Buck]

On Tue, Jul 05, 2005 at 07:05:16PM +0200, Paolo Carlini wrote:
> Michael Veksler wrote:
> 
> >   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 ?).
> >  
> >
> A possible solution would be using frexp & co to extract the mantissa
> and then work on it, one way or the other. You can find it proposed
> around. Then, often the exponent is simply discarded.
> 
> What do you think?

Close, but not quite.

Hash functions are, by nature, many-to-one.  A good hash function has
few collisions for values that frequently appear; the program will preform
very poorly if many inputs hash to the same value.  The existing function
will make all values over max(size_t) collide (assuming the cast clips).
Using only the mantissa is better, but if doubles are used to
represent fixed-point, then common values like 0.25, 0.5, 1, 2, 4 might
all be in the hash table, and they will collide.

You could do frexp, scale the mantissa to form an integer (e.g. multiply
by a large integer), then add it (modulo 2**n) to some prime number
multiplied by the exponent.  This should give good spreading for both
large values and exactly representable values.

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

[Paolo Carlini]

Hi Joe and Gaby and thanks for your messages,

>Close, but not quite.
>
>Hash functions are, by nature, many-to-one.  A good hash function has
>few collisions for values that frequently appear; the program will preform
>very poorly if many inputs hash to the same value.  The existing function
>will make all values over max(size_t) collide (assuming the cast clips).
>Using only the mantissa is better, but if doubles are used to
>represent fixed-point, then common values like 0.25, 0.5, 1, 2, 4 might
>all be in the hash table, and they will collide.
>
>You could do frexp, scale the mantissa to form an integer (e.g. multiply
>by a large integer), then add it (modulo 2**n) to some prime number
>multiplied by the exponent.  This should give good spreading for both
>large values and exactly representable values.
>
Indeed, I can find around also more sophisticated solutions similar to
your proposal, perhaps in the python library?!? I'm tempted to go along
this way, but Gaby's idea also seems nice, opinions about it? We have to
make a choice... or we can provide both and the user chooses... still we
have to select a default ;)

Thanks

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

[Joe Buck]

On Tue, Jul 05, 2005 at 08:13:41PM +0200, Paolo Carlini wrote:
> Hi Joe and Gaby and thanks for your messages,
> 
> >Close, but not quite.
> >
> >Hash functions are, by nature, many-to-one.  A good hash function has
> >few collisions for values that frequently appear; the program will preform
> >very poorly if many inputs hash to the same value.  The existing function
> >will make all values over max(size_t) collide (assuming the cast clips).
> >Using only the mantissa is better, but if doubles are used to
> >represent fixed-point, then common values like 0.25, 0.5, 1, 2, 4 might
> >all be in the hash table, and they will collide.
> >
> >You could do frexp, scale the mantissa to form an integer (e.g. multiply
> >by a large integer), then add it (modulo 2**n) to some prime number
> >multiplied by the exponent.  This should give good spreading for both
> >large values and exactly representable values.
> >
> Indeed, I can find around also more sophisticated solutions similar to
> your proposal, perhaps in the python library?!? I'm tempted to go along
> this way, but Gaby's idea also seems nice, opinions about it? We have to
> make a choice... or we can provide both and the user chooses... still we
> have to select a default ;)

If I were you I'd be tempted to crib from Python.  Because of the
centrality of good hashing for Python performance, I'm sure that they've
done a good job.

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

[Paolo Carlini]

Joe Buck wrote:

>If I were you I'd be tempted to crib from Python.  Because of the
>centrality of good hashing for Python performance, I'm sure that they've
>done a good job.
>
I agree Joe, probably that's a good empirically tested solution.

Paolo.