undefined | Better HN

0 pointsbsder10y ago0 comments

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.

0 comments

3 comments · 1 top-level

chrisseaton10y ago· 2 in thread

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.

bsderOP10y ago

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.

chrisseaton10y ago

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.

j / k navigate · click thread line to collapse