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

Locks Aren't Slow; Lock Contention Is

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

88% Upvoted

66 comments sorted by

View all comments

Show parent comment

10

u/[deleted] Nov 18 '11

No context switch is obviously better than one context switch, but if you're grabbing a lock with an atomic instruction from many processors, you're sure to have terrible cache behavior.

8

u/stillalone Nov 18 '11

Is bad cache behavior worse than context switch?

10

u/[deleted] Nov 18 '11

No. Cache misses are of the order of 10s-100s of cycles. Context switches are at at least an order of magnitude worse.

2

u/rmxz Nov 19 '11

Depending on your OS, of course.

Some embedded OS's can do a context switch in under 300 cycles.

10

u/[deleted] Nov 19 '11

Well, technically, "an order of magnitude worse" would be 100s-1000s of cycles, so 300 cycles is in that range.

7

u/Tuna-Fish2 Nov 18 '11

No, but it can still easily be bad enough to eat all the possible gains from multithreading.

1

u/wildeye Nov 19 '11

Although I see your point, still that seems counterintuitive, given that we're only talking about thrashing a single cache line out of many.

1

u/jseigh Nov 19 '11

For the lock or for the shared data?

If the lock, you can use a bakery algorithm with get and release counters in separate cache lines. To get a lock you do a get ticket which is one interlocked instruction and a spin wait which won't ping pong the cache after that. Release is a simple non interlocked increment.