> Time is a slippery notion in concurrency. Most language-level memory models (e.g. Java) or even hardware-level concurrency models focus on happens-before relations, which are induced by executing certain operations

You are correct, but for simplicity we can assume that the CPU executes one operation at a time and still have a valid model for reasoning about data races.

> But ultimately, all inter-thread communication boils down to programs (or libraries) using barriers for acquire/release semantics and/or using compare/swap and atomic read-modify-write.

Interesting. I read about STM and it reminded me of "modification box" algorithm for modifying immutable trees, which also uses versions. So it is another clever but complicated trick. Also it seems that it requires locking? That's not very good given that locks often need syscalls.

▲

titzer 4 days ago | parent | next [-]

> Also it seems that it requires locking? That's not very good given that locks often need syscalls.

AFAIU in most STMs all the fast paths are implemented using lock-free algorithms with just barriers.

▲

codedokode 4 days ago | parent [-]

How do you implement "commit" part safely (writing changes to the object) without locking the object?

▲

titzer 4 days ago | parent [-]

One way is that the writer thread prepares a completely new copy of the object in a private area and then either compare-and-swaps a pointer to it, or executes a store with a store-store barrier (depending on details of the STM system around it).

	▲	codedokode 4 days ago \| parent [-]
		Interesting, it's almost like immutable data structures.

▲

mrkeen 4 days ago | parent | prev [-]

> Also it seems that it requires locking?

STM requires locking in the same way that GC requires malloc. It gets it right so that the programmer doesn't mess it up.

	▲	astrange 4 days ago \| parent [-]
		A non-compacting GC still needs a good malloc because it needs to avoid heap fragmentation.