Mar 31, 2021 (data collected Aug 9, 2019)

Concurrent Queue Evaluation

Executive Summary

Initially, BDE supplied two concurrent queue implementations: bdlcc::FixedQueue and bdlcc::Queue. As the name implies, bdlcc::FixedQueue has a fixed sized (specified at construction). bdlcc::Queue grows as needed. Both implementations support multiple producers and multiple consumers. By adding constraints upon the number of producers and consumers, and applying lessons learned since the creation of the initial two queues, queues with a cleaner interface and better performance - as measured by a simple micro-benchmark - were created (note that “bounded” is a synonym for “fixed” with regard to the queue’s capacity):

• bdlcc::SingleProducerQueue,

• bdlcc::SingleConsumerQueue,

• bdlcc::SingleProducerSingleConsumerBoundedQueue, and

• bdlcc::BoundedQueue.

While a micro-benchmark is never as good an evaluation as a test using production code with real data, the micro-benchmark does demonstrate there exists a usage scenario where these new queue implementations outperform the old implementations. As such, these new queues are valuable additions to the BDE libraries. Furthermore, using the most constrained of the new queues applicable to your problem (e.g., using bdlcc::SingleProducerQueue for a problem with one producer that must never be blocked) is always recommended (if you find a usage scenario where the appropriate new queue significantly underperforms another queue, please contact BDE).

Benchmark

The results presented are based upon throughput measurements, as per bslmt::ThroughputBenchmark, for a simple micro-benchmark where there are a specified number of producer threads that push an element and then perform a specified amount of busy-waiting, and a specified number of consumer threads that pop an element and then perform a specified amount of busy-waiting. Each reported result is the median result of 101 trials of the micro-benchmark, with each trial having a ten millisecond execution time. The parameters of a scenario are:

Abbreviation	Description	Values
PUSH BUSY	number of (arbitrary) work units a producer performs after a push	20, 100, 500, 1000, 5000
POP BUSY	number of (arbitrary) work units a consumer performs after a pop	20, 100, 500, 1000, 5000
#PUSH	number of producer threads	1, 2, 4, 8, 16
#POP	number of consumer threads	1, 2, 4, 8, 16
INIT CAP	queue initial capacity	64, 512, 4096
OS	platform	LINUX, WIN

The values for PUSH BUSY and POP BUSY are measured in an arbitrary unit of work, where each unit of work consists of one 64-bit integer multiplication and a modulus.

Selecting a Result Table

A table is presented to guide the selection of an implementation in a specific situation. The most common situations are formed by the cross product of three constraints: single or multiple producer threads, single or multiple consumer threads, and whether the queue’s size is unbounded, bounded, or either.

In general, with regard to single versus multiple threads, selecting the most constrained queue (e.g., single over multiple producer threads) will result in better performance. However, the constraint must then be met by the usage of the queue. For instance, to use a single producer queue, at most one thread may be using the queue at any given time (e.g., there is only one thread that will use the push methods).

Frequently there are constraints on the size of the queue. For instance, the queue must be unbounded to ensure push operations never block. Or, the queue has a maximum amount of memory that may be used and must therefore be a bounded implementation. Unfortunately, the relative performance of bounded versus unbounded queues can be complicated so choosing a queue in the absence of a constraint may be difficult; the result tables where the queue size is “either” will hopefully help.

Result Table Format

The result tables are information dense and hence provide succinct support for the recommendation of a particular implementation.

A table is comprised of two sections. The title section has three lines: what is being presented, the row and column parameters, and the data filters. The results section is a grid of scenario outcomes represented as a color-coded numeric value.

The first title line details what is being presented, and is always “% Throughput rel. Best”. The presented numeric results are the throughput percentage of the indicate algorithm relative to the best performing implementation. The implementation abbreviations used:

Abbreviation	Implementation
F	bdlcc::FixedQueue
Q	bdlcc::Queue
SP	bdlcc::SingleProducerQueue
SC	bdlcc::SingleConsumerQueue
SPSCB	bdlcc::SingleProducerSingleConsumerBoundedQueue
B	bdlcc::BoundedQueue

The second title line is formatted as “Row Parameter vs. Column Parameter”. For instance, “PUSH BUSY vs. POP BUSY” indicates the row header values are the PUSH BUSY parameter values, and the column header values are the POP BUSY parameter values. The third title line shows the filters for the presented data. For instance, “INIT CAP=64, OS=LINUX” indicates the results were for scenarios where the queue had an initial capacity of 64 elements, and the platform was Linux.

