Backoff arena for queues

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Backoff arena for queues

Ben Manes
During the development of the concurrent queues, and more narrowly the unbounded variants, was there a consideration of adding a backoff strategy? In particular an arena-based approach modeled after the elimination stack [1].

For a long time I've been meaning to explore the idea of a combining arena as a backoff strategy for producers. I implemented this on top of a mpsc linked queue [2] and observe a 70% gain when contended. The combined addition is a sublist that is appended atomically as one operation instead of many individual ones, which is an optimizations that is usually only available to #addAll(c).

The benchmark [3] was taken on a MacBook Pro i7-4870HQ CPU @ 2.50GHz (4 core). Note that the 8 producer benchmark is unfair for CLQ by using #clear() so that the consumer thread kept up with the producers.

ConcurrentLinkedQueue
  * 1 producer: 26.8 ops/s
  * 2 producers: 17 ops/s
  * 8 producers: 7.9 ops/s
SingleConsumerQueue
  * 1 producer: 37.5 ops/s
  * 2 producers: 19.9 ops/s
  * 8 producers: 14.5 ops/s
SingleConsumerQueue + backoff
  * 1 producer: 39.4 ops/s
  * 2 producers: 34.2 ops/s
  * 8 producers: 24.5 ops/s


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest