638
edits
User:Jorend/Deterministic hash tables: Difference between revisions
User:Jorend/Deterministic hash tables (view source)
Revision as of 21:12, 27 February 2012
, 27 February 2012→Theory
(→Theory) |
|||
| (18 intermediate revisions by the same user not shown) | |||
| Line 19: | Line 19: | ||
Can a data structure retain the performance of traditional, arbitrary-order hash tables while also storing the order in which entries were added, so that iteration order is deterministic? | Can a data structure retain the performance of traditional, arbitrary-order hash tables while also storing the order in which entries were added, so that iteration order is deterministic? | ||
Tyler Close has developed a | Tyler Close has developed a deterministic hash table that is structured like this (pseudocode): | ||
struct Entry { | struct Entry { | ||
| Line 35: | Line 35: | ||
Removing an entry simply replaces its <code>key</code> with some sentinel while leaving the <code>chain</code> intact. | Removing an entry simply replaces its <code>key</code> with some sentinel while leaving the <code>chain</code> intact. | ||
== Theory == | |||
'''Memory.''' Every map data structure must store the keys and values. A map with ''N'' entries must use at least ''NE'' memory, where ''E'' is the size of a key-value pair (we assume the data can’t be compressed). | |||
In the following discussion we neglect the effect of deletions, which can cause both kinds of table to have extra memory that isn't in use at a given moment. | |||
An open addressing hash table has additional overhead depending on the fill factor. <code>OpenTable</code> in particular has a maximum fill factor ''F''=3/4. When it becomes more than 3/4 full, it doubles in size, becoming just over 3/8 full. The amount of overhead in an <code>OpenTable</code> is ''(1/f)NE'', where ''f'' is the actual current fill ratio of the table and ''F/2 < f ≤ F''. | |||
A Close table has three sources of overhead: the entire <code>hashTable</code>, the <code>chain</code> pointers in the <code>dataTable</code>, and the unused portion of the <code>dataTable</code>. In <code>CloseTable</code>, the <code>chain</code> pointer causes each entry to require ''(3/2)E'' memory rather than ''E''. The <code>dataTable</code> doubles in size when it becomes completely full, so its size is ''(3/2)(1/u)NE'' where ''u'' is the proportion of the <code>dataTable</code> that is in use and ''1/2 < u ≤ 1''. The <code>hashTable</code> is always 1/16 the size of the <code>dataTable</code> (1/8 on 64-bit platforms), so the total size of both tables is ''(1+1/16)(3/2)(1/u)NE'' (substitute 1/8 on 64-bit platforms). | |||
For back-of-envelope purposes, then, ''f'' may be expected to be about ''3F/4'' (halfway between F/2 and F) and ''u'' about 3/4 on average; plugging these numbers in, we expect an <code>OpenTable</code> to use about (1/(3F/4)) = 1.78×''NE'', and a <code>CloseTable</code> about 2.13×''NE'' (2.25×''NE'' on 64-bit), on average. This would mean that the <code>CloseTable</code> would be 20% larger on average (27% larger on 64-bit). However, see the Results section for a picture of how the two implementations compare in practice. | |||
'''Lookup speed.''' The <code>get</code>, <code>has</code>, <code>set</code>, and <code>delete</code> operations all start with a lookup. We will quantify lookup speed in terms of how many memory locations must be accessed. To simulate locality effects, we treat multiple reads from a single entry, or from the table object, as a single read. | |||
In an open addressing hash table with fill factor ''f'', an unsuccessful lookup performs about ''1/(1-f)'' probes.[https://en.wikipedia.org/wiki/Hash_table#Performance_analysis] In an <code>OpenTable</code>, at worst ''f=F=3/4'' and so an unsuccessful lookup performs 4 probes on average. In the usual case, ''f=3F/4=9/16'', so about 2.3 probes on average. A successful lookup performs half as many probes on average. Before probing the table, the lookup must access the <code>OpenTable</code> struct itself, so the final numbers are as shown in the table: 5 reads, 3.3 reads, etc. | |||
A Close table uses direct chaining. Each lookup must read first the <code>CloseTable</code> object itself, and next the <code>hashTable</code>. Then, for an unsuccessful lookup, the whole chain is walked; the expected length of the chain is simply the number of keys in the table divided by the number of hash buckets. For a <code>CloseTable</code>, this quotient is at most 8/3 and typically 2. A successful lookup would perform about half as many probes, if keys were distributed evenly, but instead they are distributed randomly, making successful lookups slower; by simulation, I found the expected number of probes is 2.3 under full load and 2 under typical load. | |||
<table class="data"> | |||
<tr> | |||
<th></th> | |||
<th colspan=2>Expected cost of unsuccessful lookup (miss)</th> | |||
<th colspan=2>Expected cost of successful lookup (hit)</th> | |||
</tr> | |||
<tr> | |||
<th>Data structure</th> | |||
<th>Maximum load</th> | |||
<th>Typical load</th> | |||
<th>Maximum load</th> | |||
<th>Typical load</th> | |||
</tr> | |||
<tr> | |||
<td><code>OpenTable</code> | |||
<td>5 | |||
<td>3.3 | |||
<td>3 | |||
<td>2.2 | |||
</tr> | |||
<tr> | |||
<td><code>CloseTable</code> | |||
<td>4.7 | |||
<td>4 | |||
<td>4.3 | |||
<td>4 | |||
</tr> | |||
</table> | |||
'''Note:''' This analysis does not explain the lookup speed observed in practice. See the Results section. | |||
= Method = | = Method = | ||
| Line 40: | Line 89: | ||
The code I used to make these pictures is available at: https://github.com/jorendorff/dht | The code I used to make these pictures is available at: https://github.com/jorendorff/dht | ||
The graphs below show data collected on a MacBook Pro, using g++-apple-4.2 and a 64-bit build. The results from running the test on a 32-bit Windows build were basically qualitatively the same. CloseTable performance was even better on Windows, for most tests; however, on LookupHitTest, OpenTable achieved almost equal speed. | |||
The project contains two complete hash map implementations: OpenTable and CloseTable. A third implementation, DenseTable, is a thin wrapper around the <code>dense_hash_map</code> type from [https://code.google.com/p/sparsehash/ Sparsehash]. The three classes have the same API and were all benchmarked using the same templates (in hashbench.cpp). | The project contains two complete hash map implementations: OpenTable and CloseTable. A third implementation, DenseTable, is a thin wrapper around the <code>dense_hash_map</code> type from [https://code.google.com/p/sparsehash/ Sparsehash]. The three classes have the same API and were all benchmarked using the same templates (in hashbench.cpp). | ||
| Line 68: | Line 117: | ||
Benchmark design notes: | Benchmark design notes: | ||
* | * The benchmark is pure C++, rather than a Map/Set implementation embedded in an existing ES implementation, in order to make the results as stable as possible, to avoid biasing the results to a particular ES implementation, to encourage contributors, and to focus on the performance differences in the hash table implementations by eliminating all other performance effects as much as possible. | ||
* The program runs each benchmark many different times in order to produce enough numbers that noise is visually obvious in the resulting graph. (Most of the speed graphs are nice and smooth.) | * The program runs each benchmark many different times in order to produce enough numbers that noise is visually obvious in the resulting graph. (Most of the speed graphs are nice and smooth.) | ||
| Line 81: | Line 130: | ||
All three implementations double the size of the table whenever it gets too full. On a log-log plot, this shows as stair-steps of a constant height. The slope of each staircase is 1, indicating linear growth. | All three implementations double the size of the table whenever it gets too full. On a log-log plot, this shows as stair-steps of a constant height. The slope of each staircase is 1, indicating linear growth. | ||
CloseTable | Both OpenTable and CloseTable are much more memory-efficient than DenseTable, because <code>dense_hash_map</code> is tuned for fast lookups at all costs. | ||
For any ''N'' > 5, a CloseTable with ''N'' entries allocates '''either 1.0625x or 2.125x as much memory''' as an OpenTable with ''N'' entries (1.125x or 2.25x as much memory on 64-bit systems). Both tables double in size at certain thresholds, and the thresholds for CloseTable are lower than those for OpenTable. That is, as a CloseTable is populated, it doubles in size sooner than the corresponding OpenTable. The factors determining this behavior are (1) the fact that CloseTable entries are 50% larger, and it therefore takes fewer of them to fill up a power-of-two-sized allocation; and (2) the value of <code>OpenTable::max_fill_factor()</code>. | |||
It is tempting to reduce this complicated picture to a single number, and write that CloseTables are, for example, 20% larger. Or 30%. But such a number would not be easily justified mathematically: the ratio does not converge as the number of entries increases. | |||
[[Image:jorendorff-dht-figure-2.png]] | [[Image:jorendorff-dht-figure-2.png]] | ||
| Line 108: | Line 161: | ||
[[Image:jorendorff-dht-LookupHitTest-speed.png]] | [[Image:jorendorff-dht-LookupHitTest-speed.png]] | ||
This test measures the speed of <code>table.get(k)</code> operations, where ''k'' is the key of an existing entry in the table. | |||
[[Image:jorendorff-dht-LookupMissTest-speed.png]] | [[Image:jorendorff-dht-LookupMissTest-speed.png]] | ||
This test measures the speed of <code>table.get(k)</code> operations, where the key ''k'' is not found in the table. | |||
In an OpenTable, lookups that miss are slower than lookups that hit ''when there is at least one collision''. This is because we keep probing the hash table until we find an empty entry. | In an OpenTable, lookups that miss are slower than lookups that hit ''when there is at least one collision''. This is because we keep probing the hash table until we find an empty entry. | ||
| Line 120: | Line 177: | ||
This test creates a table with 700 entries, then measures the speed of alternately adding an entry and deleting the oldest remaining entry from the table. Entries are therefore removed in FIFO order. Each “operation” here includes both an insert and a delete. | This test creates a table with 700 entries, then measures the speed of alternately adding an entry and deleting the oldest remaining entry from the table. Entries are therefore removed in FIFO order. Each “operation” here includes both an insert and a delete. | ||
The CloseTable stores the entries in insertion order, so this test gets extremely good memory locality. The effect is even more pronounced in a 32-bit build. | |||
[[Image:jorendorff-dht-DeleteTest-speed.png]] | [[Image:jorendorff-dht-DeleteTest-speed.png]] | ||
| Line 127: | Line 186: | ||
The numbers for dense_hash_map are jagged because <code>DenseMap</code> shrinks the table at certain threshold sizes as entries are deleted, and shrinking the table is expensive. | The numbers for dense_hash_map are jagged because <code>DenseMap</code> shrinks the table at certain threshold sizes as entries are deleted, and shrinking the table is expensive. | ||
The apparent randomness of the OpenTable and CloseTable numbers is unexplained. | The apparent randomness of the OpenTable and CloseTable numbers is reproducible and unexplained. | ||
[[Image:jorendorff-dht-LookupAfterDeleteTest-speed.png]] | [[Image:jorendorff-dht-LookupAfterDeleteTest-speed.png]] | ||
This test measures the performance of lookups, mostly misses, in a table that was filled to size 50000, then reduced to size 195 by deleting most of the entries. | This test measures the performance of lookups, mostly misses, in a table that was filled to size 50000, then reduced to size 195 by deleting most of the entries. | ||
The results here are sensitive to the two sizes, which are totally arbitrary choices. A less arbitrary replacement for this test would be welcome. | |||