[Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring

[Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring

[TazForEver at dlfp dot org]

The current implementation of std::tr1::hash for std::string and std::wstring is
pretty bad. I think FNV should be used instead.

http://www.isthe.com/chongo/tech/comp/fnv/

I'm attaching a patch that may not be optimal when size_t is 64bits.

-- 
           Summary: provide better std::tr1::hash for std::string and
                    std::wstring
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P2
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: TazForEver at dlfp dot org
                CC: gcc-bugs at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[TazForEver at dlfp dot org]

------- Additional Comments From TazForEver at dlfp dot org  2005-04-24 16:58 -------
Created an attachment (id=8729)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=8729&action=view)
FNV


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-04-26 08:45 -------
Hi, and thanks for your report. Actually, as you may have noticed, we are aware
that the current function is not optimal in any sense... Now, if we want to
improve it now, maybe we should carry out a minimum of bibliographic research.
Also, maybe we should also change consistently collate<_CharT>::do_hash (in
locale_facets.tcc) which is also not perfect, but at least doesn't depend on
the size of size_t. I consider the latter a rather serious issue, given the
range of targets supported by GCC. What do you think?

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[TazForEver at dlfp dot org]

------- Additional Comments From TazForEver at dlfp dot org  2005-04-26 09:36 -------
Well, there are FNV* parameters for 32bits and 64bits size_t.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-04-26 09:49 -------
Of course there are, but wouldn't be better just using an hashing function that
does *not* depend on such constants? Is really unavoidable? If we *really* think
so, then we have also to implement the necessary bits, maybe dispatching to a
suited template via sizeof(size_t) as integer template argument.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[TazForEver at dlfp dot org]

------- Additional Comments From TazForEver at dlfp dot org  2005-04-26 10:03 -------
But collate<_CharT>::do_hash() already depends on sizeof(long)...

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-04-26 10:39 -------
... which, of course, tracks size_t, on every platform I know. Or you have a
counterexample?

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-04-26 10:44 -------
But, as I said, the issue is more general: whether we want a function that does
not depend on constants or one that does. If, after an appropriate bib search, we
agree about the latter, wouldn't be difficult to dispatch at compile time via
sizeof(size_t).

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[schlie at comcast dot net]

------- Additional Comments From schlie at comcast dot net  2005-04-26 14:38 -------
(In reply to comment #6)
>> But collate<_CharT>::do_hash() already depends on sizeof(long)..
> ... which, of course, tracks size_t, on every platform I know. Or you have a
> counterexample?

Just about any 8 or 16 bit target with a 16-bits wide address, including avr, etc.
(so in general would expect sizeof(int) ~ sizeof(size_t) to be more consistently true,
 or of course could be structured to rely on sizeof(size_t) directly.)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-04-26 14:52 -------
> Just about any 8 or 16 bit target with a 16-bits wide address, including avr,
> etc. (so in general would expect sizeof(int) ~ sizeof(size_t) to be more 
> consistently true, or of course could be structured to rely on sizeof(size_t)
> directly.)

As you imply in the last line, this is really a side-issue (in collate we have
to return a long and there is nothing wrong with probing sizeof(long)). By the
way, I would be curious to know whether the targets that you are mentioning do
actually run well libstdc++-v3 in general (often my practical point of view is
tied to that ;)

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-04-28 12:12 -------
By the way, the proposed patch does *not* implement FNV right: among other
things, replaces a bit-a-bit xor with a sum.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[pcarlini at suse dot de]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pcarlini at suse dot de
                   |dot org                     |
             Status|WAITING                     |ASSIGNED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-07-05 16:30 -------
Also investigate a better hashing of floating point values.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[tneumann at pi3 dot informatik dot uni-mannheim dot de]

------- Additional Comments From tneumann at pi3 dot informatik dot uni-mannheim dot de  2005-07-06 07:42 -------
How about using a union-cast to hash floating point numbers? Something like this

unsigned hash(double v) {
   union { double a; unsigned long long b; } tmp;
   tmp.a=v; return tmp.b^(tmp.b>>32);
}

The code is only a sketch (assumes 32bit unsigned etc.) but should produce much 
better results than the current hash function. It should also avoid the problems 
with unordered_set<double> mentioned on the mailing list.
The main disadvantage is that it forces memory access, which is somewhat slow.
Another problem is that the resulting hash value is not portable, but this is 
probably ok.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-07-13 10:47 -------
Subject: Bug 21193

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	paolo@gcc.gnu.org	2005-07-13 10:47:40

Modified files:
	libstdc++-v3   : ChangeLog 
	libstdc++-v3/include/tr1: functional 

Log message:
	2005-07-13  Paolo Carlini  <pcarlini@suse.de>
	
	PR libstdc++/21193 (string & wstring)
	* include/tr1/functional (hash<string>, hash<wstring>):
	Reimplement using the FNV hash.
	
	* include/tr1/functional: Trivial formatting fixes.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/ChangeLog.diff?cvsroot=gcc&r1=1.3057&r2=1.3058
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/include/tr1/functional.diff?cvsroot=gcc&r1=1.11&r2=1.12



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-07-15 00:05 -------
Subject: Bug 21193

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	paolo@gcc.gnu.org	2005-07-15 00:05:45

Modified files:
	libstdc++-v3   : ChangeLog 
	libstdc++-v3/include/tr1: functional 

Log message:
	2005-07-14  Paolo Carlini  <pcarlini@suse.de>
	
	PR libstdc++/21193 (float, double, long double)
	* include/tr1/functional (hash<float>, hash<double>):
	Reimplement exploiting the Fnv_hash<>::hash helper.
	(hash<long double>): Reimplement using frexp (in this
	case, due to random padding bits, the former approach
	is not generally viable).

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/ChangeLog.diff?cvsroot=gcc&r1=1.3058&r2=1.3059
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/include/tr1/functional.diff?cvsroot=gcc&r1=1.12&r2=1.13



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-07-15 09:37 -------
Subject: Bug 21193

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-4_0-branch
Changes by:	paolo@gcc.gnu.org	2005-07-15 09:36:52

Modified files:
	libstdc++-v3   : ChangeLog 
	libstdc++-v3/include/tr1: functional 

Log message:
	2005-07-15  Paolo Carlini  <pcarlini@suse.de>
	
	PR libstdc++/21193 (float, double, long double)
	* include/tr1/functional (hash<float>, hash<double>):
	Reimplement exploiting the Fnv_hash<>::hash helper.
	(hash<long double>): Reimplement using frexp (in this
	case, due to random padding bits, the former approach
	is not generally viable).
	
	2005-07-15  Paolo Carlini  <pcarlini@suse.de>
	
	PR libstdc++/21193 (string & wstring)
	* include/tr1/functional (hash<string>, hash<wstring>):
	Reimplement using the FNV hash.
	
	* include/tr1/functional: Trivial formatting fixes.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.2917.2.66&r2=1.2917.2.67
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/include/tr1/functional.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.7.2.4&r2=1.7.2.5



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193

[Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-07-15 09:38 -------
Fixed for 4.0.2.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.0.2


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21193