How to make any immutable data structure distributed • Hacker News Board

Re: How to make any immutable data structure distributed

#51

Post by dwohnitmok » Mon, Dec 06, 2021, 8:45 PM UTC

Guvante wrote: post #50

dwohnitmok wrote: post #43

Earlier quoted context omitted.

> CAS is a massive pain in the ass for complex changes. Why is that?

What are you CASing? If the object is too large you will have contention to the point that you might as well be single threaded. If the object is too small you now have to CAS multiple things which is far from trivial. CAS is a primitive, it isn't complex itself but it can be complex to work with once you are talking non trivial work. Just like locks. A global lock is dumb simple but a real locking system can be as c…

> If the object is too large you will have contention to the point that you might as well be single threaded. If the object is too small you now have to CAS multiple things which is far from trivial.

Right but both of those things are true for locks too right? CAS seems no harder than locks.

Re: How to make any immutable data structure distributed

#52

Post by Guvante » Mon, Dec 06, 2021, 9:04 PM UTC

dwohnitmok wrote: post #51

Guvante wrote: post #50

Earlier quoted context omitted.

What are you CASing? If the object is too large you will have contention to the point that you might as well be single threaded. If the object is too small you now have to CAS multiple things which is far from trivial. CAS is a primitive, it isn't complex itself but it can be complex to work with once you are talking non trivial work. Just like locks. A global lock is dumb simple but a real locking system can be as c…

> If the object is too large you will have contention to the point that you might as well be single threaded. If the object is too small you now have to CAS multiple things which is far from trivial. Right but both of those things are true for locks too right? CAS seems no harder than locks.

Retry logic is hidden for locks while in your face for CAS.

Additionally while multiple locks is annoying it is way easier than multiple CAS. "Have a global order for locks" is the hard but solvable problem for multiple locks. For CAS if you need to CAS two dependent things you... I don't know it depends.

Re: How to make any immutable data structure distributed

#53

Post by dwohnitmok » Mon, Dec 06, 2021, 10:21 PM UTC

Guvante wrote: post #52

dwohnitmok wrote: post #51

Earlier quoted context omitted.

> If the object is too large you will have contention to the point that you might as well be single threaded. If the object is too small you now have to CAS multiple things which is far from trivial. Right but both of those things are true for locks too right? CAS seems no harder than locks.

Retry logic is hidden for locks while in your face for CAS. Additionally while multiple locks is annoying it is way easier than multiple CAS. "Have a global order for locks" is the hard but solvable problem for multiple locks. For CAS if you need to CAS two dependent things you... I don't know it depends.

> Retry logic is hidden for locks while in your face for CAS.

It's hidden in both cases (usually CAS instructions are hidden behind an `update` interface as in Java's Atomic* family rather than directly used in the same way that generally a lock is an interface for a TAS instruction/spin lock + upgrading to wait queue).

> For CAS if you need to CAS two dependent things you... I don't know it depends.

You use nested atomic references. Just like locks it's not a great way of doing things, and an analogous problem to ordering locks rears its head (by virtue of nesting you cannot mess up ordering in the strict sense, but you can accidentally "cross the boundaries" of two atomics in an update that goes against the nesting order), but it's doable in the same way as locks.

The usual CAS-like but better approach is STM (which is where immutability really shines).

I'm still not seeing how CAS is any harder than locks.

Re: How to make any immutable data structure distributed

#54

Post by cipheredStones » Tue, Dec 07, 2021, 8:23 AM UTC

jmfldn wrote: post #44

cipheredStones wrote: post #7

Earlier quoted context omitted.

Tangential to the thread, but do you have any other favorite Scala resources you would recommend? I've had only glancing exposure to it, and will soon be taking a role where it's the primary language.

I do indeed. The "red book" aka Functional Programming in Scala I wouldn't recommend to a beginner. It teaches FP at a fairly deep level to the extent of implementing the abstractions yourself. Take a look at that later perhaps. Don't get me wrong, it is utterly brilliant but it wouldn't be the place to start. I would recommend Essential Scala for the basics. Scala with Cats if you're going to be working with the Typ…

Thank you, much appreciated!