3 ms·

Please excuse me if my question is dumb, I have little understanding of Rust. You declaring your implementation "lock-free", but are using Atomic* Rust primitiv

Please excuse me if my question is dumb, I have little understanding of Rust. You declaring your implementation "lock-free", but are using Atomic* Rust primitives at the same time. Those are using CPU atomic instructions, if I googled correctly. Those, in their turn, are using CPU locking mechanism. Turns out that you just shifted locking from language to CPU, right?

mrcode007 3y ago
Yes, this is correct and the most overlooked aspect and reason for the misnomer. Atomics imply locking at the cpu. Depending on the CPU the lock happens either for the entire memory bus (pre Intel P6 on x86) or as part of snoop disable bits on relevant cache lines in the snooping protocol
- DannyBee 3y ago
  It's not a misnomer, it's just a bad term of art. When it was coined folks were well aware that atomics locked at the CPU level.
  - mrcode007 3y ago
    “In discussing the question, he used to liken the case to that of the boy who, when asked how many legs his calf would have if he called its tail a leg, replied, ” Five,” to which the prompt response was made that calling the tail a leg would not make it a leg.”
    - deleted 3y ago
      [deleted]
- gpderetta 3y ago
  The "locking" happening on the CPU level is very different from the software level locking, as it is guaranteed by the hardware to be bounded (technically bus arbiters are not guaranteed to complete in finite time, but they are astronomically unlikely to do so).
DannyBee 3y ago
It's a reasonable question, because lock-free is a confusing term. Lock-free here does not mean "without any form of synchronization primitive". That is impossible. Some synchronization must occur. Instead, it is a term of art that means: 1. Thread failure can't cause other threads to get blocked. 2. Forward progress in the algorithm is guaranteed. Basically: threads can't block each other and death of threads does not screw things up. https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm CPU atomics often work by blocking (they have to) but they are non-interruptible instructions and there is a fixed maximum execution time. (So you can still guarantee forward progress if you use them).

mrcode007 3y ago

Yes, this is correct and the most overlooked aspect and reason for the misnomer. Atomics imply locking at the cpu. Depending on the CPU the lock happens either for the entire memory bus (pre Intel P6 on x86) or as part of snoop disable bits on relevant cache lines in the snooping protocol

DannyBee 3y ago
It's not a misnomer, it's just a bad term of art. When it was coined folks were well aware that atomics locked at the CPU level.
- mrcode007 3y ago
  “In discussing the question, he used to liken the case to that of the boy who, when asked how many legs his calf would have if he called its tail a leg, replied, ” Five,” to which the prompt response was made that calling the tail a leg would not make it a leg.”
  - deleted 3y ago
    [deleted]
gpderetta 3y ago
The "locking" happening on the CPU level is very different from the software level locking, as it is guaranteed by the hardware to be bounded (technically bus arbiters are not guaranteed to complete in finite time, but they are astronomically unlikely to do so).

DannyBee 3y ago

It's a reasonable question, because lock-free is a confusing term. Lock-free here does not mean "without any form of synchronization primitive". That is impossible. Some synchronization must occur. Instead, it is a term of art that means: 1. Thread failure can't cause other threads to get blocked. 2. Forward progress in the algorithm is guaranteed. Basically: threads can't block each other and death of threads does not screw things up. https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm CPU atomics often work by blocking (they have to) but they are non-interruptible instructions and there is a fixed maximum execution time. (So you can still guarantee forward progress if you use them).