Hi Martin,
thank you for your interest.
> [..] the list contains the reference [12] which deals
> primarily with a specific RCU implementation and the
> hash table used for benchmarking in [12] is a variant
> of the classical McKenney's concurrent hash table.
I listed both McKenney's HT [11] as well as Podzimek's
reimplementation of it [12] just for convenience to
those who may have glanced over Podzimek's HT but are
unfamiliar with McKenney's work. I wanted them to know
I considered "both" HTs.
> Can you please elaborate on the exact ways why the
> other implementations are inferior?
[11, 12] McKenney's, K42, Podzimek's HT
Do not resize. There does not seem to be an obvious
way to grow the HT since new items are always inserted
at the start of each bucket (so we can't use (F)'s
multipass unzip).
[13] DDDS
DDDS resizes and has zero reader overhead. (F) however
outperforms DDDS (see [8] for benchmarks) because while
resizing all DDDS readers must issue at least 2 MBs and
search both the old and the new buckets irrespective of
whether the searched bucket is being moved/split. What
is more, if a reader is unlucky enough to probe a bucket
while it is being split, the reader has to spin.
[14] Xu's RCU HT
Xu's HT has space overhead as it requires nodes to have
pointers for two linked lists so they can be placed
in the new and the old table/bucket simultaneously. I
have not investigated it further.
[10] Multiple references/HTs
Chapter 13 of the book elaborates on some of the HTs
referenced in section 13.5 of the book (ie [10]).
As a general rule of thumb, assume the HTs referenced
from [10] either require locking for update or do not
resize (or use DCAS).
Moreover, according to its authors (D) of 2006 was
the first lock-free hash table that allowed extension
(see first sentence of [5]'s abstract). Furthermore,
authors of (F) mention (in 2011) only two other RCU
based resizable HTs, namely DDDS [13] (from 2008) and
Xu's HT [14] (from 2010). Because the book [10] is
from 2008 you can safely believe me that the HTs
referenced there do not surpass the HTs mentioned
in my previous email (in their respective domains).
Summary
=======
Unlike [10, 11, 12, 13, 14] (F) resizes, readers never
spin or block and it has moderate/typical/the best
available space overhead.
Adam
References
==========
[14] bridge: Add core IGMP snooping support,
Xu, 2010
http://kerneltrap.org/mailarchive/git-commits-head/2010/3/2/27131
_______________________________________________
HelenOS-devel mailing list
[email protected]
http://lists.modry.cz/cgi-bin/listinfo/helenos-devel
