<commit_before># The Parallel Hashmap
   or Abseiling from the shoulders of giants - &copy; <NAME> - March 10, 2019

[tl;dr] We present a novel hashmap design, the Parallel Hashmap. Built on a modified version of Abseil's *flat_hash_map*, the Parallel Hashmap has lower space requirements, is nearly as fast as the underlying *flat_hash_map*, and can be used from multiple threads with high levels of concurrency. The [parallel hashmap](https://github.com/greg7mdp/parallel-hashmap) repository provides header-only version of the flat and node hashmaps, and their parallel versions as well.

### A quick look at the current state of the art

If you haven't been living under a rock, you know that Google open sourced late last year their Abseil library, which includes a very efficient flat hash table implementation. The *absl::flat_hash_map* stores the values directly in a memory array, which avoids memory indirections (this is referred to as closed hashing). 

![closed_hashing](https://github.com/greg7mdp/parallel-hashmap/blob/master/html/img/closed_hashing.png?raw=true)

Using parallel SSE2 instructions, the flat hash table is able to look up items by checking 16 slots in parallel, which allows the implementation to remain fast even when the table is filled to 87.5% capacity.

The graphs below show a comparison of time and memory usage necessary to insert up to 100 million values (each value is composed of two 8-byte integers), between the default hashmap of Visual Studio 2017 (std::unordered_map), and Abseil's flat_hash_map:

![stl_flat comparison](https://github.com/greg7mdp/parallel-hashmap/blob/master/html/img/stl_flat_both.PNG?raw=true)
                       
On the bottom graph, we can see that, as expected, the Abseil *flat_hash_map* is significantly faster that the default stl implementation, typically about three times faster.

### The peak memory usage issue

The top graph shown the memory usage for both tables. 

I used a separate thread to monitor the memory usage, which allows to track the increased memory usage when the table resizes. Indeed, both tables have a peak memory usage that is significantly higher than the memory usage seen between insertions. 

In the case of Abseil's *flat_hash_map*, the values are stored directly in a memory array. The memory usage is constant until the table needs to resize, which is why we see these horizontal sections of memory usage. 

When the *flat_hash_map* reaches 87.5% occupancy, a new array of twice the size is allocated, the values are moved (rehashed) from the smaller to the larger array, and then the smaller array, now empty, is freed. So we see that during the resize, the occupancy is only one third of 87.5%, or 29.1%, and when the smaller array is released, occupancy is half of 87.5% or 43.75%.

The default STL implementation is also subject to this higher peak memory usage, since it typically is implemented with an array of buckets, each bucket having a pointer to a linked list of nodes containing the values. In order to maintain O(1) lookups, the array of buckets also needs to be resized as the table size grows, requiring a 3x temporary memory requirement for moving the old bucket array (1x) to the newly allocated, larger (2x) array. In between the bucket array resizes, the default STL implementation memory usage grows at a constant rate as new values are added to the linked lists.

> Instead of having a separate linked list for each bucket, *std::unordered_map* implementations often use a single linked list (making iteration faster), with buckets pointing to locations within the single linked list. *absl::node_hash_map*, on the other hand, has each bucket pointing to a single value, and collisions are handled with open addressing like for the *absl::flat_hash_map*.

This peak memory usage can be the limiting factor for large tables. Suppose you are on a machine with 32 GB of ram, and the *flat_hash_map* needs to resize when you inserted 10 GB of values in it. 10 GB of values means the array size is 11.42 GB (resizing at 87.5% occupancy), and we need to allocate a new array of double size (22.85 GB), which obviously will not be possible on our 32 GB machine.

For my work developing mechanical engineering software, this has kept me from using flat hash maps, as the high peak memory usage was the limiting factor for the size of FE models which could be loaded on a given machine. So I used other types of maps, such as [sparsepp](https://github.com/greg7mdp/sparsepp) or Google's [cpp-btree](https://code.google.com/archive/p/cpp-btree/).

When the Abseil library was open sourced, I started pondering the issue again. Compared to Google's old dense_hash_map which resized at 50% capacity, the new *absl::flat_hash_map* resizing at 87.5% capacity was more memory friendly, but it still had these significant peaks of memory usage when resizing. 

If only there was a way to eliminate those peaks, the *flat_hash_map* would be close to perfect. But how?

### The peak memory usage solution

Suddenly, it hit me. I had a solution. I would create a hash table that internally is made of an array of 16 hash tables (the submaps). When inserting or looking up an item, the index of the target submap would be decided by the hash of the value to insert. For example, if for a given `size_t hashval`, the index for the internal submap would be computed with: 

`submap_index = (hashval ^ (hashval >> 4)) & 0xF;`

providing an index between 0 and 15.

> In the actual implementation, the size of the array of hash tables is configurable to a power of two, so it can be 2, 4, 8, 16, 32, ... The following illustration shows a parallel_hash_map with 8 submaps.

![index_computation](https://github.com/greg7mdp/parallel-hashmap/blob/master/html/img/index_computation.png?raw=true)

The benefit of this approach would be that the internal tables would each resize on its own when they reach 87.5% capacity, and since each table contains approximately one sixteenth of the values, the memory usage peak would be only one sixteenth of the size we saw for the single *flat_hash_map*.

The rest of this article describes my implementation of this concept that I have done in my [parallel hashmap](https://github.com/greg7mdp/parallel-hashmap) repository. This is a header only library, which provides the following eight hashmaps:
  - phmap::flat_hash_set
  - phmap::flat_hash_map
  - phmap::node_hash_set
  - phmap::node_hash_map
  - phmap::parallel_flat_hash_set
  - phmap::parallel_flat_hash_map
  - phmap::parallel_node_hash_set
  - phmap::parallel_node_hash_map

This implementation requires a C++11 compatible compiler, and provides full compatibility with the std::unordered_map (with the exception of *pointer stability* for the `flat` versions. C++14 and C++17 methods, like `try-emplace`, are provided as well.
The names for it are  *parallel_flat_hash_map* or *parallel_flat_hash_set*, and the *node* equivalents. These hashmaps provide the same external API as the *flat_hash_map*, and internally use a std::array of 2**N *flat_hash_maps*.

I was delighted to find out that not only the *parallel_flat_hash_map* has significant memory usage benefits compared to the *flat_hash_map*, but it also has significant advantages for concurrent programming as I will show later. In the rest of this article, we will focus on the *parallel_flat_hash_map*, but similar results are seen for the *parallel_node_hash_map*, and the *set* versions of course.


### The Parallel Hashmap: memory usage

So, without further ado, let's see the same graphs graphs as above, with the addition of the *parallel_flat_hash_map*. Let us first look at memory usage (the second graph provides a "zoomed-in" view of the location where resizing occurs):

![stl_flat_par comparison](https://github.com/greg7mdp/parallel-hashmap/blob/master/html/img/stl_flat_par_mem.PNG?raw=true)<commit_msg>Update parallel_hashmap.md<commit_after># The Parallel Hashmap
   or Abseiling from the shoulders of giants - &copy; <NAME> - March 10, 2019

[tl;dr] We present a novel hashmap design, the Parallel Hashmap. Built on a modified version of Abseil's *flat_hash_map*, the Parallel Hashmap has lower space requirements, is nearly as fast as the underlying *flat_hash_map*, and can be used from multiple threads with high levels of concurrency. The [parallel hashmap](https://github.com/greg7mdp/parallel-hashmap) repository provides header-only version of the flat and node hashmaps, and their parallel versions as well.

### A quick look at the current state of the art

If you haven't been living under a rock, you know that Google open sourced late last year their Abseil library, which includes a very efficient flat hash table implementation. The *absl::flat_hash_map* stores the values directly in a memory array, which avoids memory indirections (this is referred to as closed hashing). 

![closed_hashing](https://github.com/greg7mdp/parallel-hashmap/blob/master/html/img/closed_hashing.png?raw=true)

Using parallel SSE2 instructions, the flat hash table is able to look up items by checking 16 slots in parallel, which allows the implementation to remain fast even when the table is filled to 87.5% capacity.

The graphs below show a comparison of time and memory usage necessary to insert up to 100 million values (each value is composed of two 8-byte integers), between the default hashmap of Visual Studio 2017 (std::unordered_map), and Abseil's flat_hash_map:

![stl_flat comparison](https://github.com/greg7mdp/parallel-hashmap/blob/master/html/img/stl_flat_both.PNG?raw=true)
                       
On the bottom graph, we can see that, as expected, the Abseil *flat_hash_map* is significantly faster that the default stl implementation, typically about three times faster.

### The peak memory usage issue

The top graph shown the memory usage for both tables. 

I used a separate thread to monitor the memory usage, which allows to track the increased memory usage when the table resizes. Indeed, both tables have a peak memory usage that is significantly higher than the memory usage seen between insertions. 

In the case of Abseil's *flat_hash_map*, the values are stored directly in a memory array. The memory usage is constant until the table needs to resize, which is why we see these horizontal sections of memory usage. 

When the *flat_hash_map* reaches 87.5% occupancy, a new array of twice the size is allocated, the values are moved (rehashed) from the smaller to the larger array, and then the smaller array, now empty, is freed. So we see that during the resize, the occupancy is only one third of 87.5%, or 29.1%, and when the smaller array is released, occupancy is half of 87.5% or 43.75%.

The default STL implementation is also subject to this higher peak memory usage, since it typically is implemented with an array of buckets, each bucket having a pointer to a linked list of nodes containing the values. In order to maintain O(1) lookups, the array of buckets also needs to be resized as the table size grows, requiring a 3x temporary memory requirement for moving the old bucket array (1x) to the newly allocated, larger (2x) array. In between the bucket array resizes, the default STL implementation memory usage grows at a constant rate as new values are added to the linked lists.

> Instead of having a separate linked list for each bucket, *std::unordered_map* implementations often use a single linked list (making iteration faster), with buckets pointing to locations within the single linked list. *absl::node_hash_map*, on the other hand, has each bucket pointing to a single value, and collisions are handled with open addressing like for the *absl::flat_hash_map*.

This peak memory usage can be the limiting factor for large tables. Suppose you are on a machine with 32 GB of ram, and the *flat_hash_map* needs to resize when you inserted 10 GB of values in it. 10 GB of values means the array size is 11.42 GB (resizing at 87.5% occupancy), and we need to allocate a new array of double size (22.85 GB), which obviously will not be possible on our 32 GB machine.

For my work developing mechanical engineering software, this has kept me from using flat hash maps, as the high peak memory usage was the limiting factor for the size of FE models which could be loaded on a given machine. So I used other types of maps, such as [sparsepp](https://github.com/greg7mdp/sparsepp) or Google's [cpp-btree](https://code.google.com/archive/p/cpp-btree/).

When the Abseil library was open sourced, I started pondering the issue again. Compared to Google's old dense_hash_map which resized at 50% capacity, the new *absl::flat_hash_map* resizing at 87.5% capacity was more memory friendly, but it still had these significant peaks of memory usage when resizing. 

If only there was a way to eliminate those peaks, the *flat_hash_map* would be close to perfect. But how?

### The peak memory usage solution

Suddenly, it hit me. I had a solution. I would create a hash table that internally is made of an array of 16 hash tables (the submaps). When inserting or looking up an item, the index of the target submap would be decided by the hash of the value to insert. For example, if for a given `size_t hashval`, the index for the internal submap would be computed with: 

`submap_index = (hashval ^ (hashval >> 4)) & 0xF;`

providing an index between 0 and 15.

> In the actual implementation, the size of the array of hash tables is configurable to a power of two, so it can be 2, 4, 8, 16, 32, ... The following illustration shows a parallel_hash_map with 8 submaps.

![index_computation](https://github.com/greg7mdp/parallel-hashmap/blob/master/html/img/index_computation.png?raw=true)

The benefit of this approach would be that the internal tables would each resize on its own when they reach 87.5% capacity, and since each table contains approximately one sixteenth of the values, the memory usage peak would be only one sixteenth of the size we saw for the single *flat_hash_map*.

The rest of this article describes my implementation of this concept that I have done in my [parallel hashmap](https://github.com/greg7mdp/parallel-hashmap) repository. This is a header only library, which provides the following eight hashmaps:

- phmap::flat_hash_set
- phmap::flat_hash_map
- phmap::node_hash_set
- phmap::node_hash_map
- phmap::parallel_flat_hash_set
- phmap::parallel_flat_hash_map
- phmap::parallel_node_hash_set
- phmap::parallel_node_hash_map

This implementation requires a C++11 compatible compiler, and provides full compatibility with the std::unordered_map (with the exception of *pointer stability* for the `flat` versions. C++14 and C++17 methods, like `try-emplace`, are provided as well.
The names for it are  *parallel_flat_hash_map* or *parallel_flat_hash_set*, and the *node* equivalents. These hashmaps provide the same external API as the *flat_hash_map*, and internally use a std::array of 2**N *flat_hash_maps*.

I was delighted to find out that not only the *parallel_flat_hash_map* has significant memory usage benefits compared to the *flat_hash_map*, but it also has significant advantages for concurrent programming as I will show later. In the rest of this article, we will focus on the *parallel_flat_hash_map*, but similar results are seen for the *parallel_node_hash_map*, and the *set* versions of course.


### The Parallel Hashmap: memory usage

So, without further ado, let's see the same graphs graphs as above, with the addition of the *parallel_flat_hash_map*. Let us first look at memory usage (the second graph provides a "zoomed-in" view of the location where resizing occurs):

![stl_flat_par comparison](https://github.com/greg7mdp/parallel-hashmap/blob/master/html/img/stl_flat_par_mem.PNG?raw=true)
{'fraction_non_alphanumeric': 0.05799214095576118, 'fraction_numerical': 0.012168842692356446, 'mean_word_length': 4.708755426917511, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 13, 'https://': 16, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1969543', 'n_tokens_mistral': 4284, 'n_tokens_neox': 4058, 'n_words': 2282}