Comment by bsder | Hacker News Reader

Comment by bsder | Hacker News Reader

Sigh. What's wrong with using lock-free data structures?

Go study java.util.concurrent. It's one of the absolute best libraries ever written by some of the smartest programmers I have ever seen.

The primary question is "Do I really need to wait or do I just need to be consistent?" 90% of the time the answer is that consistent is good enough.

Lock-free data structures are not a panacea. They don't always do as well as locks in the face of contention. However, if you have that much contention, congratulations, you have an actual spot you really need to optimize.

By default, though, lock-free data structures protect you from so much fail it's ridiculous. I don't dread concurrent programming if I have a good lock-free data structure library.

That having been said, if you really have to wait (normally for hardware access), then you MUST do certain things. Your "lock" MUST be as small as possible--if it isn't "lock with timeout", "single small action that always goes to completion even if error occurs", "unlock"--YOU HAVE FAILED. START OVER. Also, note the "timeout" portion of the lock. "Timeout" MUST be handled and IS NOT NECESSARILY AN ERROR.

Now, these don't get all the situations. People who need "transactions" have hard problems. People who have high contention have hard problems.

However, I can count the number of times I genuinely needed to deal with contention or transactions on one hand and still have two fingers left over.

Whereas, I have lost count of the number of times that I cleared out all manner of bugs simply by switching to a lock-free data structure.

> Sigh. What's wrong with using lock-free data structures?

They don't compose.

You can't use them to, for example, implement a bank account system where you need to atomically remove from one account and add to another, unless there is special support for that in the implementation - and there can't be special support for everything built in.

A lock-free hash table most certainly composes, but it may not scale. That's why you use it instead of a lock.

This is exactly the kind of thing that hangs everybody up when programming concurrency.

Most people just want "multiple tasks executing simultaneously that occasionally have to exchange data". However, everybody beats them over the head with "must always have exactly consistent state".

These are two very different problems.

I don't get your argument. You start off with a 'sigh' as if this is a trivially solved problem and anyone else is just being awkward, and then you admit that this only holds when you don't care about consistency, and on top of that, only when you don't really have a complex parallelism problem in the first place!

The actual answer to your question 'what's wrong with using lock-free data structures?' is really simple - what's wrong with them is that they don't provide atomicity, consistency nor isolation under composition.

Have you ever used one? Please go read all the stuff about java.util.concurrent. It holds for almost all lock-free libraries, but it's way better documented than anything else.

They provide consistency and atomicity. Lock-free data structures are always in a consistent state. The view they provide is always "atomic". It moves from one consistent state to another with no inconsistent state ever visible in-between.

They provide isolation under composition quite well. They compose far better than locks which can't even handle a simple inversion of order.

What they generally don't provide are guarantees of progress under high contention. The structure will never be wrong, but it may not be efficient.

The problem is that everybody equates "consistent" and "atomic" with "absolutely must exist in one and only one place at all times". And that's too strong for most uses.

Yes, if you are writing bank software, you want that transaction to ever only exist in exactly one place.

But, 99% of the time, that's too strong a guarantee.

Yeah I've read the literature and used lock-free data structures extensively. I've got a chapter in my PhD thesis about data-flow concurrency structures which were implemented using lock-free constructs, and I work in Oracle Labs on JVM research.

You've suggested a definition of consistency which is something like "could possibly exist in zero or more than one place at the same time". Well that's useless! Anything could be consistent with that definition!

So really I think you agree with me that you cannot compose multiple operations on a lock-free data structure and get any degree of atomicity, consistency or isolation. But you just don't think that matters for most programs, so you weaken the definitions until they could be met by anything.

> Yes, if you are writing bank software, you want that transaction to ever only exist in exactly one place.

Right so this answers your question!

> Sigh. What's wrong with using lock-free data structures?

Because - as you say! - they don't meet all requirements!

Finally - I don't think we even have lock-free implementations of all data structures do we? So it's not even always an option.

I'm terrified of lock-free stuff because it typically depends on nasty things like memory order, cache behavior and other subtle things, mostly nonportable and simply awful to get right on a new platform.

Also, I keep finding bugs in lock free structures. That's annoying.

This is the kind of thing you abstract on a library

Except that libraries are written by people, who have assumptions and probably limited budgets, and the sheer inventiveness of hardware engineers at making things like memory ordering different, or even buggy [game consoles are famous for this] . . . well, libraries aren't magic. You have to test them somewhere, and the failures are often subtle, happen sporadically, are hard to reproduce and are very difficult to debug.

I've used them. But in limited areas, where the win is great and they are explicitly called out as portability hazards, with alternate implementations of the areas in case the lock-free stuff goes pear-shaped. And from time to time we look at these things and wonder if the performance gain is (a) real, and (b) worth the headache.

> I'm terrified of lock-free stuff because it typically depends on nasty things like memory order, cache behavior and other subtle things, mostly nonportable and simply awful to get right on a new platform.

Not really. Most lock free stuff relies on a single compare-and-swap or memory barrier instruction. Even the cheap microcontrollers have them these days.

> Also, I keep finding bugs in lock free structures. That's annoying.

I recommend you leave programming now. :) I have yet to find a library that doesn't have bugs.

java.util.concurrent has some great functionality, but I have found that some of the concurrent datastructures cause significantly more garbage generation than their non-concurrent counterparts.

I was writing some highly concurrent code and initially wrote it with the jdk's lock-free containers, but found that GC was about 5-10x worse (depending on the workload) than simply wrapping the non-concurrent equivalent in a lock.

> I was writing some highly concurrent code and initially wrote it with the jdk's lock-free containers, but found that GC was about 5-10x worse (depending on the workload) than simply wrapping the non-concurrent equivalent in a lock.

That seems a bit high, but I can believe it under heavy contention.

But, you measured, and then optimized. Which is what people should be doing but aren't.

The biggest of them was all of the Node objects that ConcurrentSkipListSet generates. Replacing that with a synchronized TreeSet fixed most GC issues.

Yes, this was a 100K+ element collection being concurrently used by 1000+ threads. I used YourKit to profile.

lock-free data structures should have identical semantics (and uncontended performance) to lockful data structures with per-operation locks (up to performance), except for the temptation to hold the data structure lock for a long time.

The problem with locks is that people don't want one thread per object, and instead use one lock per object. This has the effect of making all object operations synchronous, which turns some potential race-conditions into deadlocks.

Lock-free data structures generally use check-and-retry (compare and swap) rather than a lock.

Now, in the face of contention, they don't scale as well as a lock. However, this falls under "optimize when you have data".

Reply on news.ycombinator.com