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

Changes between Version 3 and Version 4 of ConcurrentHashTable


Ignore:
Timestamp:
2012-08-08T11:43:00Z (7 years ago)
Author:
Adam Hraska
Comment:

rcu update overhead benchmark description

Legend:

Unmodified
Added
Removed
Modified
  • ConcurrentHashTable

    v3 v4  
    127127chtbench 4 4 0 -w
    128128}}}
     129Then build with Podzimek-RCU and rerun:
     130{{{
     131chtbench 3 1 0 -w
     132chtbench 3 2 0 -w
     133chtbench 3 3 0 -w
     134chtbench 3 4 0 -w
     135}}}
    129136
     137=== RCU write side overhead ===
    130138[[Image(r1589-list-upd.png)]]
    131139[[Image(r1589-list-upd-trim.png)]]
     140
     141Second, we examine the overhead of rcu writers (ie invoking {{{rcu_call()}}} and processing the callback in the background)
     142compared to acquiring a spinlock. The figure above shows the number of traversals
     143or updates of a five element list with an increasing percentage of updates.
     144The benchmark ran in 4 threads/CPUs. In each iteration a thread selected at random
     145whether to walk the entire list or to replace an item in the list (ie to update the
     146list). All items were preallocated. More is better ;-).
     147- //ideal// - the list was accessed without any synchronization whatsoever on a single cpu;
     148  and the result multiplied by the number of cpus (ie 4)
     149- //a-rcu + spinlock// - each list traversal and update was protected by A-RCU; concurrent updates
     150  were synchronized by means of a spinlock
     151- //podzimek-rcu + spinlock// - same as a-rcu but protected by preemptible version of Podzimek's RCU
     152- //spinlock// - guarded by an ordinary preemption disabling spinlock
     153
     154To reproduce these results, switch to the kernel console and run:
     155{{{
     156chtbench 6 1 0 -w
     157chtbench 7 4 0 -w
     158chtbench 7 4 5 -w
     159chtbench 7 4 10 -w
     160chtbench 7 4 20 -w
     161chtbench 7 4 30 -w
     162chtbench 7 4 40 -w
     163chtbench 7 4 60 -w
     164chtbench 7 4 100 -w
     165chtbench 8 4 0 -w
     166chtbench 8 4 5 -w
     167chtbench 8 4 10 -w
     168chtbench 8 4 20 -w
     169chtbench 8 4 30 -w
     170chtbench 8 4 40 -w
     171chtbench 8 4 60 -w
     172chtbench 8 4 100 -w
     173}}}
     174Then rebuild with Podzimek-RCU and rerun:
     175{{{
     176chtbench 7 4 0 -w
     177chtbench 7 4 5 -w
     178chtbench 7 4 10 -w
     179chtbench 7 4 20 -w
     180chtbench 7 4 30 -w
     181chtbench 7 4 40 -w
     182chtbench 7 4 60 -w
     183chtbench 7 4 100 -w
     184}}}
     185
     186
     187=== Hash table lookup scalability ===
    132188[[Image(r1589-ht-lookup.png)]]
     189
     190=== Hash table update overhead ===
    133191[[Image(r1589-ht-upd.png)]]