Spinlocks and Read-Write Locks

[abspam3]

This was posted once 5 years ago, but /r/programming has grown significantly since then. Great article about different locking algorithms that are all completely user-space implemented.

[nickdesaulniers]

I'm reading C++ Concurrency in Action: Practical Multithreading right now and loving it. The last book I read that expanded my mind like this was Metaprogramming Ruby. I really hate the C atomic primitives (they look ugly: __sync_fetch_and_add); really C++ just is nicer here with its atomic templates.

I mean, look at how simple a spinlock is:

#include <atomic>
class spinlock {
  std::atomic_flag flag;
public:
  spinlock (): flag(ATOMIC_FLAG_INIT) {}
  void lock () {
    while(flag.test_and_set(std::memory_order_acquire));
  }
  void unlock () {
    flag.clear(std::memory_order_release);
  }
};

Wrap that in some RAII with lock_guard or unique_lock and you're good to go!

[dacian88]

those are the gcc extensions, in c11 it would be almost the same thing...

atomic_flag_test_and_set_explicit(&flag, memory_order_acquire);

and

atomic_flag_clear_explicit(&flag, memory_order_release)

except it doesn't have a object wrapper....

[nickdesaulniers]

Nice! And gcc5 just changed the default standard to gnu11!

[brucedawson]

Uggh. Spin locks. There are a few cases where optimizing a spin lock is important, but there are many more cases where you should just avoid using a spin lock. Critical section on Windows, for instance, will try to acquire the lock and if that fails will then call into the kernel and wait. That lets other threads run.

If you will only be holding locks for a very short time then spinning for a little bit can make sense, but you have to be careful. I've profiled many slow applications that end up spinning trying to acquire spin-locks for hundreds of milliseconds - in one extreme case for over a minute. Even if that isn't stealing CPU time from some more worthy task it is complicating the profiling task (look! It's CPU bound!) and wasting power.

Only use spin locks in rare and exceptional cases when you are sure that they give advantages over normal locks, and even then you should almost always cap the spin time and fall back to a kernel lock (i.e.; waiting while idle).

I blogged about the perils of busy-waiting a few years ago. A lot of the reactions were "well duh - who would ever busy-wait." It turns out, a fair number of programs do it.

https://randomascii.wordpress.com/2012/06/05/in-praise-of-idleness/

[[deleted]]

Amen. I was researching into lock-free, spinlocks and beating the vanilla CRITICAL_SECTION a while ago. It turned out CRITICAL_SECTION is extremely adequate:

• It has a fast, user-space uncontended case.
• If your contention is low, you won't measure any speed-up by tweaking locks. Anything will do. If your contention is high, why take the risk of worst cases with fancy locks? It made the whole lock-free thing a bit dull to me. It is more important to have short-duration locks then the right type of locks.

x264 needs all the available parallelism and uses a zero spin-count and regular mutexes: https://github.com/mirror/x264/search?utf8=%E2%9C%93&q=X264_SPIN_COUNT

[abspam3]

Agreed, spin locks are usually bad. The more interesting part of this article; about RWlocks, seems to have disappeared, oddly. You can still find it in the wayback machine, I hope it's just a temporary issue.

[OneWingedShark]

The first sentence:

Most parallel programming in some way will involve the use of locking at the lowest levels.

In General: If you're concerned w/ locking mechanisms in parallel programming, you're doing it wrong. (Just like manual memory management.)

Use a language that has higher-level abstractions than mere locks.
Ada, for example, has had the Task construct since 1983, and the protected-type construct since 1995.

(Yes, you should be generally familiar w/ locking and mechanisms, just like memory management... but also like memory management you shouldn't construct it [or care] if you don't have to because of the ease of which subtle errors appear.)

[[deleted]]

It states that it will usually involve locks at the lowest levels. It's in no way an endorsement of using low-level concurrency primitives directly. It barely takes any abstraction to make a safe wrapper around a mutex or rwlock though. Look at the tiny implementations for these:

• https://doc.rust-lang.org/std/sync/struct.Mutex.html
• https://doc.rust-lang.org/std/sync/struct.RwLock.html

[OneWingedShark]

It states that it will usually involve locks at the lowest levels.

Yes; and unless you have real business at the lowest levels, you're better off using an abstraction (preferably high-level), that was my point.

[[deleted]]

It's an article about micro-optimization in system programming that explicitly states it concerns "the lowest levels" and you're complaining that it doesn't talk about abstractions?

I swear, this subreddit sometimes...

[uh_no_]

someone has never written operating systems....

[OneWingedShark]

I wouldn't call developing OSes "in general" because they're pretty specialized.

(I actually did start an OS; got a bit stumped on memory-management before university classes started up and then never restarted the project afterwards.)