Note that, typically, a number of parameters are not defined within the second and third title lines. The value used for each implementation within a cell is the best result across the unrestricted parameters. For instance, if the title lines are “% Throughput rel. Best”, “PUSH BUSY vs. POP BUSY”, and “INIT CAP=64, OS=LINUX”, the result used for each algorithm in each cell is the one with highest throughput of all scenarios for #PUSH and #POP, divided by the result for the best value and multiplied by 100.

Finally, the result cells are color-coded to indicate the best performing implementation.

Sample Result Table Interpretation

The following table shows the percent throughput relative the best implementation of three queue implementations on the Linux platform for queues having an initial capacity of 64 elements. The three implementations are bdlcc::FixedQueue, bdlcc::BoundedQueue, and bdlcc::Queue. For the PUSH BUSY value 20 (20 units of work are done after each push) and the POP BUSY value 100 (100 units of work are done after each pop), bdlcc::BoundedQueue was the most performant (as indicated by the 100%), the throughput of bdlcc::FixedQueue was 80% that of bdlcc::BoundedQueue, and the throughput of bdlcc::Queue was 50% that of bdlcc::BoundedQueue. This cell is colored to indicate bdlcc::BoundedQueue was the most performant.

% Throughput rel. Best PUSH BUSY vs. POP BUSY INIT CAP=64, OS=LINUX 100 20 B 100 F 80 Q 50

Multi-Producer, Multi-Consumer, Unbounded

Currently, the only available container for this set of constraints is bdlcc::Queue. As such, the result table is boring.

% Throughput rel. Best PUSH BUSY vs. POP BUSY OS=LINUX 20 100 500 1000 5000 20 Q 100 Q 100 Q 100 Q 100 Q 100 100 Q 100 Q 100 Q 100 Q 100 Q 100 500 Q 100 Q 100 Q 100 Q 100 Q 100 1000 Q 100 Q 100 Q 100 Q 100 Q 100 5000 Q 100 Q 100 Q 100 Q 100 Q 100

% Throughput rel. Best PUSH BUSY vs. POP BUSY OS=WIN 20 100 500 1000 5000 20 Q 100 Q 100 Q 100 Q 100 Q 100 100 Q 100 Q 100 Q 100 Q 100 Q 100 500 Q 100 Q 100 Q 100 Q 100 Q 100 1000 Q 100 Q 100 Q 100 Q 100 Q 100 5000 Q 100 Q 100 Q 100 Q 100 Q 100

Legend Q

Multi-Producer, Multi-Consumer, Bounded

The containers available for this set of constraints are bdlcc::FixedQueue and bdlcc::BoundedQueue. bdlcc::BoundedQueue generally outperforms bdlcc::FixedQueue.

% Throughput rel. Best PUSH BUSY vs. POP BUSY OS=LINUX 20 100 500 1000 5000 20 B 100 F 73 B 100 F 65 B 100 F 91 B 100 F 75 B 100 F 99 100 B 100 F 59 B 100 F 61 B 100 F 70 B 100 F 71 B 100 F 98 500 B 100 F 55 B 100 F 54 B 100 F 63 B 100 F 66 B 100 F 97 1000 B 100 F 60 B 100 F 64 B 100 F 66 B 100 F 66 B 100 F 99 5000 F 100 B 93 F 100 B 93 B 100 F 96 B 100 F 90 F 100 B 99

% Throughput rel. Best PUSH BUSY vs. POP BUSY OS=WIN 20 100 500 1000 5000 20 B 100 F 98 F 100 B 90 F 100 B 97 F 100 B 95 B 100 F 99 100 B 100 F 88 F 100 B 93 F 100 B 86 B 100 F 71 B 100 F 99 500 B 100 F 75 B 100 F 63 B 100 F 98 B 100 F 89 B 100 F 99 1000 B 100 F 70 B 100 F 70 B 100 F 68 B 100 F 76 B 100 F 98 5000 B 100 F 97 B 100 F 96 B 100 F 95 B 100 F 93 B 100 F 99

Legend B F

Multi-Producer, Multi-Consumer, Either

The containers available for this set of constraints are bdlcc::Queue, bdlcc::FixedQueue, and bdlcc::BoundedQueue. bdlcc::BoundedQueue generally outperforms the other implementations.

