Zig: SinglyLinkedList should use atomics

[daurnimator]

I was reading https://lwn.net/Articles/827180/ and the example of making a singly linked list was shown.

To get things started, consider this possible code for prepending? (I'm not sure if its correct):

pub fn prepend(list: *Self, new_node: *Node) void {
    @atomicStore(?*Node, &new_node.next, @atomicLoad(?*Node, &list.first, .Monotonic), .Monotonic);
    while (@cmpxchgWeak(?*Node, &list.first, new_node.next, new_node, .Acquire, .Monotonic)) |old_value| {
        @atomicStore(?*Node, &new_node.next, old_value, .Monotonic);
    }
}

[SpexGuy]

We could update std.atomic.Stack to do this, but I think we should keep the standard linked list as is. Atomics have a performance cost on most CPUs, and they also can significantly limit the abilities of the optimizer. For example, if you push and then pop immediately from a linked list, the optimizer may realize that that had no effect and remove the whole thing. But if you use atomics, the optimizer can't make any assumptions when performing the pop and won't be able to do this sort of optimization.

It's also worth mentioning that this type of atomic linked list is subject to the ABA problem. Users have to be careful not to reuse nodes in quick succession to avoid it, or add significant complexity to actually fix it. (using extra flags, using hazard pointers)

[AssortedFantasy]

A proper concurrent lock-free linked list is a far more complicated endevour then just slapping around a few atomics. This talk by Fedor G. Pikus at cppcon goes over a bit of an actual implementation. https://youtu.be/9hJkWwHDDxs (starting around 19:55)

For one thing the pointers can't just be raw pointers, every pointer must be a shared pointer.

I'm not saying the standard library shouldn't have a thread safe singly linked list, but I don't think there is any point in having a not thread safe singly linked list that uses atomics.