last day (1365 days later) » 

4:21 AM
-1
A: Are X86 atomic RMW instructions wait free

user3453226When multiple threads happen to lock the same cache line, their execution is serialized. This is called write contention due to false sharing. The single-writer principle stems from this. Writes cannot be performed concurrently, as opposed to reads. From 1024cores.net: atomic RMW operations have...

 
I don't think this has anything to do with non-blocking algorithms (NBA). The assumption behind the NBAs is that if a thread (execution) is suspended then either some progress can still be made (lock-free) or even all threads can progress (wait-free). But x86 instructions cannot be suspended midway, so the whole question doesn't apply in the first place. lock works by either delaying the cache coherency messages (the RFO, IIRC) or by asking a lock from the quiescent master (the system agent). Either way, this is blocking.
If a ucode bug would freeze the CPU in the middle of a lock the lock would say on forever (see the F00F bug). Possibly, a watchdog timer in the quiescent master could revert the lock (if granted by them) but I think this is a catastrophic failure scenario and no recovery can be expected.
 
What hardware did you test on? (hyperthreading / SMT enabled or not? Also, AMD or Intel might have different hardware arbitration) Were all threads trying to increment the same location, or were some using different cache lines? How many cores did your CPU have? Obviously having some threads descheduled is going to make a huge difference.
It takes exactly one lock add [rdi], eax to increment a memory location, regardless of how long that takes in seconds or cycles. Algorithm analysis is often done in abstract steps (which could correspond to instruction), without considering exact time cost of each step, but usually with the tacit assumption that each step has about the same cost. That's what makes it hard to answer this question.
Also, I'd wouldn't just say it's "not lock-less". There's no way for a thread to sleep while holding the hardware "lock" on a cache line, and holding the lock only lasts for one instruction (for a few cycles while the core owns the line for an RMW). There's an important distinction between the kind of locking software can do (which can block other threads), vs. hardware contention via MESI.
It matters what kind CPU you have because you previously were talking about a 200 thread test, and earlier you hadn't explicitly state whether you had more physical cores than threads. Also, the interconnect between cores is different in Skylake Xeon (a mesh) vs. previous Xeon and still-current consumer chips (ring bus). So anyone curious about your actual numbers for any specific purpose, or comparing to their own test, would get a lot more value from yours if they know what CPU it's for. Always include HW and SW details if you're going to bother to do a benchmark at all.
But how are you measuring single instructions? Surely the slowest ones are just noise from interrupts, if you're not already detecting that somehow to rule it out. Also, are you checking perf counters for the MACHINE_CLEARS.MEMORY_ORDERING to see if that's ever happening? locked instructions might avoid it, but it would be interesting to check. Why flush the pipeline for Memory Order Violation caused by other logical processors?
 
user3453226
@PeterCordes System.nanoTime() It has 100ns granularity. Since it takes 14ns to execute, I have a dedicated thread that reads it continuously, so its value is kept in memory and reading it is a simple getOpaque() that takes ~4ns IIRC.
 
You're writing this in Java?!?!?? How are you verifying that you get exactly the asm loop you wanted to measure? I guess usually the overhead is high enough that the details of the loop probably won't matter, but C or asm would be much more obvious choices. Reading a shared variable should just be one load that can be executed in parallel with other stuff if it's hot in cache, otherwise (e.g. after the writer writes it) it will miss. But waiting for that miss can happen in parallel with waiting for the cache line you want to increment.
 
Good edit but I don't agree with that thread. They assume an x86 instruction always terminates when started (and so no lock is held indefinitely), but then the basis for talking about lock-freedom is missing. Either you make the assumption a lock instruction could, somehow, be suspended forever midway, or you don't talk about lock-freedom of instructions. We are talking about the algorithm used by the instruction not the algorithm built with that instruction. The Wikipedia statement "When a thread is suspended", in this case means "when a lock instruction is suspended".
 
4:21 AM
Regarding "For modern Intel x86 processors cost of a single atomic RMW operation (LOCK prefixed instruction) is some 40 cycles.[...] However, the cost is fixed": you have quoted it in a misleading way. Clipping out the rest of the sentence and also the earlier context. This quote appears in at the end of a list of costs for atomic operations, and is specifically only dealing the core-local fixed costs. In fact, if could have included the rest of the last sentence: "... cost is fixed and does not affect scalability, so is far less important than above-outlined scalability-affecting points."
This would have made it clear that the author is not saying "the cost is fixed, period".
 
Right, the part of the cost that's local to a single core doesn't scale with number of cores. But the majority of the cost with multiple cores hammering on the same line is the time waiting to get access to a line in the first place, making the fixed core-local part of the cost nearly irrelevant.
re: stores being wait-free. Only if you measure in steps or instructions, ignoring cycles or seconds. Now you're leaving out the more important practical part of the answer. (Except for "their execution is serialized" and the "proportional to how much contention the cache line experiences" parts, which seem to conflict with your later claims of wait-free stores / RMWs.) I removed my upvoted since you removed the important practical part of the answer that did usefully point out the difference between counting cycles vs. counting instructions executed.
@MargaretBloom: I think it does make sense to talk about different levels of parallel progress being possible. Wait-free means all threads can make parallel progress, lock-free means at least 1 can. For cores / threads accessing the same location, and counting progress per cycle (not per instruction), that's atomic loads vs. atomic stores and RMWs. There doesn't have to be any possibility of actually locking anything; your complaint about the lock prefix and actual locking is IMO misplaced. The fact that there are no single instructions with weaker or no guarantees isn't a problem.
 
user3453226
@PeterCordes I'm taking the definition of wait-free that's written in the question. "all threads can make parallel progress" is wait-free population-oblivious (if that is actually universally accepted and was not invented by the author of the linked post). What you call instructions vs cycles, I call algorithm vs instruction, where algorithm is the retrying done by the hardware, and instruction is what modifies the cache line while it is locked.
 
@PeterCordes Do you mean that even if an HW thread is holding a uarch lock forever, the other HW threads would not freeze but keep trying to acquire it? But that would not constitute successful progress, I guess. Otherwise, I'm afraid I don't get your point. If one could use the Intel's internal tool sto freeze a lock add just after the read phase, no other HW thread could read the same line/location since the lock is still in place. That doesn't mean lock-freedom is impossible, it suffices to assume CPU instructions don't fail and use appropriate primitives (e.g. a CAS).
 
@MargaretBloom: I'm ruling out the possibility of HW bugs that result in holding a uarch lock forever. (e.g. never replying to a MESI share or RFO request while a line is in M or E state). I guess your way is an alternative way to formulate a similar idea, by considering the hypothetical of what if the cache-lock was never released, but that seems like an extra complication or extra mental gymnastics. There are no x86-64 instructions that can cause this problem, lock-anything completes in ~fixed cycles after taking a cache-lock. And TSX transactions abort on contention like LL/SC, I think.
Your answer quotes a claim that x86 CPUs internally "retry" something, which sounds lock-free not wait-free. I'm not sure what Dr. McCalpin is talking about in that linked quote; doesn't match my understanding unless he's talking about the core optimistically dispatching uops in hopes that the cache line is about to arrive that cycle.
(We do know that cache-miss loads lead to uop replays on Intel CPUs, but that happens even for mov eax, [rdi] / add eax, eax. So it seems more useful to think of it is the CPU just filling time while waiting, unless we're worried about HT/SMT friendliness. See also chat.stackoverflow.com/transcript/message/48426964#48426964)
 

  last day (1365 days later) »