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 18:30, 24 February 2012
, 24 February 2012→Deletion speed
(→Method) |
|||
| Line 124: | Line 124: | ||
This test creates a table with 700 entries, then measures the speed of alternately adding an entry and deleting the oldest remaining entry from the table. Entries are therefore removed in FIFO order. Each “operation” here includes both an insert and a delete. | This test creates a table with 700 entries, then measures the speed of alternately adding an entry and deleting the oldest remaining entry from the table. Entries are therefore removed in FIFO order. Each “operation” here includes both an insert and a delete. | ||
The CloseTable stores the entries in insertion order, so this test gets extremely good memory locality. The effect is even more pronounced in a 32-bit build. | |||
[[Image:jorendorff-dht-DeleteTest-speed.png]] | [[Image:jorendorff-dht-DeleteTest-speed.png]] | ||
| Line 131: | Line 133: | ||
The numbers for dense_hash_map are jagged because <code>DenseMap</code> shrinks the table at certain threshold sizes as entries are deleted, and shrinking the table is expensive. | The numbers for dense_hash_map are jagged because <code>DenseMap</code> shrinks the table at certain threshold sizes as entries are deleted, and shrinking the table is expensive. | ||
The apparent randomness of the OpenTable and CloseTable numbers is unexplained. | The apparent randomness of the OpenTable and CloseTable numbers is reproducible and unexplained. | ||
[[Image:jorendorff-dht-LookupAfterDeleteTest-speed.png]] | [[Image:jorendorff-dht-LookupAfterDeleteTest-speed.png]] | ||
This test measures the performance of lookups, mostly misses, in a table that was filled to size 50000, then reduced to size 195 by deleting most of the entries. | This test measures the performance of lookups, mostly misses, in a table that was filled to size 50000, then reduced to size 195 by deleting most of the entries. | ||