Hi guys, This week I have been working on the following:
1) I implemented the initial version of the concurrent hash table (CHT) [1,2]. It grows and shrinks. Lookups never block nor spin. Updates (ie insert(), remove()) are lock-free [6] (as in "the system always makes progress as a whole"; not just "uses no locks") even during resize. 2) Added a sanity checking test and a stress test of the CHT [3]. 3) Implemeted rcu_barrier() - it waits for outstanding rcu callbacks to complete. 4) I added some hash related utility functions, ie hash mixing as well as hash combining functions in kernel/include /adt/hash.h [4]. In my spare time, I: 5) Decreased the podzimek-rcu read side overhead (now 40-50% faster). 6) Implemented my own preemptible kernel rcu (thoughtfully refered to as a-rcu). It has a about 3x faster read side than the tuned preemptible podzimek-rcu in helenos. 7) Started my own little rcu/cht benchmarking branch. If you pull [5], you can run "chtbench 0 0 0" in the kernel console to see what benchmarks are available. Eg to see the performance difference between accessing an rcu protected list and a spinlock protected list, run "chtbench 3 4 0" and then "chtbench 4 4 0" on a 4 cpu machine. CHT details ----------- The CHT should scale very well (ie "run faster with additional cpus", not "resize"). However, it remains to be seen what the base cost of running the table on one cpu is. CHT has lock-free updates which is a very nice property. It implies that a thread may be preempted at any point even in the middle of updating the table and it will not block other threads trying to access/change the table. This property might be useful in user space. Currently if a user space thread is preempted while accessing a table and it holds a lock to the table, other threads trying to access the table would have to wait till the preempted thread gets another time slice and unlocks the table. With the lock-free CHT, these other threads would not have to wait. In fact they would not even notice the thread was preempted. CHT, obviously, needs more documentation. On the down side, CHT has a fairly high resize latency. It takes on the order of 10s of milliseconds for the table to expand independent of its size and benefit from the new doubled-size. As a result, if one starts with a small table (eg 128 buckets), it is rather easy to stuff 10 000s of items into it before the table resizes to 256 buckets. I have yet to see if this constitutes a real problem. On the up side, it takes on the order of 10s of milliseconds for the table to expand (more-or-less) independent of its size :-). Therefore, going from eg 2^19 to 2^20 buckets takes about the same as going from 128 to 256 buckets. Good night. Adam [1] http://bazaar.launchpad.net/~adam-hraska+lp/helenos/rcu/revision/1572 [2] http://bazaar.launchpad.net/~adam-hraska+lp/helenos/rcu/revision/1574 [3] http://bazaar.launchpad.net/~adam-hraska+lp/helenos/rcu/revision/1573 [4] http://bazaar.launchpad.net/~adam-hraska+lp/helenos/rcu/revision/1568 [5] http://bazaar.launchpad.net/~adam-hraska+lp/helenos/cht-bench/changes [6] http://en.wikipedia.org/wiki/Lock-free#Lock-freedom _______________________________________________ HelenOS-devel mailing list [email protected] http://lists.modry.cz/cgi-bin/listinfo/helenos-devel