% Throughput rel. Best PUSH BUSY vs. POP BUSY OS=LINUX 20 100 500 1000 5000 20 B 100 F 73 Q 26 B 100 F 65 Q 34 B 100 F 91 Q 42 B 100 F 75 Q 39 B 100 F 99 Q 98 100 B 100 F 59 Q 22 B 100 F 61 Q 23 B 100 F 70 Q 33 B 100 F 71 Q 35 B 100 F 98 Q 98 500 B 100 F 55 Q 18 B 100 F 54 Q 27 B 100 F 63 Q 31 B 100 F 66 Q 31 B 100 F 97 Q 92 1000 B 100 F 60 Q 24 B 100 F 64 Q 24 B 100 F 66 Q 33 B 100 F 66 Q 43 B 100 F 99 Q 80 5000 F 100 B 93 Q 48 F 100 B 93 Q 47 B 100 F 96 Q 47 B 100 F 90 Q 44 F 100 B 99 Q 79

% Throughput rel. Best PUSH BUSY vs. POP BUSY OS=WIN 20 100 500 1000 5000 20 B 100 F 98 Q 54 F 100 B 90 Q 50 F 100 B 97 Q 85 F 100 B 95 Q 60 Q 100 B 99 F 99 100 B 100 F 88 Q 50 F 100 B 93 Q 44 F 100 B 86 Q 61 B 100 Q 75 F 71 Q 100 B 99 F 99 500 B 100 Q 77 F 75 B 100 Q 74 F 63 B 100 F 98 Q 73 B 100 F 89 Q 86 B 100 F 99 Q 98 1000 B 100 Q 73 F 70 B 100 F 70 Q 69 B 100 F 68 Q 68 B 100 Q 77 F 76 B 100 Q 98 F 98 5000 B 100 F 97 Q 82 B 100 F 96 Q 82 B 100 F 95 Q 81 B 100 F 93 Q 79 B 100 F 99 Q 96

Legend B F Q

Single-Producer, Multi-Consumer, Unbounded

The containers available for this set of constraints are bdlcc::Queue and bdlcc::SingleProducerQueue. bdlcc::SingleProducerQueue either outperforms bdlcc::Queue or is a very close competitor (i.e., losing by only 1% of throughput).

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, OS=LINUX 20 100 500 1000 5000 20 SP 100 Q 44 SP 100 Q 46 SP 100 Q 33 SP 100 Q 16 SP 100 Q 15 100 SP 100 Q 71 SP 100 Q 60 SP 100 Q 44 SP 100 Q 66 SP 100 Q 65 500 SP 100 Q 93 SP 100 Q 92 SP 100 Q 90 SP 100 Q 83 SP 100 Q 96 1000 Q 100 SP 99 Q 100 SP 99 SP 100 Q 98 SP 100 Q 97 SP 100 Q 98 5000 Q 100 SP 99 Q 100 SP 99 Q 100 SP 99 Q 100 SP 99 SP 100 Q 99

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, OS=WIN 20 100 500 1000 5000 20 SP 100 Q 70 SP 100 Q 60 SP 100 Q 61 SP 100 Q 44 SP 100 Q 21 100 Q 100 SP 80 Q 100 SP 95 SP 100 Q 93 SP 100 Q 96 SP 100 Q 67 500 Q 100 SP 98 SP 100 Q 94 SP 100 Q 99 Q 100 SP 94 SP 100 Q 99 1000 Q 100 SP 99 Q 100 SP 99 Q 100 SP 99 SP 100 Q 99 Q 100 SP 99 5000 Q 100 SP 99 Q 100 SP 99 Q 100 SP 99 Q 100 SP 99 Q 100 SP 99

Legend Q SP

Single-Producer, Multi-Consumer, Bounded

