4 ms·
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 s
by bsder 11y ago
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.
- gamegoblin 11y agojava.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.
- bsder 11y ago> 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.
- gamegoblin 11y agoThe 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.
- kabdib 11y agoI'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.
- raverbashing 11y agoThis is the kind of thing you abstract on a library
- kabdib 11y agoExcept 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.
- bsder 11y ago> 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.
- arielby 11y agolock-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.
- bsder 11y agoLock-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".
- chrisseaton 11y ago> 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.
- bsder 11y agoA 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.
- chrisseaton 11y agoI 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.
- bsder 11y agoHave 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.