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.
OK.
[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).
OK, thank you for the clarification! M.D. _______________________________________________ HelenOS-devel mailing list [email protected] http://lists.modry.cz/cgi-bin/listinfo/helenos-devel