The containers available for this set of constraints are bdlcc::FixedQueue and bdlcc::BoundedQueue. The results indicate that bdlcc::FixedQueue outperforms bdlcc::BoundedQueue or is a close competitor. Arguably, what the results really show is the need for a special implementation for this constraint set.

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, OS=LINUX 20 100 500 1000 5000 20 F 100 B 66 F 100 B 77 F 100 B 59 F 100 B 97 B 100 F 99 100 F 100 B 76 F 100 B 86 B 100 F 65 F 100 B 98 B 100 F 98 500 F 100 B 93 F 100 B 94 F 100 B 92 F 100 B 96 F 100 B 99 1000 F 100 B 99 F 100 B 98 F 100 B 98 B 100 F 98 B 100 F 99 5000 F 100 B 99 F 100 B 99 F 100 B 99 F 100 B 99 B 100 F 99

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, OS=WIN 20 100 500 1000 5000 20 F 100 B 59 F 100 B 82 F 100 B 97 F 100 B 88 B 100 F 99 100 B 100 F 86 B 100 F 83 B 100 F 91 B 100 F 99 B 100 F 99 500 B 100 F 97 B 100 F 97 B 100 F 98 F 100 B 97 B 100 F 99 1000 B 100 F 99 B 100 F 99 B 100 F 99 F 100 B 99 B 100 F 99 5000 B 100 F 99 B 100 F 99 B 100 F 99 B 100 F 99 B 100 F 99

Legend B F

Single-Producer, Multi-Consumer, Either

The containers available for this set of constraints are bdlcc::Queue, bdlcc::SingleProducerQueue, bdlcc::FixedQueue and bdlcc::BoundedQueue. bdlcc::SingleProducerQueue is generally the best choice at the moment. Hopefully, a single-producer, multi-consumer, bounded implementation will simplify the results in the future.

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, OS=LINUX 20 100 500 1000 5000 20 F 100 SP 81 B 66 SP 100 F 89 B 69 SP 100 F 73 B 43 SP 100 F 36 B 35 SP 100 B 16 F 15 100 F 100 SP 89 B 76 F 100 SP 90 B 86 SP 100 B 91 F 60 SP 100 F 72 B 71 SP 100 B 66 F 65 500 F 100 SP 95 B 93 F 100 SP 95 B 94 F 100 SP 94 B 92 SP 100 F 95 B 91 SP 100 F 99 B 98 1000 F 100 Q 99 SP 99 F 100 Q 99 B 98 F 100 SP 98 B 98 B 100 SP 99 F 98 SP 100 B 99 F 99 5000 F 100 Q 99 B 99 F 100 Q 99 SP 99 F 100 Q 99 B 99 F 100 Q 99 B 99 B 100 SP 99 F 99

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, OS=WIN 20 100 500 1000 5000 20 SP 100 F 95 Q 70 SP 100 F 77 B 63 SP 100 F 72 B 70 SP 100 F 79 B 70 SP 100 Q 21 B 21 100 Q 100 SP 80 B 68 Q 100 SP 95 B 84 SP 100 Q 93 B 90 SP 100 Q 96 B 92 SP 100 Q 67 B 67 500 Q 100 SP 98 B 97 SP 100 Q 94 B 92 SP 100 Q 99 B 97 Q 100 SP 94 F 90 SP 100 Q 99 B 99 1000 Q 100 SP 99 B 98 Q 100 SP 99 B 99 Q 100 SP 99 B 99 SP 100 Q 99 F 98 Q 100 SP 99 B 99 5000 Q 100 SP 99 B 99 Q 100 SP 99 B 99 Q 100 SP 99 B 99 Q 100 SP 99 B 99 Q 100 SP 99 B 99

Legend B F Q SP

Multi-Producer, Single-Consumer, Unbounded

The containers available for this set of constraints are bdlcc::Queue and bdlcc::SingleConsumerQueue. bdlcc::SingleConsumerQueue generally dominates bdlcc::Queue. Expected improvements to bdlcc::SingleConsumerQueue will hopefully make bdlcc::SingleConsumerQueue the best candidate in all of these scenarios.

% Throughput rel. Best PUSH BUSY vs. POP BUSY #POP=1, OS=LINUX 20 100 500 1000 5000 20 SC 100 Q 50 SC 100 Q 43 SC 100 Q 16 SC 100 Q 7 SC 100 Q 5 100 SC 100 Q 81 SC 100 Q 65 SC 100 Q 36 SC 100 Q 24 SC 100 Q 16 500 SC 100 Q 94 SC 100 Q 87 SC 100 Q 93 SC 100 Q 96 SC 100 Q 74 1000 SC 100 Q 92 SC 100 Q 89 SC 100 Q 98 SC 100 Q 97 SC 100 Q 99 5000 SC 100 Q 98 SC 100 Q 98 SC 100 Q 98 SC 100 Q 99 SC 100 Q 99

