Dynamic expansion of folly MPMC queue
Summary:
This diff allows queues to start with small capacity and expand as needed up to the specified capacity.
The main additions and changes:
- Extra template parameter `Dynamic` that enables dynamic expansion (`default 'false').
- `ClosedArray` type.
- Extra members:
-- `dstate_`: a packed 64 bit unsigned int that contains a seqlock (which implicitly indicates the number of expansions and the lowest ticket for the current `dslots_/dcapacity_/dstride_` configuration.
-- `dcapacity_`: current dynamic capacity.
-- `dslots_`: current dynamic slots array. (in anonymous union with `slots_`)
-- `dstride_`: current dynamic stride. (in anonymous union with `stride_`)
-- `closed_` a logarithmic-sized array of ClosedArray to hold information about earlier smaller queue arrays for use by lagging consumers.
Design sketch:
- Reallocate a new larger array on expansion
- Expansion uses a seqlock. The common case critical path includes a seqlock read-only section.
- Lagging consumers and lagging blocking producers use a logarithmic-sized array for info about closed arrays
- Tickets are adjusted by an offset (to accounts for the tickets associated with earlier closed arrays) in order to calculate appropriate index and turn.
- The synching of `pushTicket_` with the ticket offset packed in `dstate_` is tricky. `pushTicket_` is accessed outside `dstate_`'s seqlock.
Reviewed By: djwatson
Differential Revision:
D3462592
fbshipit-source-id:
d442a7694190cca3c33753409ffac941d7463f83