0920R2_precalculated_hash_values_in_lookup.bs

<pre class='metadata'>
Title: Precalculated hash values in lookup
Shortname: P0920
Revision: 2
Status: P
Date: 2019-02-22
Group: WG21
Audience: LWG
URL: http://wg21.link/P0920r2
Editor: Mateusz Pusz, Epam Systems http://www.epam.com, mateusz.pusz@gmail.com, https://www.train-it.eu
Abstract: This proposal extends the interface of unordered containers with the member function overloads that
    have one additional argument taking a precalculated hash value for the value being queried. 
Repository: mpusz/wg21_papers
!Source: <a href="https://github.com/mpusz/wg21_papers/blob/master/src/0920_precalculated_hash_values_in_lookup.bs">github.com/mpusz/wg21_papers/blob/master/src/0920_precalculated_hash_values_in_lookup.bs</a>
Markup Shorthands: markdown on
</pre>


Motivation and Scope {#motivation-and-scope}
============================================

In business scenarios it often happens that we have to look for the same keyword in more than one container at a time.
Doing that is expensive right now as it forces hash value recalculation on every lookup.

With the changes proposed by this paper the following code will calculate the hash value only once per each run
of the function `update()`:

```cpp
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);
    // ...
  }
}
```


Prior Work {#prior-work}
========================

Proposed feature was implemented in the [tsl::hopscotch_map](https://github.com/Tessil/hopscotch-map) and proved
to deliver significant performance improvements.


Impact On The Standard {#impact}
================================

This proposal modifies the unordered associative containers in `<unordered_map>` and `<unordered_set>` by
overloading the lookup member functions with member function templates having one additional parameter.

There are no language changes. 

All existing C++17 code is unaffected.


Considered Alternatives {#alternatives}
=======================================

Stateful hash object {#stateful-hash}
-------------------------------------

Similar, although a bit slower, behavior can be obtained with usage of a stateful hash object that introduces additional
branch on every lookup:

```cpp
template<typename Key, typename Hash>
struct hash_cache {
  inline static std::pair<Key, std::size_t> cache;
  size_t operator()(const Key& k) const
  {
    std::size_t val{};
    if (k != cache.first) {
      cache.first = k;
      cache.second = Hash()(k);
    }
    val = cache.second;
    return val;
  }
};
```

However, the case complicates in a multithreaded environment where synchronization has to be introduced to
such a `hash_cache_sync` helper class:

```cpp
template<typename Key, typename Hash>
struct hash_cache_sync {
  inline static std::mutex m;
  inline static std::pair<Key, std::size_t> cache;
  size_t operator()(const Key& k) const
  {
    std::size_t val{};
    {
      std::scoped_lock lock(m);
      if (k != cache.first) {
        cache.first = k;
        cache.second = Hash()(k);
      }
      val = cache.second;
    }
    return val;
  }
};
```

Such synchronization nearly negates all benefits of having a cache. 

Another problem with that solution happens in the case of the heterogeneous lookup introduced by [[!p0919r3]]:

```cpp
struct string_hash {
  using transparent_key_equal = std::equal_to<>;
  std::pair<???, std::size_t> cache;
  std::size_t operator()(std::string_view txt) const;
  std::size_t operator()(const std::string& txt) const;
  std::size_t operator()(const char* txt) const;
};
```

In such a case there is no one good `Key` type to be used for storage in a cache. Additional conversions and object
constructions will always be involved which negates all benefits of having the heterogeneous lookup feature. 



Proposed Wording {#wording}
===========================

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

Modify **21.2.7 [unord.req]** paragraph 11 as follows:

Add new paragraph 11.23 in **21.2.7 [unord.req]**:

<blockquote>
<ins>
    - `hk` and `hke` denote values of type `size_t`,
</ins>
</blockquote>

Modify table 70 in section **21.2.7 [unord.req]** as follows:

<blockquote>

<table>
  <tr>
    <th>Expression</th>
    <th>Return type</th>
    <th>Assertion/note pre-/post-condition</th>
    <th>Complexity</th>
  </tr>
  <tr>
    <td>`b.find(k)`</td>
    <td>`iterator`; `const_iterator` for const `b`.</td>
    <td><i>Returns:</i> an iterator pointing to an element with key equivalent to `k`, or `b.end()` 
        if no such element exists.</td>
    <td>Average case O(1), worst case O(`b.size()`).</td>
  </tr>
  <tr>
    <td><ins>`b.find(k, hk)`</ins></td>
    <td><ins>`iterator`; `const_iterator` for const `b`.</ins></td>
    <td><ins><i>Expects:</i> `b.hash_function()(k)` equals `hk`,<br/>
        <i>Returns:</i> an iterator pointing to an element with key equivalent to `k`, or `b.end()` 
        if no such element exists.</ins></td>
    <td><ins>Average case O(1), worst case O(`b.size()`).</ins></td>
  </tr>
  <tr>
    <td>`a_tran.find(ke)`</td>
    <td>`iterator`; `const_iterator` for const `a_tran`.</td>
    <td><i>Returns:</i> an iterator pointing to an element with key equivalent to `ke`, or `a_tran.end()` if no such
    element exists.</td>
    <td>Average case O(1), worst case O(`a_tran.size()`).</td>
  </tr>
  <tr>
    <td><ins>`a_tran.find(ke, hke)`</ins></td>
    <td><ins>`iterator`; `const_iterator` for const `a_tran`.</ins></td>
    <td><ins><i>Expects:</i> `a_tran.hash_function()(ke)` equals `hke`,<br/>
        <i>Returns:</i> an iterator pointing to an element with key equivalent to `ke`, or `a_tran.end()` if no such
        element exists.</ins></td>
    <td><ins>Average case O(1), worst case O(`a_tran.size()`).</ins></td>
  </tr>
  <tr>
    <td>`b.count(k)`<br/></td>
    <td>`size_type`</td>
    <td><i>Returns:</i> the number of elements with key equivalent to `k`.</td>
    <td>Average case O(`b.count(k)`), worst case O(`b.size()`).</td>
  </tr>
  <tr>
    <td><ins>`b.count(k, hk)`</ins></td>
    <td>`size_type`</td>
    <td><ins><i>Expects:</i> `b.hash_function()(k)` equals `hk`,<br/>
        <i>Returns:</i> the number of elements with key equivalent to `k`.</ins></td>
    <td><ins>Average case O(`b.count(k)`), worst case O(`b.size()`).</ins></td>
  </tr>
  <tr>
    <td>`a_tran.count(ke)`</td>
    <td>`size_type`</td>
    <td><i>Returns:</i> the number of elements with key equivalent to `ke`.</td>
    <td>Average case O(`a_tran.count(ke)`), worst case O(`a_tran.size()`).</td>
  </tr>
  <tr>
    <td><ins>`a_tran.count(ke, hke)`</ins></td>
    <td>`size_type`</td>
    <td><ins><i>Expects:</i> `a_tran.hash_function()(ke)` equals `hke`,<br/>
        <i>Returns:</i> the number of elements with key equivalent to `ke`.</ins></td>
    <td><ins>Average case O(`a_tran.count(ke)`), worst case O(`a_tran.size()`).</ins></td>
  </tr>
  <tr>
    <td>`b.contains(k)`</td>
    <td>bool</td>
    <td><ins><i>Effects:</i></ins> Equivalent to `b.find(k) != b.end()`</td>
    <td>Average case O(1), worst case O(`b.size()`)</td>
  </tr>
  <tr>
    <td><ins>`b.contains(k, hk)`</ins></td>
    <td><ins>bool</ins></td>
    <td><ins><i>Expects:</i> `b.hash_function()(k)` equals `hk`,<br/>
        <i>Effects:</i> Equivalent to `b.find(k, hk) != b.end()`</ins></td>
    <td><ins>Average case O(1), worst case O(`b.size()`)</ins></td>
  </tr>
  <tr>
    <td>`a_tran.contains(ke)`</td>
    <td>bool</td>
    <td><ins><i>Effects:</i></ins> Equivalent to `a_tran.find(ke) != a_tran.end()`</td>
    <td>Average case O(1), worst case O(`a_tran.size()`)</td>
  </tr>
  <tr>
    <td><ins>`a_tran.contains(ke, hke)`</ins></td>
    <td><ins>bool</ins></td>
    <td><ins><i>Expects:</i> `a_tran.hash_function()(ke)` equals `hke`,<br/>
        <i>Effects:</i> Equivalent to `a_tran.find(ke, hke) != a_tran.end()`</ins></td>
    <td><ins>Average case O(1), worst case O(`a_tran.size()`)</ins></td>
  </tr>
  <tr>
    <td>`b.equal_range(k)`</td>
    <td>`pair<iterator, iterator>`; `pair<const_iterator, const_iterator>` for const `b`.</td>
    <td><i>Returns:</i> a range containing all elements with keys equivalent to `k`. Returns
        `make_pair(b.end(), b.end())` if no such elements exist.</td>
    <td>Average case O(`b.count(k)`), worst case O(`b.size()`).</td>
  </tr>
  <tr>
    <td><ins>`b.equal_range(k, hk)`</ins></td>
    <td><ins>`pair<iterator, iterator>`; `pair<const_iterator, const_iterator>` for const `b`.</ins></td>
    <td><ins><i>Expects:</i> `b.hash_function()(k)` equals `hk`,<br/>
        <i>Returns:</i> a range containing all elements with keys equivalent to `k`. Returns
        `make_pair(b.end(), b.end())` if no such elements exist.</ins></td>
    <td><ins>Average case O(`b.count(k)`), worst case O(`b.size()`).</ins></td>
  </tr>
  <tr>
    <td>`a_tran.equal_range(ke)`</td>
    <td>`pair<iterator, iterator>`; `pair<const_iterator, const_iterator>` for const `a_tran`.</td>
    <td><i>Returns:</i> a range containing all elements with keys equivalent to `ke`. Returns
        `make_pair(a_tran.end(), a_tran.end())` if no such elements exist.</td>
    <td>Average case O(`a_tran.count(ke)`), worst case O(`a_tran.size()`).</td>
  </tr>
  <tr>
    <td><ins>`a_tran.equal_range(ke, hke)`</ins></td>
    <td><ins>`pair<iterator, iterator>`; `pair<const_iterator, const_iterator>` for const `a_tran`.</ins></td>
    <td><ins><i>Expects:</i> `a_tran.hash_function()(ke)` equals `hke`,<br/>
        <i>Returns:</i> a range containing all elements with keys equivalent to `ke`. Returns
        `make_pair(a_tran.end(), a_tran.end())` if no such elements exist.</ins></td>
    <td><ins>Average case O(`a_tran.count(ke)`), worst case O(`a_tran.size()`).</ins></td>
  </tr>
</table>

</blockquote>

Add the following changes to:
  - **21.5.4.1 [unord.map.overview]**
  - **21.5.5.1 [unord.multimap.overview]**
  - **21.5.6.1 [unord.set.overview]**
  - **21.5.7.1 [unord.multiset.overview]**  

<blockquote>
<pre>
iterator       find(const key_type& k);
const_iterator find(const key_type& k) const;
<ins>iterator       find(const key_type& k, size_t hash);
const_iterator find(const key_type& k, size_t hash) const;</ins>
template &lt;class K> iterator       find(const K& k);
template &lt;class K> const_iterator find(const K& k) const;
<ins>template &lt;class K> iterator       find(const K& k, size_t hash);
template &lt;class K> const_iterator find(const K& k, size_t hash) const;</ins>
size_type count(const key_type& k) const;
<ins>size_type count(const key_type& k, size_t hash) const;</ins>
template &lt;class K> size_type count(const K& k) const;
<ins>template &lt;class K> size_type count(const K& k, size_t hash) const;</ins>
bool contains(const key_type& k) const;
<ins>bool contains(const key_type& k, size_t hash) const;</ins>
template &lt;class K> bool contains(const K& k) const;
<ins>template &lt;class K> bool contains(const K& k, size_t hash) const;</ins>
pair&lt;iterator, iterator>             equal_range(const key_type& k);
pair&lt;const_iterator, const_iterator> equal_range(const key_type& k) const;
<ins>pair&lt;iterator, iterator>             equal_range(const key_type& k, size_t hash);
pair&lt;const_iterator, const_iterator> equal_range(const key_type& k, size_t hash) const;</ins>
template &lt;class K> pair&lt;iterator, iterator>             equal_range(const K& k);
template &lt;class K> pair&lt;const_iterator, const_iterator> equal_range(const K& k) const;
<ins>template &lt;class K> pair&lt;iterator, iterator>             equal_range(const K& k, size_t hash);
template &lt;class K> pair&lt;const_iterator, const_iterator> equal_range(const K& k, size_t hash) const;</ins>
</pre>
</blockquote>


Feature Testing {#feature-testing}
==================================

Add the following row to a **Table 36** in **16.3.1 [support.limits.general]** paragraph 3:  

<table>
  <tr>
    <th>Macro name</th>
    <th>Value</th>
    <th>Header(s)</th>
  </tr>
  <tr>
    <td colspan="3">...</td>
  </tr>
  <tr>
    <td>__cpp_lib_generic_associative_lookup</td>
    <td>201304L</td>
    <td>&lt;map&gt; &lt;set&gt;</td>
  </tr>
  <tr>
    <td>__cpp_lib_generic_unordered_lookup</td>
    <td>201811L</td>
    <td>&lt;unordered_map&gt; &lt;unordered_set&gt;</td>
  </tr>
  <tr>
    <td><ins>__cpp_lib_generic_unordered_hash_lookup</ins></td>
    <td></td>
    <td><ins>&lt;unordered_map&gt; &lt;unordered_set&gt;</ins></td>
  </tr>
</table>


Implementation Experience {#implementation}
===========================================

Changes related to that proposal are partially implemented in [GitHub repo](https://github.com/mpusz/unordered_v2)
against [libc++ 7.0.0](https://libcxx.llvm.org).

Simple performance tests provided there proved nearly:
- 20% performance gain for short text
- 50% performance gain for long text

Revision History {#revision-history}
====================================

r1 ➡ r2 [[diff](https://github.com/mpusz/wg21-papers/commit/c2b056b9ce238eea28c25a4ae2bddbbe468ecefa)] {#r1r2}
-------------------------------------------------------------------------------------------------------------

- Table 70 updated according to [[!p0788r3]]


r0 ➡ r1 [[diff](https://github.com/mpusz/wg21-papers/commit/8a1ba0ea256efaf2ac65c3e136b60b0c8dea7d96)] {#r0r1}
-------------------------------------------------------------------------------------------------------------

- Rebased to [[!n4791]]
- Simplified wording by aggregating rows in a table (where possible) and providing overview wording once
    for all the containers
- Feature test macro name changed

Acknowledgements {#acknowledgements}
====================================

Special thanks and recognition goes to [Epam Systems](http://www.epam.com) for supporting my
membership in the ISO C++ Committee and the production of this proposal.