% Throughput rel. Best PUSH BUSY vs. POP BUSY #POP=1, OS=WIN 20 100 500 1000 5000 20 Q 100 SC 86 SC 100 Q 50 SC 100 Q 14 SC 100 Q 9 SC 100 Q 5 100 Q 100 SC 88 Q 100 SC 95 SC 100 Q 40 SC 100 Q 27 SC 100 Q 16 500 Q 100 SC 97 Q 100 SC 97 SC 100 Q 99 SC 100 Q 96 SC 100 Q 66 1000 Q 100 SC 97 Q 100 SC 97 Q 100 SC 97 Q 100 SC 98 SC 100 Q 93 5000 Q 100 SC 99 Q 100 SC 96 Q 100 SC 99 Q 100 SC 99 Q 100 SC 99

Legend Q SC

Multi-Producer, Single-Consumer, Bounded

The containers available for this set of constraints are bdlcc::FixedQueue and bdlcc::BoundedQueue. The mixed results imply the need for a special implementation for this constraint set.

% Throughput rel. Best PUSH BUSY vs. POP BUSY #POP=1, OS=LINUX 20 100 500 1000 5000 20 F 100 B 50 F 100 B 83 B 100 F 99 F 100 B 99 F 100 B 99 100 F 100 B 78 F 100 B 92 F 100 B 98 F 100 B 99 F 100 B 99 500 B 100 F 98 F 100 B 96 F 100 B 99 F 100 B 99 F 100 B 99 1000 B 100 F 99 B 100 F 97 F 100 B 98 B 100 F 99 B 100 F 99 5000 B 100 F 98 B 100 F 98 B 100 F 98 F 100 B 99 F 100 B 99

% Throughput rel. Best PUSH BUSY vs. POP BUSY #POP=1, OS=WIN 20 100 500 1000 5000 20 F 100 B 65 F 100 B 97 B 100 F 89 B 100 F 94 F 100 B 99 100 F 100 B 86 F 100 B 91 B 100 F 93 B 100 F 95 F 100 B 98 500 B 100 F 92 B 100 F 96 F 100 B 97 F 100 B 94 F 100 B 98 1000 B 100 F 91 B 100 F 92 B 100 F 96 B 100 F 99 B 100 F 99 5000 F 100 B 99 B 100 F 99 F 100 B 98 B 100 F 99 B 100 F 99

Legend B F

Multi-Producer, Single-Consumer, Either

The containers available for this set of constraints are bdlcc::Queue, bdlcc::SingleConsumerQueue, bdlcc::FixedQueue and bdlcc::BoundedQueue. bdlcc::SingleConsumerQueue is generally the best choice at the moment. Hopefully, a multi-producer, single-consumer, bounded implementation will simplify the results in the future.

% Throughput rel. Best PUSH BUSY vs. POP BUSY #POP=1, OS=LINUX 20 100 500 1000 5000 20 F 100 SC 70 B 50 SC 100 F 57 B 47 SC 100 B 16 F 16 SC 100 F 7 B 7 SC 100 F 5 B 5 100 F 100 SC 79 B 78 F 100 B 92 SC 88 SC 100 F 37 B 37 SC 100 F 24 B 24 SC 100 F 16 B 16 500 B 100 F 98 SC 96 F 100 B 96 SC 95 F 100 B 99 SC 99 F 100 SC 99 B 99 SC 100 F 74 B 74 1000 B 100 F 99 SC 98 SC 100 B 97 F 95 F 100 SC 99 B 98 SC 100 B 99 F 99 SC 100 B 99 F 99 5000 B 100 SC 99 F 98 B 100 SC 99 F 98 B 100 SC 99 F 98 F 100 B 99 SC 99 F 100 SC 99 B 99

% Throughput rel. Best PUSH BUSY vs. POP BUSY #POP=1, OS=WIN 20 100 500 1000 5000 20 F 100 Q 80 SC 70 SC 100 Q 50 F 44 SC 100 Q 14 B 14 SC 100 Q 9 B 9 SC 100 F 6 B 5 100 Q 100 F 91 SC 88 F 100 Q 96 SC 92 SC 100 Q 40 B 39 SC 100 Q 27 B 26 SC 100 Q 16 F 16 500 Q 100 SC 97 B 96 Q 100 SC 97 B 95 F 100 B 97 SC 94 F 100 SC 97 B 94 SC 100 F 66 Q 66 1000 Q 100 SC 97 B 97 Q 100 B 98 SC 97 Q 100 B 98 SC 97 Q 100 B 99 F 99 B 100 SC 99 F 99 5000 Q 100 SC 99 F 97 Q 100 B 99 F 98 F 100 Q 98 B 98 Q 100 B 99 SC 99 B 100 F 99 Q 99

