* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
@ 2005-04-24 16:58 ` TazForEver at dlfp dot org
2005-04-26 8:45 ` pcarlini at suse dot de
` (15 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: TazForEver at dlfp dot org @ 2005-04-24 16:58 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
2005-04-24 16:58 ` [Bug libstdc++/21193] " TazForEver at dlfp dot org
@ 2005-04-26 8:45 ` pcarlini at suse dot de
2005-04-26 9:36 ` TazForEver at dlfp dot org
` (14 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pcarlini at suse dot de @ 2005-04-26 8:45 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
2005-04-24 16:58 ` [Bug libstdc++/21193] " TazForEver at dlfp dot org
2005-04-26 8:45 ` pcarlini at suse dot de
@ 2005-04-26 9:36 ` TazForEver at dlfp dot org
2005-04-26 9:50 ` pcarlini at suse dot de
` (13 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: TazForEver at dlfp dot org @ 2005-04-26 9:36 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (2 preceding siblings ...)
2005-04-26 9:36 ` TazForEver at dlfp dot org
@ 2005-04-26 9:50 ` pcarlini at suse dot de
2005-04-26 10:22 ` TazForEver at dlfp dot org
` (12 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pcarlini at suse dot de @ 2005-04-26 9:50 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (3 preceding siblings ...)
2005-04-26 9:50 ` pcarlini at suse dot de
@ 2005-04-26 10:22 ` TazForEver at dlfp dot org
2005-04-26 10:44 ` pcarlini at suse dot de
` (11 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: TazForEver at dlfp dot org @ 2005-04-26 10:22 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (4 preceding siblings ...)
2005-04-26 10:22 ` TazForEver at dlfp dot org
@ 2005-04-26 10:44 ` pcarlini at suse dot de
2005-04-26 10:46 ` pcarlini at suse dot de
` (10 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pcarlini at suse dot de @ 2005-04-26 10:44 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (5 preceding siblings ...)
2005-04-26 10:44 ` pcarlini at suse dot de
@ 2005-04-26 10:46 ` pcarlini at suse dot de
2005-04-26 14:38 ` schlie at comcast dot net
` (9 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pcarlini at suse dot de @ 2005-04-26 10:46 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (6 preceding siblings ...)
2005-04-26 10:46 ` pcarlini at suse dot de
@ 2005-04-26 14:38 ` schlie at comcast dot net
2005-04-26 14:52 ` pcarlini at suse dot de
` (8 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: schlie at comcast dot net @ 2005-04-26 14:38 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (7 preceding siblings ...)
2005-04-26 14:38 ` schlie at comcast dot net
@ 2005-04-26 14:52 ` pcarlini at suse dot de
2005-04-28 12:12 ` pcarlini at suse dot de
` (7 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pcarlini at suse dot de @ 2005-04-26 14:52 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (8 preceding siblings ...)
2005-04-26 14:52 ` pcarlini at suse dot de
@ 2005-04-28 12:12 ` pcarlini at suse dot de
2005-04-28 15:09 ` pcarlini at suse dot de
` (6 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pcarlini at suse dot de @ 2005-04-28 12:12 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (9 preceding siblings ...)
2005-04-28 12:12 ` pcarlini at suse dot de
@ 2005-04-28 15:09 ` pcarlini at suse dot de
2005-07-05 16:30 ` pcarlini at suse dot de
` (5 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pcarlini at suse dot de @ 2005-04-28 15:09 UTC (permalink / raw)
To: gcc-bugs
--
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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (10 preceding siblings ...)
2005-04-28 15:09 ` pcarlini at suse dot de
@ 2005-07-05 16:30 ` pcarlini at suse dot de
2005-07-06 7:42 ` tneumann at pi3 dot informatik dot uni-mannheim dot de
` (4 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pcarlini at suse dot de @ 2005-07-05 16:30 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (11 preceding siblings ...)
2005-07-05 16:30 ` pcarlini at suse dot de
@ 2005-07-06 7:42 ` tneumann at pi3 dot informatik dot uni-mannheim dot de
2005-07-13 10:51 ` cvs-commit at gcc dot gnu dot org
` (3 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: tneumann at pi3 dot informatik dot uni-mannheim dot de @ 2005-07-06 7:42 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (12 preceding siblings ...)
2005-07-06 7:42 ` tneumann at pi3 dot informatik dot uni-mannheim dot de
@ 2005-07-13 10:51 ` cvs-commit at gcc dot gnu dot org
2005-07-15 0:07 ` cvs-commit at gcc dot gnu dot org
` (2 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: cvs-commit at gcc dot gnu dot org @ 2005-07-13 10:51 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (13 preceding siblings ...)
2005-07-13 10:51 ` cvs-commit at gcc dot gnu dot org
@ 2005-07-15 0:07 ` cvs-commit at gcc dot gnu dot org
2005-07-15 9:38 ` cvs-commit at gcc dot gnu dot org
2005-07-15 9:40 ` pcarlini at suse dot de
16 siblings, 0 replies; 18+ messages in thread
From: cvs-commit at gcc dot gnu dot org @ 2005-07-15 0:07 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (14 preceding siblings ...)
2005-07-15 0:07 ` cvs-commit at gcc dot gnu dot org
@ 2005-07-15 9:38 ` cvs-commit at gcc dot gnu dot org
2005-07-15 9:40 ` pcarlini at suse dot de
16 siblings, 0 replies; 18+ messages in thread
From: cvs-commit at gcc dot gnu dot org @ 2005-07-15 9:38 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug libstdc++/21193] provide better std::tr1::hash for std::string and std::wstring
2005-04-24 16:57 [Bug libstdc++/21193] New: provide better std::tr1::hash for std::string and std::wstring TazForEver at dlfp dot org
` (15 preceding siblings ...)
2005-07-15 9:38 ` cvs-commit at gcc dot gnu dot org
@ 2005-07-15 9:40 ` pcarlini at suse dot de
16 siblings, 0 replies; 18+ messages in thread
From: pcarlini at suse dot de @ 2005-07-15 9:40 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread