Reason for weird conditionallyRemoveHead implementation

[asonix]

I just finished watching the video from yesterday's stream and I wanted to point out the reason for the implementation of conditionallyRemoveHead in the java codebase

Say we have 2 nodes, the first is the sentinel, and the second is the "first valued node".

order: [sentinel] -> [node 1] -> null

We also have two additional pointers

head -> [sentinel]
tail -> [node 1]

In this situation, the desired outcome is this:

order: [sentinel] -> null
head -> [sentinel]
tail -> [sentinel]

Going Wrong

If we want to keep the sentinel in place, we need to know [node 1]'s next pointer, so we'll end up with something like

compare_exchange(
  [sentinel]->next, // pointer we're modifying
  [node 1], // expected value
  [node 1]->next, // new value
)

but now we have a problem, because our pointers look like this:

order: [sentinel] -> null
head -> [sentinel]
tail -> [node 1]

so we need to add in an additional store to update tail

store(tail, [sentinel])

but wait! maybe another thread has enqueued a new node during this time

order: [sentinel] -> null
order (somewhere else): [node 1] -> [node 2] -> null
head -> [sentinel]
tail -> [node 2] // this could optionally still be [node 1] if the enqueue hasn't finished yet

The list has now been split, since enqueue pushes onto the tail, rather than traversing the list from head. Say we finally store our new tail value, our pointers end up like this:

order: [sentinel] -> null
order (somewhere else): [node 1] -> [node 2] -> null
head -> [sentinel]
tail -> [sentinel]

We have successfully forgotten an enqueued node during this process.

Going Right

By instead promoting the existing "first value node" to being the new sentinel we avoid this problem. Let's take a look:

order: [sentinel] -> [node 1] -> null
head -> [sentinel]
tail -> [node 1]

We'll preform our compare_exchange to update the head pointer

compare_exchange(
  head, // pointer we're modifying
  [sentinel], // expected value
  [sentinel]->next, // new value
)

now our pointers are as follows:

order: [sentinel] -> [node 1] -> null
head -> [node 1]
tail -> [node 1]

at this point, nobody but us should know about [sentinel] anymore, and it's perfectly fine to get rid of it. Any future reads to head or tail are correct. we can optionally perform the following store:

store([sentinel]->next, null)

but we might get that for free when dropping [sentinel] once we have memory reclamation

That's all I have on that topic. Great stream by the way, hopefully I can catch the next one live.

[jonhoo]

This is great, thank you! I'll bring this up next stream, and also add a comment to the code to clarify (or maybe you want to do it with a PR?).

[asonix]

I'll leave adding a comment to you. I'm hesitant to modify a stream project off-stream tbh, even if it is just a comment