Legend B F Q SC

Single-Producer, Single-Consumer, Unbounded

The containers available for this set of constraints are bdlcc::Queue, bdlcc::SingleProducerQueue, and bdlcc::SingleConsumerQueue. bdlcc::SingleProducerQueue is generally the best choice at the moment. Hopefully, a single-producer, single-consumer, unbounded implementation will simplify the results in the future.

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, #POP=1, OS=LINUX 20 100 500 1000 5000 20 SP 100 SC 97 Q 48 SP 100 SC 72 Q 31 SP 100 SC 55 Q 9 SP 100 SC 63 Q 4 SP 100 SC 63 Q 3 100 SP 100 SC 87 Q 71 SP 100 SC 91 Q 60 SP 100 SC 86 Q 31 SP 100 SC 90 Q 21 SP 100 SC 91 Q 15 500 Q 100 SP 98 SC 98 Q 100 SP 98 SC 98 SP 100 SC 99 Q 93 SC 100 SP 99 Q 96 SP 100 SC 99 Q 74 1000 Q 100 SP 99 SC 99 Q 100 SP 99 SC 98 Q 100 SP 99 SC 98 SC 100 SP 99 Q 97 SP 100 SC 99 Q 98 5000 SP 100 Q 99 SC 99 SP 100 Q 99 SC 99 Q 100 SP 99 SC 99 SP 100 Q 99 SC 99 SC 100 SP 99 Q 99

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, #POP=1, OS=WIN 20 100 500 1000 5000 20 SP 100 Q 70 SC 60 SP 100 SC 70 Q 35 SP 100 SC 73 Q 10 SP 100 SC 74 Q 7 SP 100 SC 74 Q 4 100 Q 100 SC 88 SP 87 SP 100 Q 91 SC 87 SP 100 SC 90 Q 36 SP 100 SC 91 Q 25 SP 100 SC 92 Q 15 500 Q 100 SP 97 SC 97 Q 100 SP 98 SC 97 SP 100 Q 93 SC 93 SP 100 SC 95 Q 92 SC 100 SP 99 Q 66 1000 Q 100 SP 98 SC 97 Q 100 SP 98 SC 97 Q 100 SP 98 SC 97 Q 100 SP 99 SC 98 SP 100 SC 97 Q 91 5000 Q 100 SP 99 SC 99 Q 100 SP 97 SC 96 SP 100 Q 97 SC 96 Q 100 SP 99 SC 99 Q 100 SP 99 SC 99

Legend Q SC SP

Single-Producer, Single-Consumer, Bounded

The containers available for this set of constraints are bdlcc::FixedQueue, bdlcc::BoundedQueue, and bdlcc::SingleProducerSingleConsumerBoundedQueue. The results indicate that bdlcc::SingleProducerSingleConsumerBoundedQueue outperforms the other implementations.

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, #POP=1, OS=LINUX 20 100 500 1000 5000 20 SPSCB 100 F 77 B 39 F 100 SPSCB 98 B 83 B 100 SPSCB 99 F 99 SPSCB 100 F 99 B 99 F 100 B 99 SPSCB 99 100 F 100 SPSCB 98 B 78 SPSCB 100 F 88 B 82 F 100 SPSCB 99 B 98 F 100 SPSCB 99 B 99 SPSCB 100 F 99 B 99 500 SPSCB 100 B 98 F 98 SPSCB 100 F 98 B 97 SPSCB 100 F 97 B 96 SPSCB 100 F 97 B 96 SPSCB 100 F 99 B 99 1000 F 100 B 99 SPSCB 98 F 100 SPSCB 99 B 98 F 100 SPSCB 98 B 98 SPSCB 100 B 98 F 98 SPSCB 100 B 99 F 98 5000 F 100 SPSCB 99 B 99 F 100 SPSCB 99 B 99 F 100 B 99 SPSCB 99 F 100 SPSCB 99 B 99 F 100 SPSCB 99 B 99

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, #POP=1, OS=WIN 20 100 500 1000 5000 20 SPSCB 100 F 58 B 38 SPSCB 100 F 92 B 89 SPSCB 100 B 98 F 87 SPSCB 100 B 99 F 93 F 100 B 99 SPSCB 99 100 F 100 SPSCB 97 B 86 SPSCB 100 F 86 B 78 SPSCB 100 B 98 F 92 SPSCB 100 B 97 F 93 SPSCB 100 F 99 B 98 500 SPSCB 100 B 97 F 82 SPSCB 100 B 97 F 86 SPSCB 100 F 96 B 94 SPSCB 100 F 97 B 91 F 100 SPSCB 99 B 98 1000 SPSCB 100 B 99 F 87 B 100 SPSCB 99 F 86 B 100 SPSCB 99 F 90 SPSCB 100 B 98 F 98 SPSCB 100 B 98 F 97 5000 SPSCB 100 F 97 B 97 B 100 F 99 SPSCB 97 SPSCB 100 F 99 B 97 B 100 SPSCB 99 F 99 SPSCB 100 B 99 F 99

