unord: Extract key to avoid preemptive mallocs in insert/emplace

unordered_set::emplace and unordered_map::emplace construct a node, then
try to insert it.  If insertion fails, the node gets deleted.

To avoid this unnecessary malloc traffic, check to see if the argument
to emplace has the appropriate key_type.  If so, we can use that key
directly and delay the malloc until we're sure we're inserting something
new.

Test updates by Eric Fiselier, who rewrote the old allocation tests to
include the new cases.

There are two orthogonal future directions:

1. Apply the same optimization to set and map.

2. Extend the optimization to when the argument is not key_type, but can
   be converted to it without side effects.  Ideally, we could do this
   whenever key_type is trivially destructible and the argument is
   trivially convertible to key_type, but in practise the relevant type
   traits "blow up sometimes".  At least, we should catch a few simple
   cases (such as when both are primitive types).

llvm-svn: 263746

0 files changed, 0 insertions, 0 deletions