Hacker News Reader

Comment by iaaan | Hacker News Reader

Ignorant question: what's the alternative? A normal mutex? I just sort of assumed atomics were abstractions around some type and a mutex.

View on HN

Partition your data structure to be per-CPU and get rid of any sharing.

how is this done in rust or c?

MPI partitioning by rank? I’m curious what other solutions there may be.

This 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.

Algorithm design problems, when general enough, warrant being treated as language problems!

Every feature of programming languages started in this fashion.

Indeed, 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.

There are programming languages e.g. occam designed with the intention of exposing parallelism algebraically, but I wouldn't call them a silver bullet either.

They are great in theory, but sucks in practice.

We don't have good optimising compiler for that

For 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.

For 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.

In rust, you can usually use the rayon library which handles partitioning and scheduling for you.

that'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?

> 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.)

> 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

Locking 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.

This 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.

Yeah, 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.

mutexes 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.

I guess you have more than 8 physical CPUs?

16 cores

Is that AMD or Intel? Intel ivalidates the other CPU's cache line on write. AMD sends an update to the other CPU's cache line. AMD is supposed to be significantly faster than Intel on a "real" multiprocessor workload.

AMD Ryzen 9.

Don’t know why you were downvoted but yes, AMD uses MOESI and Intel uses MESI.

No, they are not.

The slow part of locking is invalidation of cache lines, and this has to happen with spinlocks anyway. Modern mutex implementations also first try to acquire the lock optimistically, so in the uncontended case they are as fast as userspace spinlocks (modulo inlining).

And if you have a contended lock, then userspace spinlocks are a PITA. You need to take care of fairness, ideally deal with the scheduler (yield to a thread that is not spinning on the same spinlock), and so on.

You can do all of that properly, but even then, you're looking at maaaaybe 10-20% performance increase in real-world applications.

Pure spinlocks can win only in contrived cases, like only having exactly two threads contending for the lock, with short locked sections.

Pure spin locks will always win for uncontended locks.

Without any contention at all, a spinlock and a mutex are identical: a single compare-and-swap.

Technically you can use a release-store on a spinlock unlock path, but you need a CAS for a mutex.

>userspace spinlocks are a PITA ... >ideally deal with the scheduler

Don't you anyway need to drop the scheduler a hint so that the thread holding the spinlock doesn't get scheduled off the CPU, making the contenders wait longer than they ideally should? (Or is this what you meant by your "fairness" reference?)

In my limited understanding, this was the no. 1 reason why userspace spinlocks were discouraged -- because pretty much no scheduler accepted a hint from userspace to not kick a thread off the CPU -- modulo jumping through hoops with priority, et cetera.

If I'm missing something (and I likely am), I would be glad to be educated.

You're correct -- the problem with userspace spinlocks is that the holding thread can be scheduled off. You can prevent this to some degree (probabilistically) with isolcpus and thread pinning, but that usually doesn't prevent hardware interrupts from running on those cores (which kernel spinlocks can avoid!). This isn't really solvable without running in kernel context (to have the elevated permissions necessary to mask interrupts).

> Don't you anyway need to drop the scheduler a hint so that the thread holding the spinlock doesn't get scheduled off the CPU, making the contenders wait longer than they ideally should?

How would you do it? You can change the thread's priority to realtime to prevent the scheduler from pre-empting it while holding the lock, but this requires a kernel roundtrip and several scheduler locks anyway.

You can have a worker thread pool, with individual threads hard-pinned to specific CPUs. Then you can dispatch your work into these threads. This in practice will guarantee that they are not pre-emptied except for occasional kernel housekeeping needs.

But this will make it impossible to use the kernel-level mutexes because they can block your worker threads. So you'll have to reimplement waiting mutexes in userspace, along with a scheduler to intelligently switch to a work item that is not blocked on waiting for something else to complete.

Long story short, you're eventually going to reimplement the kernel in userspace. This can be done, and you can get some performance improvements out of it because you can avoid relatively slow kernel-userspace transitions. DPDK is a good example of this, but at that point you're not just using spinlocks, you're writing software for essentially a custom operating system with its own IO, locking, memory management, etc.

Yes indeed -- all of these reasons make userspace spinlocks undesirable in the general case, which is pretty much the point I was trying to make :)

(Edit:) Arguably, I could've been less obtuse in what I wrote.

This is not true, you should never use spinlocks in userspace unless you know exactly what you're doing. Using spinlocks well requires scheduling, which you have no control over in userspace, this is why it makes more sense for kernel to use spinlocks. Without scheduling, with spinlocks, random threads can starve for no reason.

You are right, theoretically.

Unfortunately, the userspace part of pthreads is not tuned for performance and does a lot of ridiculous things if you care about parallelism.

(Mostly I was complaining about the poor quality of userspace system libraries.)

aka share-nothing architecture

It's the other way around. Mutex is an abstraction over atomics.

Other 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.

Not 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.

Don'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.

Honest question: why would atomics be necessary or useful if data isn’t shared between threads?

Because 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.

You can and should use atomics, just not in any kind of hot loop. Using atomics is fine but expensive.

You 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.

Reference 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.

Reply on news.ycombinator.com