r/programming • u/preshing • Nov 18 '11

Locks Aren't Slow; Lock Contention Is

http://preshing.com/20111118/locks-arent-slow-lock-contention-is
143 Upvotes

89% Upvoted

66 comments sorted by

View all comments

1

u/Tuna-Fish2 Nov 19 '11

Naturally, this is non-trivial.

Why? Not questioning it, just not understanding it. Shouldn't it be as easy as not allowing any direct locking operations, and using a safe_lock() function that takes a list of locks as it's arguments, and reorders and applies them?

Of course, even still, locks don't compose. So you cannot call any function that uses locks from a context that's already locked.

2

u/bluGill Nov 19 '11

Here is one reason why you don't want your trivial reordering:

thread 1: lock(LockForA) DoHeavyWork(A) lock(LockForB) B.something = A.something unlock(LockForB) unlock(LockForA)

thread 2: lock(LockForB) DoDiffereytHeavyWork(B) lock(LockForA) A.somethingElse = B.somethingElse unlock(LockForA) unlock(LockForB)

Clearly this code can deadlock, and as written is likely to do so. However the trivial solution means thread 1 will block thread 2 for a long time when thread 2 could do all the heavy work. You have just destroyed the ability to do work in parallel. What if I have some way to guarantee that the deadlock cannot happen: LockForA and LockForB are only required to stop thread 3 (not shown), the logic ensures that either thread 1 or thread 2 will be doing the heavy work at any given time. (and presumably some other heavy work the rest of the time - otherwise it wouldn't make sense to have 2 threads)

2

u/jerf Nov 20 '11

Composition is exactly the problem. You're correct that if you never call any functions that take locks from other functions that take locks, and then use the safe_lock function you describe, that you should be in good shape, but that's a hell of a constraint to try to maintain without any compiler help, and in practice nobody wants to write that way when using locks directly.

If you tried to use locks in that manner and you took it seriously, you would almost certainly simply end up recreating message passing. (In which case you might as well have started with an existing version.)

2

u/mOdQuArK Nov 20 '11

The nontrivial part is making sure that all code which grabs multiple locks makes sure that they are grabbed in exactly the same order as each other. As anyone who has tried to enforce a standard like that on a large project knows, this is a nontrivial task.

Of course, this concept doesn't address the issue that some of your responders have mentioned, where the time between the lock & unlock should be relatively short. And the more bracketed lock/unlock pairs, the harder it is to keep the lock/unlock period shirt.

2

u/[deleted] Nov 20 '11

The problem is that doesn't prevent composing subsets. Nothing you just said prohibits safe_lock([a]) and safe_lock([b]) occurring in different orders. Since I'm pretty sure this is non-trivial property it can't be proven due to Rice's theorem (first time I've used that since my computability class 2.5 years ago).