(Repost of:
http://lists.llvm.org/pipermail/cfe-commits/Week-of-Mon-20160118/147379.html
on Phabricator as requested by Eric.)
This is a follow-up to r239666: "Fix PR12999 - unordered_set::insert
calls operator new when no insert occurs". That fix didn't apply to
unordered_map because unordered_map::value_type gets packed inside:
union __value_type {
pair<key_type, mapped_type> __nc; // Only C++11 or higher. pair<const key_type, mapped_type> __cc; // Always. // Constructors...
};
and the underlying hash_table only knows about value_type.
This patch should avoid unnecessary mallocs whenever the caller passes
in a pair<T, U> such that T is trivially convertible to key_type.
Since __hash_table's value_type is really *never* a pair (for
unordered_map, it's a union of two pairs) the static dispatch is all in
unordered_map. It's doing this:
- If the argument isn't a pair<>, alloc.
- If argument.first can be referenced as const key_type&, don't alloc.
- If argument.first can be trivially converted to key_type, don't alloc.
- Else alloc.
In the pre-C++11 world the caller has already converted to
unordered_map::value_type. We can always avoid the alloc.
To support all of this:
- In C++03, unordered_map_equal and unordered_map_hasher need to handle unordered_map::value_type.
- In C++03, hash_table::insert_unique_value() now takes its argument by template.
- In C++11, hash_table::insert_unique_value() is now a one-liner that forwards to __insert_unique_key_value() for the real work.
- The versions of hash_table::construct_node() that take a pre-computed hash have been renamed to __construct_node_hash(), and these versions use perfect forwarding.
This is one of my first patches for libc++, so I may need some extra
guidance:
- Did I successfully match the coding style? (I'm kind of lost without clang-format TBH.)
- Should I separate the change to __construct_node_hash() into a separate prep commit? (I would if this were LLVM, but I'm not sure if the common practice is different for libc++.)
After this I'll fix the same performance issue in std::map (and I
assume std::set?).
The traits LGTM.