Changes between Version 5 and Version 6 of ConcurrentHashTable

Timestamp:

2012-08-08T12:37:03Z (13 years ago)

Author:

Adam Hraska

Comment:

ht lookup scalability description

ConcurrentHashTable

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