|Version 3 (modified by 11 years ago) ( diff ),|
Scalable Concurrent Hash Table
- GSoC 2012, ticket #398
- mentor: Jakub Jermar
- student: Adam Hraska
- repository: lp:~adam-hraska+lp/helenos/rcu/
- benchmarking repository: lp:~adam-hraska+lp/helenos/cht-bench/
The goal of the project is to create a scalable concurrent resizable hash table (CHT):
- scalable = performance improves with added cpus
- concurrent = the table allows parallel access from multiple threads/cpus preferably without blocking
- resizable = the table grows and shrinks automatically as item are added or removed from it
Moreover, the table must be suitable to replace the current global page hash table in the kernel. Optionally, it may be ported to user space as well.
The CHT replies on working atomic operations, SMP calls (ie IPIs), RCU and the system work queue. In order to test these out, pull and build the source code (eg on x86-64 machines):
bzr checkout lp:~adam-hraska+lp/helenos/rcu/ make PROFILE=amd64
Boot HelenOS with eg 4 CPUs in QEMU:
qemu-system-x86_64 -cdrom image.iso -smp4
Once fully operational, switch to the kernel console by pressing F12 (or typing kcon in the shell). You can then finally run the following relevant tests:
test atomic1 test smpcall1 test workqueue test rcu1 test cht
Neither of the tests should panic, crash, leak memory, loop infinitely, or report errors. The only test workqueue reports an error which is however expected and marked appropriately with line Stress testing a custom queue. Stops prematurely. Errors are expected.
You may be interested in runtime statistics gathered by RCU or the system work queue. Run these commands in the kernel console:
In order to benchmark the CHT or RCU implementation, pull sources of the benchmarking branch and build the code in a release build (ie clear the debug build option):
bzr checkout lp:~adam-hraska+lp/helenos/cht-bench/ make PROFILE=amd64 make config # this is where you have to clear the debug build option make
Boot HelenOS in QEMU with eq 4 CPUS and list the available benchmarks in the kernel console with the chtbench command:
qemu-system-x86_64 -cdrom image.iso -smp 4 / # kcon kconsole> chtbench 0 0 0
The following results were obtained by benchmarking r1589 on Core™ i7 CPU 920 @ 2.67GHz (4 cores, each with 2 HyperThreads), running a release build (with networking):
contrib/conf/net-qe.sh e1k -smp 4
Each benchmark run consists of repeating a certain operation in a loop for 10 seconds on the specified number of cpus (ie individual threads wired to these cpus). Benchmarks were repeated as many times as needed (between 10 and 20 consecutive runs) in order to obtain a confidence interval of the number of completed operations within about 1% of the average number of completed operations of the runs. The following figures include error bars depicting a single standard deviation of the completed number of operations in a single run (ie it is not the SD of the mean, aka standard error). However the estimated SD is typically below 1-2% of the mean (ie tiny) and therefore not visible in the figures without zooming .
RCU read side scalability
First, we examine the overhead of rcu read sections compared to acquiring a spinlock. The figure above shows the number of traversals of a five element immutable list depending on the number of threads/cpus used. More is better .
- ideal - the list was accessed without any synchronization whatsoever
- a-rcu - each list traversal was protected by A-RCU
- podzimek-rcu - protected by the preemptible modification of Podzimek's RCU
- spinlock - guarded by an ordinary preemption disabling spinlock
A-RCU fares the best and has optimal scaling. On the other side, spinlock presents negative scaling (ie the more cpus you throw at it, the slower it is). Podzimek's RCU scales perfectly but has a greater base cost compared to A-RCU. In particular, Podzimek-RCU's base cost is on par with a spinlock when running on a single cpu while A-RCU's base cost is significantly lower than both Podzimek-RCU's and spinlock base cost.
To reproduce these results, switch to the kernel console and run:
chtbench 2 1 0 -w chtbench 2 2 0 -w chtbench 2 3 0 -w chtbench 2 4 0 -w chtbench 3 1 0 -w chtbench 3 2 0 -w chtbench 3 3 0 -w chtbench 3 4 0 -w chtbench 4 1 0 -w chtbench 4 2 0 -w chtbench 4 3 0 -w chtbench 4 4 0 -w
- r1589-list-read.png (17.4 KB ) - added by 11 years ago.
- r1589-list-upd.png (16.6 KB ) - added by 11 years ago.
- r1589-ht-lookup.png (13.2 KB ) - added by 11 years ago.
- r1589-ht-upd.png (14.2 KB ) - added by 11 years ago.
- r1589-list-upd-trim.png (18.5 KB ) - added by 11 years ago.
Download all attachments as: .zip