Intel Threading Building Blocks

When Not to Use Queues

Queues are widely used in parallel programs to buffer consumers from producers. Before using an explicit queue, however, consider using parallel_while or pipeline instead. These options are often more efficient than queues for the following reasons:

• A queue is inherently a bottleneck because it must maintain first-in first-out order.

• A thread that is popping a value may have to wait idly until the value is pushed.

• A queue is a passive data structure. If a thread pushes an item and another thread pops it, the item must be moved to the other processor. Even if the original thread pops the item, enough time could elapse between the push and the pop for the item (and whatever it references) to be discarded from the cache.

In contrast, parallel_while and pipeline avoid these bottlenecks. Because their threading is implicit, they optimize the use of worker threads so that they do other work until a value shows up. They also try to keep items hot in the cache. For example, when another work item is added to a parallel_while, it is kept local to the thread that added it, unless another idle thread can steal it before the “hot” thread processes it. By applying this selectivity in pulling from another queue, items are more often processed by the hot thread.