Changes between Version 4 and Version 5 of ConcurrentHashTable

Timestamp:

2012-08-08T12:03:57Z (12 years ago)

Author:

Adam Hraska

Comment:

rcu update overhead benchmark results evaluation

ConcurrentHashTable

@@ -142 +142 @@
 compared to acquiring a spinlock. The figure above shows the number of traversals 
 or updates of a five element list with an increasing percentage of updates. 
-The benchmark ran in 4 threads/CPUs. In each iteration a thread selected at random
+The benchmark ran in 4 threads/CPUs. In each iteration each thread selected at random
 whether to walk the entire list or to replace an item in the list (ie to update the 
-list). All items were preallocated. More is better ;-).
+list). All items were preallocated. More is better ;-). The figure on the right
+details the effects of increasing the update percentage by leaving out the data point for 0% updates.
 - //ideal// - the list was accessed without any synchronization whatsoever on a single cpu;
   and the result multiplied by the number of cpus (ie 4)
 - //a-rcu + spinlock// - each list traversal and update was protected by A-RCU; concurrent updates
-  were synchronized by means of a spinlock
+  were synchronized by means of a spinlock, but removed items were freed via {{{rcu_call()}}}
 - //podzimek-rcu + spinlock// - same as a-rcu but protected by preemptible version of Podzimek's RCU
 - //spinlock// - guarded by an ordinary preemption disabling spinlock
+
+When the update fraction is small, RCU protected list traversals and modifications
+significantly outperform a spinlock guarded list. However, as the percent of updates
+increases the cost of acquiring a spinlock to modify the list quickly begins to dominate.
+In the case of RCU protected lists, updating a list involves not only locking a spinlock
+but also posting and rcu callback. Therefore, protecting an often modified list with a 
+spinlock eventually outperforms RCU guarded lists. The cross over point is around 40%
+and 60% of updates for Podzimek's RCU and A-RCU respectively.  Again A-RCU fare a bit
+better than the preemptible version of Podzimek's RCU.
 
 To reproduce these results, switch to the kernel console and run: