TL;DR↵
------↵
The Policy Hash Table has 20-30% faster linear insertion/deletion, equal performance for random insertion/deletion, and 3-10x increase for writes/reads. However, clear() is slower on a Policy Hash Table with random insertion order.↵
↵
Background↵
------↵
I've often been irritated by how slow unordered_map is in C++. Too often, I have something that runs fast enough in terms of complexity, but the constant factor from unordered_map slows down the solution too much. Yesterday though, after using the useful order statistics tree from https://codeforces.me/blog/entry/11080, I was curious if there were any other useful data structures hiding in the Policy STL. And lo and behold, I found a hash table.↵
↵
Benchmarks↵
------------------↵
Well, enough backstory, let's look at some numbers.↵
All benchmarks below are compiled with C++14 -O2.↵
↵
~~~~~↵
unordered map linear insertion: 0.816795↵
policy hash table linear insertion: 0.442094↵
↵
unordered map linear read/write: 1.91384↵
policy hash table linear read/write: 0.216669↵
↵
unordered map random insertion: 2.98216↵
policy hash table random insertion: 3.13651↵
↵
unordered map random read/write: 2.12804↵
policy hash table random read/write: 0.356518↵
~~~~~↵
↵
While for linear insertions, the policy hash table gives modest improvements, the policy hash table blows the unordered_map out of the water when it comes to reads/writes. These are order of magnitude improvements that make hash tables usable when they previously weren't.↵
Example↵
------↵
Benchmarks of course, don't always reflect the real world. So here's an example of it allowing a solution to be accepted that TLE's with unordered_map.↵
↵
Example problem (5000 ms time limit): http://codeforces.me/contest/264/problem/C ↵
Solution with unordered_map: http://codeforces.me/contest/264/submission/40542899 (TLE on test case 8) ↵
Solution with policy hash table directly substituted in: http://codeforces.me/contest/264/submission/40573491 (TLE on test case 26) ↵
Solution with unordered_map, rewritten to not use clears:↵
http://codeforces.me/contest/264/submission/40590437 (TLE on test case 26)↵
Solution with policy hash table and rewritten to not use clears: http://codeforces.me/contest/264/submission/40574196 (AC with max time of 3180 ms) ↵
↵
Usage↵
------↵
To use this data structure:↵
↵
~~~~~↵
#include <ext/pb_ds/assoc_container.hpp>↵
using namespace __gnu_pbds;↵
cc_hash_table<int, int> table;↵
~~~~~↵
From there, the API seems almost exactly the same.↵
↵
Thanks to ~adamant,2018-07-20 for his post that revealed to me the existence of policy data structures, and thanks to ~tonynater,2018-07-20 for the discussion.↵
↵
PS: In other posts for unordered_map, I've seen people claim that reserve and max_load_factor could increase performance drastically. They didn't seem to do much for me. However, if you want to do something similar for these hash tables, use `typedef cc_hash_table<↵
int, int, hash<int>, equal_to<int>, direct_mask_range_hashing<int>,↵
hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>>↵
ht;`, and you should be able to resize and set load factor manually as well.↵
↵
↵
↵
↵
Code for the benchmarks can be found here: https://ideone.com/ZkNMbH↵
↵
------↵
The Policy Hash Table has 20-30% faster linear insertion/deletion, equal performance for random insertion/deletion, and 3-10x increase for writes/reads. However, clear() is slower on a Policy Hash Table with random insertion order.↵
↵
Background↵
------↵
I've often been irritated by how slow unordered_map is in C++. Too often, I have something that runs fast enough in terms of complexity, but the constant factor from unordered_map slows down the solution too much. Yesterday though, after using the useful order statistics tree from https://codeforces.me/blog/entry/11080, I was curious if there were any other useful data structures hiding in the Policy STL. And lo and behold, I found a hash table.↵
↵
Benchmarks↵
------------------↵
Well, enough backstory, let's look at some numbers.↵
All benchmarks below are compiled with C++14 -O2.↵
↵
~~~~~↵
unordered map linear insertion: 0.816795↵
policy hash table linear insertion: 0.442094↵
↵
unordered map linear read/write: 1.91384↵
policy hash table linear read/write: 0.216669↵
↵
unordered map random insertion: 2.98216↵
policy hash table random insertion: 3.13651↵
↵
unordered map random read/write: 2.12804↵
policy hash table random read/write: 0.356518↵
~~~~~↵
↵
While for linear insertions, the policy hash table gives modest improvements, the policy hash table blows the unordered_map out of the water when it comes to reads/writes. These are order of magnitude improvements that make hash tables usable when they previously weren't.↵
Example↵
------↵
Benchmarks of course, don't always reflect the real world. So here's an example of it allowing a solution to be accepted that TLE's with unordered_map.↵
↵
Example problem (5000 ms time limit): http://codeforces.me/contest/264/problem/C ↵
Solution with unordered_map: http://codeforces.me/contest/264/submission/40542899 (TLE on test case 8) ↵
Solution with policy hash table directly substituted in: http://codeforces.me/contest/264/submission/40573491 (TLE on test case 26) ↵
Solution with unordered_map, rewritten to not use clears:↵
http://codeforces.me/contest/264/submission/40590437 (TLE on test case 26)↵
Solution with policy hash table and rewritten to not use clears: http://codeforces.me/contest/264/submission/40574196 (AC with max time of 3180 ms) ↵
↵
Usage↵
------↵
To use this data structure:↵
↵
~~~~~↵
#include <ext/pb_ds/assoc_container.hpp>↵
using namespace __gnu_pbds;↵
cc_hash_table<int, int> table;↵
~~~~~↵
From there, the API seems almost exactly the same.↵
↵
Thanks to ~adamant,2018-07-20 for his post that revealed to me the existence of policy data structures, and thanks to ~tonynater,2018-07-20 for the discussion.↵
↵
PS: In other posts for unordered_map, I've seen people claim that reserve and max_load_factor could increase performance drastically. They didn't seem to do much for me. However, if you want to do something similar for these hash tables, use `typedef cc_hash_table<↵
int, int, hash<int>, equal_to<int>, direct_mask_range_hashing<int>,↵
hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>>↵
ht;`, and you should be able to resize and set load factor manually as well.↵
↵
↵
↵
↵
Code for the benchmarks can be found here: https://ideone.com/ZkNMbH↵
↵
