638
edits
User:Jorend/Deterministic hash tables: Difference between revisions
Jump to navigation
Jump to search
User:Jorend/Deterministic hash tables (view source)
Revision as of 02:59, 24 February 2012
, 24 February 2012→Memory usage
| Line 83: | Line 83: | ||
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. | 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. This is because CloseTable entries are 50% larger, and it therefore takes fewer of them to fill up a power-of-two-sized allocation. | ||
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]] | ||