How FIFO is your concurrent FIFO queue

Designing and implementing high-performance concurrent data structures whose access performance scales on mul-ticore hardware is difficult. Concurrent implementations of FIFO queues, for example, seem to require algorithms that efficiently increase the potential for parallel access by imple-menting semantically relaxed rather than strict FIFO queues where elements may be returned in some out-of-order fash-ion. However, we show experimentally that the on average shorter execution time of enqueue and dequeue operations of fast but relaxed implementations may offset the effect of semantical relaxations making them appear as behaving more FIFO than strict but slow implementations. Our key assumption is that ideal concurrent data structure operations should execute in zero time. We define two metrics, element-fairness and operation-fairness, to measure the degree of ele-ment and operation reordering, respectively, assuming oper-ations take zero time. Element-fairness quantifies the devia-tion from FIFO queue semantics had all operations executed in zero time. With this metric even strict implementations of FIFO queues are not FIFO. Operation-fairness helps ex-plaining element-fairness by quantifying operation reorder-ing when considering the actual time operations took effect relative to their invocation time. In our experiments, the ef-fect of poor operation-fairness of strict but slow implemen-tations on element-fairness may outweigh the effect of se-mantical relaxation of fast but relaxed implementations