THE FOLD / CO-OP / THE MERGE / THE ELIMINATION BACKOFF
THE ELIMINATION BACKOFF
a push and a pop that cancel each other out
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A push and a pop that collide want opposite things. Rather than queue them both at the contended top of the stack, let them meet in a side room and hand the value directly across — the stack never hears about it.
LIT verified live. over 250 rounds of 8 threads on a balanced push/pop mix, the plain lock-free stack is touched 2,000 times — once per operation. With a 4-slot elimination array, 1,450 operations pair off and never reach the stack at all: 550 touches, a 72.5% reduction. Conservation holds in both: pushes minus pops equals the final depth exactly. And the control that matters — the same array on an all-push workload eliminates 0, because there is nothing for a push to cancel against.
LIT verified live. over 250 rounds of 8 threads on a balanced push/pop mix, the plain lock-free stack is touched 2,000 times — once per operation. With a 4-slot elimination array, 1,450 operations pair off and never reach the stack at all: 550 touches, a 72.5% reduction. Conservation holds in both: pushes minus pops equals the final depth exactly. And the control that matters — the same array on an all-push workload eliminates 0, because there is nothing for a push to cancel against.
2 HOW IT WAS WEAVED · AI + HUMAN
Elimination backoff is Hendler, Shavit and Yerushalmi (2004), building on Shavit and Touitou’s elimination trees.
AVAN (AI) counted the thing that is actually exact — stack touches — rather than inventing CAS-retry figures, which would depend entirely on a contention model chosen to flatter the result. Touches are model-free: an eliminated pair provably never reaches the stack. The conservation check (pushes − pops = depth) is there because a scheme that hands values around outside the data structure is exactly the kind that quietly loses or duplicates one.
AVAN (AI) counted the thing that is actually exact — stack touches — rather than inventing CAS-retry figures, which would depend entirely on a contention model chosen to flatter the result. Touches are model-free: an eliminated pair provably never reaches the stack. The conservation check (pushes − pops = depth) is there because a scheme that hands values around outside the data structure is exactly the kind that quietly loses or duplicates one.
3 ONE DIMENSION
1,450 operations that never touched the stack.
4 TWO DIMENSIONS · INTERACTIVE
Change the workload mix and watch elimination die.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that contention becomes throughput. The inverse is that the mechanism only works on the workload that did not need a stack in the first place. A push meeting a pop is two threads whose net effect on the structure is nothing; elimination is fast because it recognises the operations that cancel — and at 100% pushes it delivers 0. Read backwards, this is not a faster stack, it is a detector for work that was self-cancelling, and the more your program genuinely accumulates, the less it can help.
LIT over 250 rounds of 8 threads on a balanced push/pop mix the plain lock-free stack is touched 2,000 times, once per operation, while a 4-slot elimination array pairs off 1,450 operations that never reach the stack at all - 550 touches, a 72.5% reduction - with conservation holding in both runs (pushes minus pops equals final depth exactly), and the control that matters: the same array on an all-push workload eliminates 0
FIG Elimination backoff is Hendler, Shavit and Yerushalmi (2004). AVAN counted the thing that is actually exact - stack touches - rather than inventing CAS-retry figures, which would depend entirely on a contention model chosen to flatter the result. An eliminated pair provably never reaches the stack. The conservation check is there because a scheme that hands values around outside the data structure is exactly the kind that quietly loses or duplicates one.
FIG Elimination backoff is Hendler, Shavit and Yerushalmi (2004). AVAN counted the thing that is actually exact - stack touches - rather than inventing CAS-retry figures, which would depend entirely on a contention model chosen to flatter the result. An eliminated pair provably never reaches the stack. The conservation check is there because a scheme that hands values around outside the data structure is exactly the kind that quietly loses or duplicates one.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN