Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changes between Version 5 and Version 6 of ConcurrentHashTable


Ignore:
Timestamp:
2012-08-08T12:37:03Z (7 years ago)
Author:
Adam Hraska
Comment:

ht lookup scalability description

Legend:

Unmodified
Added
Removed
Modified
  • ConcurrentHashTable

    v5 v6  
    198198[[Image(r1589-ht-lookup.png)]]
    199199
     200In this section we compare lookup scalability of CHT with ordinary spinlock guarded hash tables.
     201The test consists of searching for keys in tables with load factor 4 (ie 4 items/bucket on average).
     202Half of all lookups searched for keys not present in the table. Moreover, all items were inserted
     203into the tables before the benchmark started.
     204
     205In the figure above:
     206- //ht/spinlock// - represents the original non-resizible kernel hash table with 127 buckets
     207  and guarded by a single global spinlock.
     208- //ht/bktlock// - same as ht/spinlock but protects each bucket with a separate spinlock.
     209- //cht/a-rcu// - CHT protected by A-RCU, uses 128 buckets.
     210
     211Note that CHT was set up with the resize triggering load factor high enough for CHT to never
     212resize. However, CHT was still tracking the number of items in the table and still checking
     213if it should resize -- quite unlike the spinlock protected tables that are not resizible
     214and therefore do not need to track the number of elements nor check if a resize is in order.
     215
     216What is more, CHT and HTs use different hash functions. While CHT mixes user supplied
     217hashes to produce a good hash, HTs divide user supplied hashes by a prime number and
     218use the remainder as the final hash. This influences both the distribution of items
     219in buckets as well as the time to actually compute a hash. Keys were selected to favor
     220traditional HTs which achieved an optimal item distribution (exactly 4 per each bucket).
     221On the other hand, in CHT buckets contained from 0 to 9 items. Furthermore, the hash
     222mixing function used by CHT in rev1589 appears to be slightly slower (~10% slower) than
     223dividing by a prime.
     224
     225As expected, a HT protected by a single spinlock scales negatively. On the other hand,
     226a HT with one spinlock/bucket scales fairly well but is significantly slower than CHT.
     227CHT performs slightly better than both HTs in the base case of running on a single cpu.
     228
    200229=== Hash table update overhead ===
    201230[[Image(r1589-ht-upd.png)]]
     231
     232
     233
     234=== Final notes ====