MozillaWiki

User:Jorend/Deterministic hash tables: Difference between revisions

User page Discussion

User:Jorend/Deterministic hash tables (view source)

Revision as of 21:12, 27 February 2012

4,521 bytes added ,  27 February 2012
→‎Theory
 
(10 intermediate revisions by the same user not shown)
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 &lt; f &le; 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 &lt; u &le; 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&times;''NE'', and a <code>CloseTable</code> about 2.13&times;''NE'' (2.25&times;''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 83: Line 132:
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.
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 large enough number of entries ''N'', 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>.
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.
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.
Line 112: 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.
Jorend
638

edits

Retrieved from "https://wiki.mozilla.org/Special:MobileDiff/401091...401470"