When Rich Hickey uses "CAS" in his talks, I am assuming that means "Compare And Swap", but not necessarily just the processor instruction version of that idea?

And if that is correct, what is the more general form of it that is not a processor instruction? The moral equivalent in any concurrent system you are talking about?

Here is link to several uses of CAS in his talks across the years, from matthiasn's Github repo of talk transcripts: https://github.com/matthiasn/talk-transcripts/search?utf8=%E2%9C%93&q=CAS&type=

In particular the reference to "CAS timelines" in the "Are We There Yet" talk is not familiar to me. That might mean "a causal timeline constructed between threads based upon an order that they succeeded updating a compare-and-swap word of state"?

@andy.fingerhut: I do not know for certain what Rich is saying by STM vs CAS, but I can give a plausible theory. Do you want to hear it?

STM incorporates multiple values changing atomically, whereas CAS involves single values, if I'm not mistaken. Basically refs vs. atoms?

Sure.

Do you have a pointer to some place where he is saying "STM vs CAS", or a few sentences in one of his talk transcripts that you are describing that way?

Say we have some map M, thread 1: read (:a M) read (:b M) do some computation write to (:c M) thread 2: write (:a M) write (:b M) //in the STM model, both of these are executing optimistically, but there is a potential "oh shit", if it happens taht: thread 2 writes :a thread 1 rreads :a thread 1 reads : b thread 2 writes : b thread 1 writes : c so the STM somehow needs to detect thes interleaved read/writes, and rolls stuff back in the CAS model, we have: thread 1: I read M_bar, I now want to write it with M_bar' thread 2: I read M_foo, I want to write M_foo' so basically both threads are saying: "if current state of M is the state I read it as, then use this new value for M" ^-- this is all theory / my understanding / no idea if this s what Rich meant in the talk

@andy.fingerhut: ^

with regards to your other uestion, here we are "CAS" on a entire MAP, not just a single value

So I understand that CAS the instruction can be used to implement a pointer-flip atomically, so "if this pointer to a map is the one I have been calculating an updated version of, then here is the pointer to the new version to replace it with, otherwise return failure, and I will start all over again with the current latest map".

That I believe is the underpinning of a Clojure atom.

With which you can do atomic updates of arbitrarily complex data structures, but only single ones.

The 'start over and retry' is what makes it a CAS as opposed to what is traditionally called just 'atomic swap'

(or something like that, reaching back to ye olden days)

STM is coordinated updates across an arbitrary subset of your refs, which I haven't dug into all the details of, other than if I wanted to do that, I would want to do nothing else brain intensive while studying it for a month.

STM is basically a locking system, somewhat like the way core.async channels work

You do some work, tracking all the refs you need to read/write from, when you're done you lock all the refs and and make the changes. If the contents of the refs have changed between the reading and the final lock, roll everything back

There's a lot more in the implementation though since you have to lock the refs in the right order (to avoid deadlock), and Clojure STM has the ability to barge a lock. One thread can say "you're taking too long, stop it!" and take control of the refs from another thread.

performance debugging STM sounds like a nightmare

So in his "Language of the System" talk, he says this: "There's nothing about what I just said that is about Clojure, that is about memory, that is about locking. There is a little bit that's probably about CAS, but not CAS on the chip. It's a very, very general notion, and Datomic implements that notion at large, but you can also implement it yourself. And you're going to need to combine a couple things. You're going to need to combine naming values with some sort of reference and some sort of a la carte coordination."

https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/LockingTransaction.java#L256

does STM imply an automatic retry on conflict, or is that just a clojure thing?

@noisesmith not sure

I am curious what the "very general notion" of CAS is meant here -- is it basically "any way of doing the equivalent of a Clojure atom swap! operation", whether it involves a compare-and-swap instruction in a chip, or some other method?

Right, so in the case of Datomic it's all a bit different. Values + single writer + some queue = Datomic's model

So in the case of Datomic on Cassandra, most of the data storage used is immutable but it uses Cassandra's conditional put to store the roots of the DB tree.

That doesn't require lockcmpxcg (x86 CAS or whatever it's called), Cassandra just has a way of doing an atomic conditional put on a CRDT store

I mean, I can implement a little web service that has no parallelism at all within its implementation, and it implements a 'compare and swap' service that many clients could use, and it wouldn't need a CAS instruction on a chip, but it would implement that feature for its clients.

exactly

And if your clients used an immutable store, they could store the GUID for the root node in your service

In his "Are We There Yet" talk, he uses the term "CAS timeline", e.g. here: "You can use CAS, which is essentially saying there’s one timeline per identity. Right? And it’s uncoordinated. It’s impossible to coordinate two things that are using CAS timelines, but CAS timelines are still useful."

My guess is that means something like "the causal sequential ordering you can see, after an execution occurs, that is the order that multiple threads CAS operations (or something like it, e.g. atom swap! operations) successfully complete.

I took it to mean that you can't do two swap! calls and guarantee consistency between two atoms.

At least not without a outside communication point (like a lock of some sort)

That makes sense, but it is the "CAS timeline" part that I haven't seen described elsewhere, and was trying to clarify what he means by that term.

yeah, and that's a phrase I've never heard before 😐

so I'd assume it's what you say, the succession of values seen by a location being updated via cas.

But I guess that makes sense, CAS has a form of time. Update 1, Update 2, Update 3. That timeline is unique to that "cell" of memory.

Yeah, that seems to fit the way he is using it there.

