[Bug libstdc++/41622] New: [c++0x] std::hash<std::string>::operator() copies its argument

[Bug libstdc++/41622] New: [c++0x] std::hash<std::string>::operator() copies its argument

[jbytheway at gmail dot com]

The following program:

====
#include <string>
#include <unordered_set>

int main()
{
  std::unordered_set<std::string> set;
  std::string key("foo");

  for (int i=0; i<1000; ++i) {
    set.count(key);
  }
  return 0;
}
====

(if compiled without optimizations) makes 1000 calls to the std::string copy
constructor (according to profiling by valgrind --tool=callgrind).  This is
because the std::hash<std::string>::operator() takes its argument by value
rather than by const reference (see tr1_impl/functional_hash.h lines 164--166).

This slowed one of my programs by about 10-20%, the faster time being achieved
by using boost::hash<std::string> instead of std::hash<std::string>.  The boost
implementation takes its argument by const reference (See
http://gitorious.org/boost/svn/blobs/750d0927ebb5adc7f4150c854305e5e28924d747/boost/functional/hash/hash.hpp
lines 351--369 and line 389).  I believe libstdc++ should follow this lead on
performance grounds.  String keys for unordered associative containers are a
very common use case, and it seems silly not to make them as fast as possible.

Looking at a draft standard (N2914, [unord.hash]) it does seem to suggest that
std::hash<T>::operator() must take its argument by value, but my standard-fu is
insufficient to be sure if it's really insisting.

As evidence that the change is OK:

- boost::hash claims in its documentation
(http://www.boost.org/doc/libs/1_40_0/doc/html/hash.html) to be compliant with
TR1, linking to N1836, in which [tr.unord.hash] has essentially the same
content as the draft standard.  I would expect Boost to get this right,
therefore I conclude that it is acceptable to use a const reference argument.

- If you were specializing std::hash for a movable-but-not-copyable type, then
it would be impossible to take the argument by value.  The standard certainly
seems to imply that Key types need not be copyable.

- The only obvious constraint on user-supplied hash functions is "A hash
function is a function object that takes a single argument of type Key and
returns a value of type std::size_t." ([unord.req], p4); it doesn't insist on
taking the argument by value.


-- 
           Summary: [c++0x] std::hash<std::string>::operator() copies its
                    argument
           Product: gcc
           Version: 4.4.1
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: jbytheway at gmail dot com
 GCC build triplet: x86_64-pc-linux-gnu
  GCC host triplet: x86_64-pc-linux-gnu
GCC target triplet: x86_64-pc-linux-gnu


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

[Bug libstdc++/41622] [c++0x] std::hash<std::string>::operator() copies its argument

[jbytheway at gmail dot com]

------- Comment #1 from jbytheway at gmail dot com  2009-10-07 15:45 -------
Created an attachment (id=18741)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18741&action=view)
Patch providing proof-of-concept implementation

I attach a patch implementing this change on svn HEAD.  It doesn't break any
tests here, but I am fairly sure I've done the wrong thing to the linker script
(gnu.ver); I don't really understand the linker script, so it was rather
monkey-see-monkey-do.


-- 


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

[Bug libstdc++/41622] [c++0x] std::hash<std::string>::operator() copies its argument

[redi at gcc dot gnu dot org]

