Re: Ottawa and slow hash-table resize

[josh@joshtriplett.org]

On Mon, Feb 23, 2015 at 10:49:04AM -0800, Paul E. McKenney wrote:
> Hello!
> 
> Alexei mentioned that there was some excitement a couple of weeks ago in
> Ottawa, something about the resizing taking forever when there were large
> numbers of concurrent additions.  One approach comes to mind:
> 
> o	Currently, the hash table does not allow additions concurrently
> 	with resize operations.  One way to allow this would be to
> 	have the addition operations add to the new hash table at the
> 	head of the lists.  This would clearly require also updating the
> 	pointers used to control the unzip operation.

In theory, resizes should only take the locks for the buckets they're
currently unzipping, and adds should take those same locks.  Neither one
should take a whole-table lock, other than resize excluding concurrent
resizes.  Is that still insufficient?

> o	Count the number of entries added during the resize operation.
> 	Then, at the end of the resize operation, if enough entries have
> 	been added, do a resize, but by multiple factors of two if
> 	need be.

Yeah, the add/remove statistics used for tracking would need some
special handling to avoid being a table-wide bottleneck.

- Josh Triplett