Legend B F SPSCB

Single-Producer, Single-Consumer, Either

The containers available for this set of constraints are bdlcc::Queue, bdlcc::SingleProducerQueue, bdlcc::SingleConsumerQueue, bdlcc::FixedQueue, bdlcc::BoundedQueue, and bdlcc::SingleProducerSingleConsumerBoundedQueue. The results indicate that the selection of an implementation is very sensitive to the scenario.

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, #POP=1, OS=LINUX 20 100 500 1000 5000 20 SPSCB 100 F 77 SP 56 SP 100 SC 72 F 41 SP 100 SC 55 B 9 SP 100 SC 63 SPSCB 4 SP 100 SC 63 F 3 100 F 100 SPSCB 98 SP 90 SPSCB 100 F 88 SP 86 SP 100 SC 86 F 32 SP 100 SC 90 F 22 SP 100 SC 91 SPSCB 15 500 Q 100 SPSCB 99 SP 98 Q 100 SPSCB 99 SP 98 SPSCB 100 F 97 B 96 SPSCB 100 F 97 SC 97 SP 100 SC 99 SPSCB 74 1000 F 100 B 99 Q 99 F 100 Q 99 SPSCB 99 Q 100 F 99 SP 99 SPSCB 100 SC 98 B 98 SPSCB 100 SP 99 SC 99 5000 F 100 SPSCB 99 SP 99 F 100 SP 99 Q 99 Q 100 F 99 B 99 F 100 SP 99 SPSCB 99 F 100 SPSCB 99 SC 99

% Throughput rel. Best PUSH BUSY vs. POP BUSY #PUSH=1, #POP=1, OS=WIN 20 100 500 1000 5000 20 SPSCB 100 SP 67 F 58 SP 100 SC 70 Q 35 SP 100 SC 73 SPSCB 10 SP 100 SC 74 Q 7 SP 100 SC 74 F 4 100 Q 100 F 91 SC 88 SPSCB 100 SP 91 F 86 SP 100 SC 90 SPSCB 36 SP 100 SC 91 Q 25 SP 100 SC 92 SPSCB 15 500 Q 100 SPSCB 98 SP 97 Q 100 SP 98 SC 97 SPSCB 100 SP 97 F 96 SPSCB 100 SP 99 F 97 SC 100 SP 99 F 66 1000 Q 100 SPSCB 98 SP 98 Q 100 B 98 SP 98 Q 100 B 98 SPSCB 98 SPSCB 100 Q 98 SP 98 SP 100 SPSCB 99 B 98 5000 SPSCB 100 Q 99 SP 99 Q 100 B 99 F 98 SP 100 SPSCB 99 F 99 Q 100 SP 99 B 99 SPSCB 100 B 99 F 99

Legend B F Q SC SP SPSCB

Conclusion

The selection of a queue should always be based upon benchmarking the specific problem; the results presented here are for an unrelated micro-benchmark. As such, the results presented here should be viewed as a starting point to help with the selection process. bdlcc::BoundedQueue is a general replacement candidate for bdlcc::FixedQueue and is a reasonable selection for most problems when the problems allows for a bounded queue. When the problem is bounded and has a single producer and a single consumer, bdlcc::SingleProducerSingleConsumerBoundedQueue should always be a candidate implementation for the problem. For unbounded problems that can be solved using a single producer, bdlcc::SingleProducerQueue should always be a candidate implementation for the problem. Finally, for unbounded problems when a single producer is not a valid constraint, but a single consumer is a valid constraint, consider bdlcc::SingleConsumerQueue.

Extensive Results

An extensive set of result tables is provided in Extensive Results.