Dynamic expansion of folly MPMC queue
authorMaged Michael <magedmichael@fb.com>
Thu, 8 Sep 2016 17:43:23 +0000 (10:43 -0700)
committerFacebook Github Bot 4 <facebook-github-bot-4-bot@fb.com>
Thu, 8 Sep 2016 17:53:27 +0000 (10:53 -0700)
commit59ea1768a8dd7c4064bf1bf2d4c3fe92b7c6386d
tree64e58e1aeddc7d3a3ae529cf6532b235c4910387
parent1cd90b1d14daac0ab0d48eda5677ba97998de99b
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
folly/MPMCQueue.h
folly/detail/MPMCPipelineDetail.h
folly/test/MPMCQueueTest.cpp