Great; thanks for volunteering to answer questions! I'm still reading your paper; please excuse me if this is covered.
There is a technique for eliminating the long pauses from rebuilding called "incremental global rebuilding". The big idea is that the new structure is built piece-by-piece, taking a few building steps for each update to the existing structure. The new construction is finished before the existing structure fills up (or empties out, for deletes). Depending on the variant, updates may be applied as the new structure is being built, batched to be applied later, or applied in a secondary "ghost" structure.
It has been used in dozens of data structures, and was, I think, made famous by a series of papers by Overmars and co-authors in the early 80s. He wrote a book about related techniques called "The Design of Dynamic Data Structures".
Does this technique not apply to resizing hash tables in a concurrent kernel?
A large part of the overhead of concurrent data structures lies not in the work itself, but in the synchronization used to avoid corruption to the data structure. The technique you're describing could potentially allow a resize to occur incrementally, without blocking other operations for a long time, but that doesn't take away the need to synchronize between resize, write, and read operations.
RCU-based algorithms allow readers to proceed with absolutely no locking, compare-and-swap, atomic operations, or other expensive steps. In order to support that, any modification to the data structure (such as a write or resize) must make sure the structure remains in a completely valid state after every individual modification. The hash resize algorithm I wrote provides that feature, ensuring that the resize does not disrupt concurrent readers.
Are you aware of any way that the work of Overmars et al. fails to meet the criterion "any modification to the data structure (such as a write or resize) must make sure the structure remains in a completely valid state after every individual modification"?
There is a technique for eliminating the long pauses from rebuilding called "incremental global rebuilding". The big idea is that the new structure is built piece-by-piece, taking a few building steps for each update to the existing structure. The new construction is finished before the existing structure fills up (or empties out, for deletes). Depending on the variant, updates may be applied as the new structure is being built, batched to be applied later, or applied in a secondary "ghost" structure.
It has been used in dozens of data structures, and was, I think, made famous by a series of papers by Overmars and co-authors in the early 80s. He wrote a book about related techniques called "The Design of Dynamic Data Structures".
Does this technique not apply to resizing hash tables in a concurrent kernel?