P1696R0
Refinement proposal for P0920 Precalculated hash values in lookup

1. Motivation and Scope

std::array<std::unordered_map<std::string, int>, array_size> maps;

void update(const std::string& user)
{
  const auto hash = maps.front().hash_function()(user);
  for(auto& m : maps) {
    auto it = m.find(user, hash);
    // ...
  }
}

This approach has a number of problems, including the lack of safety around hasher misuse and the lack of clarity around sharing hash values across multiple containers.

1.1. Hasher misuse

Firstly, this is plain incorrect if the hasher for the container is stateful. Secondly, even if the user used a different hasher instance of the correct hasher type and the hasher is not stateful, it increases the chance of mismatch between the hash value and the key, especially when the hasher of the container gets changed. It would require auditing and potentially changing all call sites of this API.

1.2. Unclear semantics of sharing hash values across containers

1.3. Use of raw hash values limits optimization opportunities

In addition, in a few use cases, sizable performance gains came mainly from prefetching the pertinent cache lines, as opposed to merely precalculating the hash value. This optimization is not possible with the API [P0920R2] proposed.

1.4. Extensibility considerations

try_emplace(const key_type& k, size_t hash, Args&&... args);
try_emplace(const key_type& k, Args&&... args);

For emplace, disambiguation is more difficult, which suggests an API akin to emplace_hint where the first parameter is the precalculated hash / position hint.

2. Design alternatives and respective concerns

2.1. Encapsulate hash values with hash_token

std::unordered_map<std::string, int> m;
auto ht = m.token(key);
m.find(ht, key);

2.1.1. Possible mismatch between hash_token and key

Conceivably, the hash table implementation could check whether the supplied hash_tokens match the keys in debug builds. (Note that we could do that with raw hash values as well and we acknowledge this is an unresolved problem with this approach.)

2.1.2. Whether to store reference / copy of key in hash_token

2.1.3. Sharing hash_tokens across different containers

2.2. “Caching” hash values in keys

struct KeyWithHash {
  std::string key_;
  size_t hash_;
};

std::unordered_map<std::string, int, MyHash, MyEqualTo> m;
m.emplace(“foo”, 42);

KeyWithHash kh;
kh.key_ = "foo";
kh.hash_ = m.hash_function()(kh.key_); // precalculated
m.find(kh); // heterogeneous lookup

Note that this approach does not need the committee need to adopt any changes to the standard. This is an option available to users with or without [P0920R2]. This could also be a mitigation that would buy us time to explore the design space further.

3. Proposed Wording

3.1. Option 1: Revert [P0920R2]

3.2. Option 2: Replace size_t with an opaque token

The proposed changes are relative to the working draft of the standard as of [N4810].

Modify 22.2.7 [unord.req] paragraph 11.23 as follows:

hk and hke denote values of type size_t X::hash_token_type .

Add the following paragraph to 22.2.7 [unord.req]:

Member function templates find, count, equal_range, and contains that take a hash_token_type shall not participate in overload resolution unless std::is_empty_v<Hash> is true.

Modify Table 70 in 22.2.7 [unord.req] as follows:

