Changes

Jump to: navigation, search

User:Jorend/Deterministic hash tables

51 bytes added, 02:59, 24 February 2012
Memory usage
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.125x 0625x or 2.25x 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]]
638
edits

Navigation menu