public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/41622]  New: [c++0x] std::hash<std::string>::operator() copies its argument
@ 2009-10-07 15:40 jbytheway at gmail dot com
  2009-10-07 15:45 ` [Bug libstdc++/41622] " jbytheway at gmail dot com
                   ` (10 more replies)
  0 siblings, 11 replies; 12+ messages in thread
From: jbytheway at gmail dot com @ 2009-10-07 15:40 UTC (permalink / raw)
  To: gcc-bugs

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


^ permalink raw reply	[flat|nested] 12+ messages in thread
end of thread, other threads:[~2009-11-19 17:04 UTC | newest]

Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-10-07 15:40 [Bug libstdc++/41622] New: [c++0x] std::hash<std::string>::operator() copies its argument jbytheway at gmail dot com
2009-10-07 15:45 ` [Bug libstdc++/41622] " jbytheway at gmail dot com
2009-10-07 16:07 ` redi at gcc dot gnu dot org
2009-10-07 16:42 ` paolo dot carlini at oracle dot com
2009-10-07 16:52 ` paolo dot carlini at oracle dot com
2009-10-08 19:40 ` jbytheway at gmail dot com
2009-10-08 19:54 ` paolo dot carlini at oracle dot com
2009-11-08 19:06 ` [Bug libstdc++/41622] [DR 1245] " paolo dot carlini at oracle dot com
2009-11-08 19:07 ` paolo dot carlini at oracle dot com
2009-11-08 19:07 ` paolo dot carlini at oracle dot com
2009-11-19 16:56 ` paolo at gcc dot gnu dot org
2009-11-19 17:04 ` paolo dot carlini at oracle dot com

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).