The WFQ d-CBO (d-Choice Balanced Operations) queue uses the choice of d to balance enqueue and dequeue counts across several sub-queues, using internal counters to approximate these operation counts. By compiling with HEURISTIC=LENGTH, you instead get the d-CBL, which balances sub-queue lengths instead of operation counts. The MS (Michael-Scott) queue is the most foundational lock-free queue, based on a linked list, using compare-and-swap for synchronization, and is here used as sub-queue.
To from the paper Balanced Allocations over Efficient Queues: A Fast Relaxed FIFO Queue, to be published in PPoPP 2025.
Kåre von Geijer [email protected]