638
edits
Changes
→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.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 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.
