638
edits
Changes
→Results
[[Image:jorendorff-dht-figure-1.png]]
CloseTable is more memory-efficient than DenseTable, because the latter is really wasteful of memory.
[[Image:jorendorff-dht-figure-2.png]]
DenseTable and OpenTable must initialize the entire table each time they resize. CloseTable also allocates large chunks of memory, but like a <code>vector</code>, it does not need to write to that memory until there is data that needs to be stored there.
[[Image:jorendorff-dht-InsertSmallTest-speed.png]]
This measures the time required to fill a table to about 100 entries, repeatedly.
[[Image:jorendorff-dht-InsertLargeTest-speed.png]]
This test measures the time required to fill a single gigantic table.
The jagged shape of this graph is robust. It reflects the fact that the table doubles in size as it grows, and rehashing is a significant part of the expense of populating a huge table.
[[Image:jorendorff-dht-LookupHitTest-speed.png]]
[[Image:jorendorff-dht-LookupMissTest-speed.png]]
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.
DenseTable is only slightly slower for misses, perhaps because more lookups have zero collisions. (?)
