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 <[email protected]> > Reviewed-by: Eli Britstein <[email protected]> > --- > 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 <[email protected]> Thanks, Maxime _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
