[ovs-dev] [PATCH v2 10/28] mpsc-queue: Module for lock-free message passing

[Maxime Coquelin]

Hi Gaetan,

On 4/12/21 5:19 PM, Gaetan Rivet wrote:
> Add a lockless multi-producer/single-consumer (MPSC), linked-list based,
> intrusive, unbounded queue that does not require deferred memory
> management.
> 
> The queue is an implementation of the structure described by Dmitri
> Vyukov[1]. It adds a slightly more explicit API explaining the proper use
> of the queue.
> Alternatives were considered such as a Treiber Stack [2] or a
> Michael-Scott queue [3], but this one is faster, simpler and scalable.
> 
> [1]: http://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue
> 
> [2]: R. K. Treiber. Systems programming: Coping with parallelism.
>      Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
> 
> [3]: M. M. Michael, Simple, Fast, and Practical Non-Blocking and Blocking
>      Concurrent Queue Algorithms.
>      https://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html
> 
> The queue is designed to improve the specific MPSC setup.  A benchmark
> accompanies the unit tests to measure the difference in this configuration.
> A single reader thread polls the queue while N writers enqueue elements
> as fast as possible.  The mpsc-queue is compared against the regular ovs-list
> as well as the guarded list.  The latter usually offers a slight improvement
> by batching the element removal, however the mpsc-queue is faster.
> 
> The average is of each producer threads time:
> 
>    $ ./tests/ovstest test-mpsc-queue benchmark 3000000 1
>    Benchmarking n=3000000 on 1 + 1 threads.
>     type\thread:  Reader      1    Avg
>      mpsc-queue:     161    161    161 ms
>            list:     803    803    803 ms
>    guarded list:     665    665    665 ms
> 
>    $ ./tests/ovstest test-mpsc-queue benchmark 3000000 2
>    Benchmarking n=3000000 on 1 + 2 threads.
>     type\thread:  Reader      1      2    Avg
>      mpsc-queue:     102    101     97     99 ms
>            list:     246    212    246    229 ms
>    guarded list:     264    263    214    238 ms
> 
>    $ ./tests/ovstest test-mpsc-queue benchmark 3000000 3
>    Benchmarking n=3000000 on 1 + 3 threads.
>     type\thread:  Reader      1      2      3    Avg
>      mpsc-queue:      92     91     92     91     91 ms
>            list:     520    517    515    520    517 ms
>    guarded list:     405    395    401    404    400 ms
> 
>    $ ./tests/ovstest test-mpsc-queue benchmark 3000000 4
>    Benchmarking n=3000000 on 1 + 4 threads.
>     type\thread:  Reader      1      2      3      4    Avg
>      mpsc-queue:      77     73     73     77     75     74 ms
>            list:     371    359    361    287    370    344 ms
>    guarded list:     389    388    359    363    357    366 ms
> 
> Signed-off-by: Gaetan Rivet <grive at u256.net>
> Reviewed-by: Eli Britstein <elibr at nvidia.com>
> ---
>  lib/automake.mk         |   2 +
>  lib/mpsc-queue.c        | 251 ++++++++++++++
>  lib/mpsc-queue.h        | 189 +++++++++++
>  tests/automake.mk       |   1 +
>  tests/library.at        |   5 +
>  tests/test-mpsc-queue.c | 727 ++++++++++++++++++++++++++++++++++++++++
>  6 files changed, 1175 insertions(+)
>  create mode 100644 lib/mpsc-queue.c
>  create mode 100644 lib/mpsc-queue.h
>  create mode 100644 tests/test-mpsc-queue.c

Nice and well documented implementation!

Reviewed-by: Maxime Coquelin <maxime.coquelin at redhat.com>

Thanks,
Maxime