6 ms·
Atomics don’t scale. In this age that needs to be widespread elementary knowledge. They are particularly bad on armv8 without atomic extensions because that pla
by jeffbee 3y ago
Atomics don’t scale. In this age that needs to be widespread elementary knowledge. They are particularly bad on armv8 without atomic extensions because that platform has no equivalent to “lock; xadd” and an atomic increment could theoretically become an infinite loop.
- iaaan 3y agoIgnorant question: what's the alternative? A normal mutex? I just sort of assumed atomics were abstractions around some type and a mutex.
- bbatha 3y agoOther way around mutexes abstract around atomics but in typical implementations will yield to the kernel scheduler fairly. That system is called futexes on Linux. The kernel will also use atomics on its end.
- kccqzy 3y agoPartition your data structure to be per-CPU and get rid of any sharing.
- MuffinFlavored 3y agohow is this done in rust or c?
- flatline 3y agoMPI partitioning by rank? I’m curious what other solutions there may be.
- bottled_poe 3y agoThis is not a language problem. It’s an algorithm design problem. There’s no silver bullet. The basic principle is to divide the problem space into independent blocks of work. How to achieve that depends on the problem.
- fooker 3y agoAlgorithm design problems, when general enough, warrant being treated as language problems! Every feature of programming languages started in this fashion.
- bottled_poe 3y agoIndeed, the holy grail (or perhaps the rapture) of programming languages is a compiler which generates the entire program with zero human-written code. I fear it may be on the horizon.
- inopinatus 3y agoThere are programming languages e.g. occam designed with the intention of exposing parallelism algebraically, but I wouldn't call them a silver bullet either.
- j16sdiz 3y agoThey are great in theory, but sucks in practice. We don't have good optimising compiler for that
- cyber_kinetist 3y agoFor a good example, there's a tricky parallelization problem in physical simulation, which you have update edge/triangle/bending wing forces in a mesh structure without any race conditions. (This becomes especially thorny if you want to parallelize your algorithm to the GPU.) A surprising solution for this is graph coloring, where you "color" each element without having two elements that interfere with each other the same color. Then you can safely parellelize the updates of all elements inside each color group, since the same color guarantees absolutely no interference.
- inopinatus 3y agoFor something small like a counter you can use thread_local since C11, but for substantial parallelized computation, designing the division of work to avoid shared writes typically entails a scheduling function that parcels up the work, sets up memory allocation in advance to avoid conflict, and then hands an entirely unshared execution context for each thread to the thread start function, most likely as a pointer to a app-specific struct (since that is what pthread_create allows for), and then subsequently applies a combination operation in the thread reaper loop to collate results (extra brownie points accrue when a reduce function is written to vectorize). The memory allocator plays a significant role, since allocation strategy needs to be per-thread-/per-CPU-cache-aware. Choosing and then tuning a different malloc (e.g. tcmalloc, jemalloc) to the one in your platform's default library is a non-trivial matter but may have enormous impact both on overall performance and memory demand. In addition, when you design computation this way it is relatively easy to hadoopify it later, since it's basically map-reduce writ small.
- deleted 3y ago[deleted]
- pitaj 3y agoIn rust, you can usually use the rayon library which handles partitioning and scheduling for you.
- MuffinFlavored 3y agothat's just multi-threading in general i feel like the post i was responding to was talking about handling/pinning a thread to a specific CPU core?
- otabdeveloper4 3y ago> Just don't use any shared state, bro Thank you, Sherlock. But for the rest of us: when you need shared state, lockfree atomic spinlocks are roughly 1000 times more performant than mutexes. (Not a scientific estimate, numbers taken from real-word experience.)
- petters 3y ago> spinlocks are roughly 1000 times more performant than mutexes That is absolutely not universal. See e.g. but there are of course many places discussing this: https://news.ycombinator.com/item?id=21970050 https://news.ycombinator.com/item?id=21970050
- saagarjha 3y agoLocking is hard in general. Don’t do an unbounded spin in userspace is typically good advice though. The typical mutex construction these days will spin for a little while in an attempt to take advantage of mostly uncontended locks and then yield to the kernel.
- happymellon 3y agoThis immediately popped into my head too when I saw the comment. Spinlocks are terrible, and written by people who are trying to do quick hacks because they work in terrible environments and are taught to do bad things. There is a reason that most GPU drivers are just lists of hacks to get games working correctly.
- imtringued 3y agoYeah, spinlocks sound cool but actually they are terrible. Hybrid locks are generally quite good. The only way to get better is to pin cores and let nothing else run on them. Only then will spinlocks have a chance to increase performance by a tiny bit.
- Ono-Sendai 3y agomutexes are not that slow. Uncontested (single thread): incrementing using atomics took 0.002011 s (0.2513 ns / increment) incrementing using mutex took 0.005515 s (0.6894 ns / increment) Contested (8 threads trying to increment a single protected integer): incrementing using atomics took 0.1069 s (13.36 ns / increment) incrementing using mutex took 1.970 s (246.3 ns / increment) So mutexes are roughly the same speed in the uncontested case, and about 20x slower in this heavily contested case. This is on Windows.
- stevefan1999 3y agoaka share-nothing architecture
- throwdbaaway 3y agoDon't share atomics among threads. For example, envoy proxy mostly doesn't share atomics among threads, and can scale nicely on arm64 without requiring the atomic extensions.
- cdogl 3y agoHonest question: why would atomics be necessary or useful if data isn’t shared between threads?
- NL807 3y agoBecause at some point data has to be exchanged across threads. For example a task queue might have tasks that can independently executed in a thread pool, but the queue index has to be atomically modified when some other thread emplaced a new task. Or if you want to transfer ownership of a heap allocated object between threads, you need to atomically transfer the pointer, or modify the reference count of that pointer. Things like that.
- tormeh 3y agoYou can and should use atomics, just not in any kind of hot loop. Using atomics is fine but expensive.
- loeg 3y agoYou can reduce sharing probabilistically, for example -- because contention is an N-squared problem, reducing sharing by some linear factor is enough for a large reduction in contention. You aren't eliminating contested atomics entirely, just making them low-contention rather than highly contended.
- jeffbee 3y agoIt's the other way around. Mutex is an abstraction over atomics.
- fulafel 3y agoReference counting (the use of std::sync::Arc covered in the article) is a parallelism unfriendly type of garbage collection algorithm - so use a better one. But might be that Rust doesn't make that easy.
- rramadass 3y agoNot ignorant at all, You have actually pointed to the core of the problem. IMO It is not enough to know the logical constructs used for synchronization in parallel programs, you have to know the hardware too. A little bit of everything from high-level parallel algorithms/data structures through memory consistency models, compiler optimizations to processor micro-architecture (cache coherency protocols, atomic instructions, NoC overhead etc.) is needed. Basically we need to be aware of the overheads for contention at every level in the system.
- TedDoesntTalk 3y agoWhat about variables locked with mutexes or semaphores?
- sweetjuly 3y agolocks and mutexes will perform worse than things like atomic increment.
- bluGill 3y agoMaybe. It depends on the algorithm. If you share a lot of data than a mutex, update it all then unlock is fastest. If you share little data atomics can be faster. This is case be case on both the algorithm and hardware, so nobody can say which is better. Of course not sharing at all is of course best, but often you have no choice in that.
- loeg 3y agoThe significant cost comes from contending on memory. Changing the synchronization primitive doesn't help much. You have to change your algorithm not to contend. This is significant because if you profile your code and find that a mutex is expensive, you should change your algorithm to avoid contention rather than blindly trying to change the code to use atomics instead of mutexes.
- trws 3y agoLet’s be clear here, while you are 100% right that armv8 atomics kinda suck by default, neither compare and swap nor load linked store conditional scale but some atomics can scale if implemented and used appropriately. As parent points out, an atomic increment can scale, we proved they could scale to the performance of a load in the 80s for goodness sake. The fact that arm, ppc, and some others tend to implement these in the absolute worst way possible for performance doesn’t mean atomics can’t scale.
- ghusbands 3y agoYou're not being clear - are you claiming that they do scale well on ARM/PPC, despite the "absolute worst" implementation or that they don't?
- bonzini 3y agoHe means that locks anyway have the same problems as atomics on platforms with load locked/store conditional. Therefore yes, that's a problem of the platform, but even on arm/ppc atomics scale better than locks. Which is true, but eliminating sharing works even better if possible as proved by the article.
- moonchild 3y ago> an atomic increment can scale, we proved they could scale to the performance of a load in the 80s Interesting--can you link a reference for this?
- trws 3y agoThis is the citation I most often use from that time, though the primary source is probably another reference down the line: https://dl.acm.org/doi/10.1145/69624.357206 https://dl.acm.org/doi/10.1145/69624.357206 The short version is that if atomics are implemented as part of the memory network, common cache, or memory controller, then atomics of the form “fetch-and-X” can be implemented in roughly equivalent complexity to a load of the current value (plus an instruction for the op, give it take) with the cost only scaling past that as op queues or other implementation-specific limits fire. It’s the infinite consensus ops that just can’t scale no matter what you do. The coherence and memory model matter a lot too of course, which is part of why x86 tends to be slow for atomics, while arm and ppc (with fetch-and-X extensions) or GPUs tend to do much better.
- throwawaylinux 3y ago`lock ; xadd` isn't really fundamentally different than `ll ; add ; sc; b again` The latter is a bit clunky but the core more or less implements them in the same way. Acquire a line exclusive, load value, increment it, write it back. And you can hold the line exclusive such that the conditional store failure cause is mostly a formality, and can't actually become an infinite loop. No general purpose atomics are done by shipping the operation to the cache or to memory controllers, it just doesn't work[*]. So even if they look slightly different in the core, they all end up looking exactly the same at the caches and coherency protocols, and that is where atomics are slow. Well any sharing of cache lines updates really. [*] EDIT: That is to say it doesn't work for performance, for many reasons. Some CPUs do have "remote atomics" something like that which does exactly this, but they are not intended to be broadly used.
- gpderetta 3y agoYes, AFAIK in practice many architectures special case some ll/sc sequences to guarantee forward progress and fairness.
- saagarjha 3y agoIt’s not just theoretical. In bad situations (many cores, heavy contention…) you can get cores to starve each other as they try to each poke the monitor and fail continuously. I know of at least one platform which moved to LSE immediately partly because it fixed stuff like this. LL/SC is nice from some perspectives but it fails if you scale it up and also can be difficult to reason about (cough, cough, Linux getting their cmpxchg implementation wrong for years…)
- jlokier 3y agoCan you say a bit more about what Linux got wrong in cmpxchg or provide a link?
- eldenring 3y agoAtomics scale very well if you are reading often and writing rarely.
- anaisbetts 3y agoYep, uncontended atomics are quite fast. When they're contended is when things start to slow down like OP has seen
- klabb3 3y agoSorry to nit, but this is important. Parent was saying that reads are cheap, which is true. Writes can be expensive even if uncontended, because they invalidate cache lines. I guess you could say they contend with unrelated data but that would stretch the definition a bit. So what does this mean in practice? In my view, the way to think about it is that atomic writes have non-local side effects. But since atomics are necessary for synchronization, and involves both reads and writes, we should compartmentalize and minimize synchronization as much as possible, to avoid these gnarly issues creeping up and tanking real world performance. Arc<T> (and it’s relatives in other languages) constitute textbook violations of this rule. In Rust they are everywhere in non-trivial code, including in the async runtimes themselves. Of course, they also violate (or evade if you’re generous) ownership principles of idiomatic Rust, (or “hello world-Rust”, if you will). I think we need to take a hard look as an industry at ref counting as a silver bullet escape hatch to shared data.
- loeg 3y ago> Writes can be expensive even if uncontended, because they invalidate cache lines. This isn't expensive if cache lines are uncontended, though. > I guess you could say they contend with unrelated data but that would stretch the definition a bit. I think you might be talking about "false sharing." This is real contention on the cache line due to co-location of apparently unrelated variables. > Arc<T> (and it’s relatives in other languages) constitute textbook violations of this rule. Definitely! > In Rust they are everywhere in non-trivial code Ehh.. only the hot ones matter. Most are not actually contended much, and the article's solution (unshared clone) is a very reasonable approach to scale these without an API change.
- mjan22640 3y agothe x86 lock prefix does the same loop, this is the best performant and scaling way to do it
- moonchild 3y agoContended atomics don't scale. It is possible to construct concurrent structures which contend rarely (but which must still use atomics to guard against the rare case when mediation is required). There was also an interesting paper from a few years ago about using HTM to detect contention in a scalable fashion. I will aver that such code may be difficult to reason about—shared-nothing has far more obvious correctness and performance properties. (Queueing/amortisation also works, and lands somewhere in the middle wrt ease of reasoning.) Riscv has an interesting compromise, which is to delineate a subset of ll/sc loops which is guaranteed to eventually make global progress. I do agree that it is better to include real wait-free primitives like cas and faa; but I wish that such guarantees of global progress would be provided to HTM.
- Liquid_Fire 3y ago> an atomic increment could theoretically become an infinite loop Only if your software is badly implemented. If you follow the requirements specified by the architecture, forward progress is guaranteed. Of course there is no guarantee how long it will take, but the things that make it slow are essentially the same things that make atomics slow.