------- Comment #2 from redi at gcc dot gnu dot org  2009-10-07 16:07 -------
(In reply to comment #1)
> but I am fairly sure I've done the wrong thing to the linker script
> (gnu.ver); I don't really understand the linker script, so it was rather
> monkey-see-monkey-do.

I think the commented out lines should not be there.
Commented out lines are usually used as placeholders for symbols which are
defined later, because more specific globs are needed e.g.

      std::basic_istr[a-d]*;
#     std::basic_istream;
      std::basic_istr[f-z]*;

This is a hint that the istream symbols are handled elsewhere (the reason being
that some istream members are only present in C++0x and need to have a
different symbol version to the C++98 ones)


-- 


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

[Bug libstdc++/41622] [c++0x] std::hash<std::string>::operator() copies its argument

[paolo dot carlini at oracle dot com]

------- Comment #3 from paolo dot carlini at oracle dot com  2009-10-07 16:42 -------
Nope. This library follows the ISO Standards ad TRs, and both the current CD
and TR1 mandates by value. I can try to raise the issue in Santa Cruz by
certainly we can't just change the implementation like this.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |INVALID


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

[Bug libstdc++/41622] [c++0x] std::hash<std::string>::operator() copies its argument

[paolo dot carlini at oracle dot com]

------- Comment #4 from paolo dot carlini at oracle dot com  2009-10-07 16:51 -------
Two very general comments: 1- Certainly, you can't change old exports like
this, you can only *add* exports at later version numbers; 2- If you mean to
contribute more to the library (that would be great!) I would suggest starting
as soon as possible the paperwork for Copyright Assignment
(http://gcc.gnu.org/contribute.html) by sending an email to
assignments@gcc.gnu.org. Thanks!


-- 


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

[Bug libstdc++/41622] [c++0x] std::hash<std::string>::operator() copies its argument

[jbytheway at gmail dot com]

------- Comment #5 from jbytheway at gmail dot com  2009-10-08 19:40 -------
Ah well.  I'm not surprised.  If you do wish to argue the point at Santa Cruz
and I can be any help then let me know.

I have no particular intention to contribute; I'm just working through my
backlog of bug reports (this one started out as a bug report and even after I
realised it wasn't a bug I thought I might as well tell you anyway).


-- 


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

[Bug libstdc++/41622] [c++0x] std::hash<std::string>::operator() copies its argument

[paolo dot carlini at oracle dot com]

------- Comment #6 from paolo dot carlini at oracle dot com  2009-10-08 19:54 -------
(In reply to comment #5)
> I have no particular intention to contribute;

Too bad, I hope you want to reconsider this decision. In case, however, please
don't attach patches, because we can't and we don't want to plagiarize your
code and we can't either commit it as-is without a Copyright Assignment on file
(unless the whole patch is, say, below 10 lines)


-- 


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

[Bug libstdc++/41622] [DR 1245] [c++0x] std::hash<std::string>::operator() copies its argument

[paolo dot carlini at oracle dot com]

------- Comment #7 from paolo dot carlini at oracle dot com  2009-11-08 19:06 -------
DR submitted, preview here, will be in R68:

  http://home.roadrunner.com/~hinnant/issue_review/lwg-active.html#1245

Actually, the proposed resolution at the moment lacks the adjustments to the
hash<thread::id> and hash<type_index> bits, I'll make sure they are properly
dealt with. In any case, any help with the proposed wording is much
appreciated...


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |UNCONFIRMED
         Resolution|INVALID                     |
            Summary|[c++0x]                     |[DR 1245] [c++0x]
                   |std::hash<std::string>::oper|std::hash<std::string>::oper
                   |ator() copies its argument  |ator() copies its argument


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

[Bug libstdc++/41622] [DR 1245] [c++0x] std::hash<std::string>::operator() copies its argument

[paolo dot carlini at oracle dot com]

-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |paolo dot carlini at oracle
                   |dot org                     |dot com
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-11-08 19:07:16
               date|                            |


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

[Bug libstdc++/41622] [DR 1245] [c++0x] std::hash<std::string>::operator() copies its argument

[paolo dot carlini at oracle dot com]

-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |SUSPENDED


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

[Bug libstdc++/41622] [DR 1245] [c++0x] std::hash<std::string>::operator() copies its argument

[paolo at gcc dot gnu dot org]

------- Comment #8 from paolo at gcc dot gnu dot org  2009-11-19 16:55 -------
Subject: Bug 41622

Author: paolo
Date: Thu Nov 19 16:55:25 2009
New Revision: 154335

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=154335
Log:
2009-11-19  Paolo Carlini  <paolo.carlini@oracle.com>

        PR libstdc++/41622
        * include/bits/functional_hash.h: Implement inline the various
        std::hash specializations, using, when appropriate, pass by
        const ref too, per DR 1245.
        * include/tr1_impl/functional_hash.h: Remove, move its contents...
        * include/tr1/functional_hash.h: ... here.
        * include/std/functional: Tweak includes.
        * src/hash_c++0x: Rename to...
        * src/compatibility-c++0x.cc: ... this, implementing compatibility
        std::hash<>::operator() specializations.
        * src/hash.cc: Do not mark specializations as throw().
        * src/Makefile.am: Adjust.
        * include/Makefile.am: Likewise.
        * src/Makefile.in: Regenerate.
        * include/Makefile.in: Likewise.
        * testsuite/util/testsuite_api.h: Define a dummy hash for
        NonDefaultConstructible.
        * testsuite/23_containers/unordered_map/requirements/
        explicit_instantiation/2.cc: Use it.
        * testsuite/23_containers/unordered_multimap/requirements/
        explicit_instantiation/2.cc: Likewise.
        * testsuite/23_containers/unordered_set/requirements/
        explicit_instantiation/2.cc: Likewise.
        * testsuite/23_containers/unordered_multiset/requirements/
        explicit_instantiation/2.cc: Likewise.

Added:
    trunk/libstdc++-v3/src/compatibility-c++0x.cc
      - copied, changed from r154326, trunk/libstdc++-v3/src/hash_c++0x.cc
Removed:
    trunk/libstdc++-v3/include/tr1_impl/functional_hash.h
    trunk/libstdc++-v3/src/hash_c++0x.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/Makefile.am
    trunk/libstdc++-v3/include/Makefile.in
    trunk/libstdc++-v3/include/bits/functional_hash.h
    trunk/libstdc++-v3/include/std/functional
    trunk/libstdc++-v3/include/tr1/functional_hash.h
    trunk/libstdc++-v3/src/Makefile.am
    trunk/libstdc++-v3/src/Makefile.in
    trunk/libstdc++-v3/src/hash.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/explicit_instantiation/2.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/2.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/2.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/explicit_instantiation/2.cc
    trunk/libstdc++-v3/testsuite/util/testsuite_api.h


-- 


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

[Bug libstdc++/41622] [DR 1245] [c++0x] std::hash<std::string>::operator() copies its argument

[paolo dot carlini at oracle dot com]

------- Comment #9 from paolo dot carlini at oracle dot com  2009-11-19 17:03 -------
Fixed for 4.5.0.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|SUSPENDED                   |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.5.0


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