Expression	Return type	Assertion/note pre-/post-condition	Complexity
X::hash_token_type	An implementation-defined type that can be used to look up its associated key.	Expects: hash_token_type meets the Cpp17DefaultConstructible requirements.	compile time
b.token(k)	X::hash_token_type	Returns: returns a value hk of type X::hash_token_type such that b.find(hk, k) equals b.find(k)	constant
a_tran.token(ke)	X::hash_token_type	Returns: returns a value hke of type X::hash_token_type such that a_tran.find(hke, ke) equals a_tran.find(ke)	constant
b.find(k, hk) b.find(hk, k)	iterator; const_iterator for const b.	Expects: b.hash_function()(k) equals hk, b.token(k) equals hk, Returns: an iterator pointing to an element with key equivalent to k, or b.end() if no such element exists.	Average case O(1), worst case O(b.size()).
a_tran.find(ke, hke) a_tran.find(hke, ke)	iterator; const_iterator for const a_tran.	Expects: a_tran.hash_function()(ke) equals hke, a_tran.token(ke) equals hke, Returns: an iterator pointing to an element with key equivalent to ke, or a_tran.end() if no such element exists.	Average case O(1), worst case O(a_tran.size()).
b.count(k, hk) b.count(hk, k)	size_type	Expects: b.hash_function()(k) equals hk, b.token(k) equals hk, Returns: the number of elements with key equivalent to k.	Average case O(b.count(k)), worst case O(b.size()).
a_tran.count(ke, hke) a_tran.count(hke, ke)	size_type	Expects: a_tran.hash_function()(ke) equals hke, a_tran.token(ke) equals hke, Returns: the number of elements with key equivalent to ke.	Average case O(a_tran.count(ke)), worst case O(a_tran.size()).
b.contains(k, hk) b.contains(hk, k)	bool	Expects: b.hash_function()(k) equals hk, b.token(k) equals hk, Effects: Equivalent to b.find(k, hk) != b.end()	Average case O(1), worst case O(b.size())
a_tran.contains(ke, hke) a_tran.contains(hke, ke)	bool	Expects: a_tran.hash_function()(ke) equals hke, a_tran.token(ke) equals hke, Effects: Equivalent to a_tran.find(ke, hke) != a_tran.end()	Average case O(1), worst case O(a_tran.size())
b.equal_range(k, hk) b.equal_range(hk, k)	pair<iterator, iterator>; pair<const_iterator, const_iterator> for const b.	Expects: b.hash_function()(k) equals hk, b.token(k) equals hk, Returns: a range containing all elements with keys equivalent to k. Returns make_pair(b.end(), b.end()) if no such elements exist.	Average case O(b.count(k)), worst case O(b.size()).
a_tran.equal_range(ke, hke) a_tran.equal_range(hke, ke)	pair<iterator, iterator>; pair<const_iterator, const_iterator> for const a_tran.	Expects: a_tran.hash_function()(ke) equals hke, a_tran.token(ke) equals hke, Returns: a range containing all elements with keys equivalent to ke. Returns make_pair(a_tran.end(), a_tran.end()) if no such elements exist.	Average case O(a_tran.count(ke)), worst case O(a_tran.size()).

Make the following changes to:

• 22.5.4.1 [unord.map.overview]

• 22.5.5.1 [unord.multimap.overview]

• 22.5.6.1 [unord.set.overview]

• 22.5.7.1 [unord.multiset.overview]

using const_local_iterator = implementation-defined; // see 22.2
using node_type            = unspecified;
using insert_return_type   = insert-return-type<iterator, node_type>;
using hash_token_type      = implementation-defined; // see 22.2
...
hash_token_type                    token(const key_type& k);
template <class K> hash_token_type token(const K& k);
iterator       find(const key_type& k);
const_iterator find(const key_type& k) const;
iterator       find(const hash_token_type& hash_token, const key_type& k, size_t hash);
const_iterator find(const hash_token_type& hash_token, const key_type& k, size_t hash) const;
template <class K> iterator       find(const K& k);
template <class K> const_iterator find(const K& k) const;
template <class K> iterator       find(const hash_token_type& hash_token, const K& k, size_t hash);
template <class K> const_iterator find(const hash_token_type& hash_token, const K& k, size_t hash) const;
size_type count(const key_type& k) const;
size_type count(const hash_token_type& hash_token, const key_type& k, size_t hash) const;
template <class K> size_type count(const K& k) const;
template <class K> size_type count(const hash_token_type& hash_token, const K& k, size_t hash) const;
bool contains(const key_type& k) const;
bool contains(const hash_token_type& hash_token, const key_type& k, size_t hash) const;
template <class K> bool contains(const K& k) const;
template <class K> bool contains(const hash_token_type& hash_token, const K& k, size_t hash) const;
pair<iterator, iterator>             equal_range(const key_type& k);
pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
pair<iterator, iterator>             equal_range(const hash_token_type& hash_token, const key_type& k, size_t hash);
pair<const_iterator, const_iterator> equal_range(const hash_token_type& hash_token, const key_type& k, size_t hash) const;
template <class K> pair<iterator, iterator>             equal_range(const K& k);
template <class K> pair<const_iterator, const_iterator> equal_range(const K& k) const;
template <class K> pair<iterator, iterator>             equal_range(const hash_token_type& hash_token, const K& k, size_t hash);
template <class K> pair<const_iterator, const_iterator> equal_range(const hash_token_type& hash_token, const K& k, size_t hash) const;

4. Implementation and Usage Experiences

Facebook’s [F14] hash tables used an opaque hash token approach. In our experiences, such an approach allowed several use cases to precalculate hash and prefetch the relevant cache lines, resulting in CPU and memory efficiency improvement.

5. Acknowledgements