On the STM note, Intel Processors used to have HTM, that worked a lot like Clojure's STM. And it'd roll back any changes if someone touched the data you were working on. Sadly it had so many bugs it was disabled for future work. AFAIK it's still disabled.

him, maybe they fixed it: https://en.wikipedia.org/wiki/Transactional_Synchronization_Extensions

That definitely sounds like the kind of thing that is a few steps beyond what I would recommend putting in specialized hardware.

because of the difficulty of getting it right.

I'm recalling a paper that basically described that synchronizing multiple individual values, each on their own timeline, was irreducible; I think that was back when reading up on vector clocks?

Programming Erlang: Software for a concurrent world Is on the clojure reading list. Does reading that book give perspective that's useful for clojure developers?

it's quite dated

personally I enjoyed "Designing for Scalability with Erlang/OTP"

I understand the erlang VM still has pretty efficient CSP to this day. Anything to gleam there?

Is the O'Reily book better than hearing it from Armstrong himself?

Yes, that book I mentioned is written by also reliable/knowledgeable authors, and it's certainly more up to date

I didn't read the one you mentioned but it seems more about the basics

actually I read it 🙂, I have the second edition, was fooled by the different cover

Erlang does actor based programming, not CSP

yes, totally different

Erlang is great at what it does, but most of the criticisms here are well founded: https://clojure.org/about/state#actors

it's not to be used in the same situations I guess

rh said it himself indirectly recently in one of his talks, you prolly wouldn't use clojure to write "phone switches"

even tho it's arguable, the memory model is so different, both have strength/weaknesses

Oh that's a really nice read

If I'm undestanding correctly, an important disadvantage to consider is that you lose the ability to throw something on a channel and stop caring about what happens to it, which is a form of complexity

agreed, CSP doesn't work over networks, as you need locks and the like

actors aren't needed as much when you have a shared memory model with locks

OTP is 😘👌 though

@radomski That's true. Also, actors require a message to be sent in order to deref the actor. That's another cause of complexity

But on the other end, your messaging is complected with locality with CSP from what I'm gleaming

So the golden rule of everything is a tradeoff

csp makes backpressure/flow control easy

in erlang you have to build that yourself since mailboxes are unbounded

As I've heard Rich say several times: "The first thing people do with Erlang is build a distributed queue".

easy to get into weird territory

A distributed que sounds like a good middle ground to an outsider

There's a lot of truth in that ^. I've never reached for Erlang simply because stuff like Tibco, Rabbit and Kafka exist.

elixir has a few "behaviors" to fix that, or in erlang you have to use credit flow control and such

Elixir is cool for what it does, back when I did Erlang all we had was the prolog syntax. Now I love me some prolog, but dang Erlang code is ugly.

We don't have a centrally used actors library correct?

Prolog is extremely cool

I kinda like it's syntax, it's simple. elixir if full of macros

@radomski that's correct. Pulsar is about the closest Iv'e seen. Although I think Akka works just fine with Clojure as well.

There's also a lot of confusion about what actors are. Erlang takes a rather loose view of actors

Notice that Erlang does a ton of stuff not mentioned here: https://en.wikipedia.org/wiki/Actor_model#Fundamental_concepts

I am understanding in terms of channels. Sort of a two way chennel with required locking

but there's no per actor gc in akka/pulsar right?

@mpenet correct, that's a big reason why Erlang is better at these sort of things.

yes, that's the big selling point of erlang imho

well, of BEAM

not many platforms have this

@radomski eh...CSP channels are a many-to-many queue with an optional buffer. Each message is delivered exactly once. If the channel doesn't have a buffer the channel works as a handoff between two threads.

Guaranteed delivery as well, so if you don't have a buffer, and a put succeeds, you know another thread has the message.

I understand that, but I'm still trying to grock actors

It looks like actors need a reference to eachother

This definition is my favorite.

An actor is a computational entity that, in response to a message it receives, can concurrently: send a finite number of messages to other actors; create a finite number of new actors; designate the behavior to be used for the next message it receives. There is no assumed sequence to the above actions and they could be carried out in parallel.

@radomski they need a name, to send to, in many situations this is nothing more than a id

That's actually the one I'm staring at right now funny enough

Excellent discussion here, by one of the inventors of Actors systems, and the inventors of a few other languages: https://channel9.msdn.com/Shows/Going+Deep/Hewitt-Meijer-and-Szyperski-The-Actor-Model-everything-you-wanted-to-know-but-were-afraid-to-ask

When I send a message, I will always expect one back or there will be a failure?

The low level send primitive has no hard guarantees. You have to build ACK in your protocols. OTP gives you some of those though.

The thing is, you don’t know if the process you’re sending the message to is local or remote or across the network. Hence the uniformity of no guarantees.

In practice, most people model with “generic servers” which OTP provide which have to acknowledge messages within a time out (default is 5s).

Of course, this means that calling code effectively blocks waiting for the response to come back. This works well if you had to block anyway, e.g. reading from a database in order to proceed.

The way failures work is by declaring dependency trees between processes. If a process that you depend on dies (or becomes inaccessible), you get notified and most often propagate the crash upwards until someone restarts the whole tree.

Fault tolerance + decomplecting with locality seems like 2 big pluses. I think I'm starting to understand why the model doesn't have core support though

https://github.com/onyx-platform/onyx and then I see this and want to play around with it

@tbaldridge cool lisp-in-x vid, can’t wait for the next one