C++ STL: Faster unordered_map with Policy Based Data Structures

Revision en1, by Chilli, 2018-07-20 23:01:11

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. Only downside is that clear is slower on a Policy Hash Table with random insertion order.

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://mirror.codeforces.com/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.

Well, enough backstory, let's look at some numbers.

unordered map linear insertion:                                 0.743023
policy hash table linear insertion:                             0.465051

unordered map linear read/write:                                0.205146
policy hash table linear read/write:                            0.034896

unordered map random insertion:                                 3.08992
policy hash table random insertion:                             3.0686

unordered map random read/write:                                0.225844
policy hash table random read/write:                            0.051624
Tags hashtable, c++, policy based, unordered_map

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en25 English Chilli 2020-04-08 21:39:21 204
en24 English Chilli 2018-12-20 19:59:40 19
en23 English Chilli 2018-08-26 22:29:49 97
en22 English Chilli 2018-07-23 11:48:12 5
en21 English Chilli 2018-07-23 11:26:11 64
en20 English Chilli 2018-07-23 11:23:29 657
en19 English Chilli 2018-07-23 10:23:47 198 Tiny change: ' clears:]( http://cod' -> ' clears:](http://cod'
en18 English Chilli 2018-07-23 09:17:15 390
en17 English Chilli 2018-07-21 23:50:59 504
en16 English Chilli 2018-07-21 05:33:02 10
en15 English Chilli 2018-07-21 05:31:38 4
en14 English Chilli 2018-07-21 05:20:37 2
en13 English Chilli 2018-07-21 05:18:56 5
en12 English Chilli 2018-07-21 04:59:02 842
en11 English Chilli 2018-07-21 01:50:28 0 (published)
en10 English Chilli 2018-07-21 01:08:04 136
en9 English Chilli 2018-07-21 01:04:50 45
en8 English Chilli 2018-07-21 00:42:45 21
en7 English Chilli 2018-07-21 00:41:07 99
en6 English Chilli 2018-07-21 00:40:10 24
en5 English Chilli 2018-07-21 00:37:56 25
en4 English Chilli 2018-07-20 23:34:11 41
en3 English Chilli 2018-07-20 23:21:31 2598 Tiny change: 'n\n\n~~~~~\n\nunordered ' -> 'n\n\n~~~~~unordered '
en2 English Chilli 2018-07-20 23:01:35 4
en1 English Chilli 2018-07-20 23:01:11 1442 Initial revision (saved to drafts)