7 ms·
Ignorant question: what's the alternative? A normal mutex? I just sort of assumed atomics were abstractions around some type and a mutex.
by iaaan 3y ago
Ignorant 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.