On May 24, 10:51 am, Rich Hickey <richhic
...@gmail.com> wrote:
> I agree that identifying the things that can change is one key issue,
> and Clojure's Refs, Agents, and Vars all do that. But I think a large
> number of your arguments reflect a lack of understanding of how (at
> least Clojure's) STM works.
> Refs are not merely markers, they do enforcement. There is simply no
> mutating a ref outside of a transaction - it's not an allowed mistake.
> Any attempt to change a ref outside a transaction throws an exception.
> So, there is no such thing as "transaction regions don't cover all the
> variables they need to" in Clojure.
Alas - there still is. :-(
Example down below, and this is my primary complaint against both
locks & STM.
However, your other arguments are more quickly answered - mostly
because I agree with you.
> Your thought exercise with a single lock is a good one. Let's say
> Clojure's implementation of STM used a single global lock (in fact it
> has no global locks at all), and contrast it with a manual locking
> program that used a single lock for everything.
> Which is more correct? The Clojure one, because it is not subject to
> undetected 'forgetting to obtain the lock'. Your assertion that
> "Suppose I can get a correct program using STM - then I also have a
> correct program using a single global lock" implies nothing about
> programs written with a single manual lock where no STM system is
> helping ensure correctness. All Clojure STM programs (that don't throw
> Ref mutation out-of-transaction exceptions) are correct with a global
> lock, but not all programs using a global lock (that don't throw
> exceptions) are correct STM (or otherwise) programs.
Good one. I agree. Clojure wins this round.
> Which one is has better performance? Constant factors aside,
> potentially the Clojure one, because readers do not wait for writers
> in MVCC.
Not really relevant; nobody writes the 'single global lock' version,
including Clojure.
It was just a thought exercise.
> As we add locks, performance of both approaches improves, but a new
> source of errors comes into play for the manual approach - lock
> acquisition order and the resultant deadlock risk. At this point STM
> becomes dramatically less complex than manual locking.
Not interesting *in practice*. Because in practice, deadlocks are
easy to find & fix.
You get a crash dump, crawl the stacks, discover the lock cycle &
reorganize.
Sure the situation could be better, but deadlocks are a 'crash once'
kind of bug.
Dev's don't like 'em, but they don't lose sleep over them either.
> I'll grant that it is likely that, in the hands of experts, it is
> possible to write a correct program with a custom crafted locking
> strategy that will outperform any general-purpose STM strategy. But I
> still contend that, for any moderately complex program, that strategy
> will approach the complexity of an STM, and that most people will get
> it wrong in subtle, intractable ways.
> Analogies to databases are telling. DBMS's took over locking long ago
> and most people were happy to have them do so. Ditto memory management
> and GC. In each case, people claimed superior control and performance
> in the manual solution, but the cost and complexity proved too high
> for most applications.
Actually, I was thinking of the compiler-vs-ASM analogy that took
place in the 60's & 70's. But point well taken: I agree that we need
*some* kind of support here. Maybe in the very long run STM runtimes
get better & STM does win. Meanwhile life sucks. If you can only
solve the problem with STM's I'll point out below then I'll agree with
you, and maybe even try my hand at an STM implementation.
> So, mutable entity identification is a problem, but it is a subproblem
> of correctness enforcement. It is likely that, given well-identified
> sharable entities, some form of static correctness analysis might be
> brought to bear on the manual locking case, and I'm sure people are
> working on that. STMs can provide correctness enforcement today, and
> therefore the two are not equivalent. Any opacity in STM operation or
> performance is an area for improvement, not necessarily a reason for
> avoidance.
> Rich
Ok, the long sought after counter example.: STM's do not compose w/
correctness.
Bad Java syntax follows, because I don't 'speak' Clojure. I'm using
the classic example.
class Account {
long _money;
add( long m ) { atomic { _money = _money + m; } }
}
transfer( Account a1, Account a2, long m ) {
a1.add( m);
a2.add(-m);
}
While 'add' alone is STM'd & safe, the two calls to 'add' that need to
be wrapped in an 'atomic' are not - so there is a race where the
accounts do not balance. Deciding at what level to add the next
'atomic' (should it be around 'transfer' or at a higher level or not
at all?) demands the programmer have domain knowledge not already
encapsulated in the Account class. THIS is the source of vast numbers
of bugs.
Less trivial examples quickly spiral out of control. Sure I know
Ref's A, B & C are all Ref's and thus only updated in 'dosync' blocks
- but can I split any collection of Ref updates into more than one
atomic region? The ad-absurdum answer is to wrap a dosync around
*all* Ref's - which means the whole program, and that means a single-
threaded program. Imagine the program unrolled in front of you, as an
endless sequence of actions (all control flow flattened out)...
interspersed with other actions are updates to Ref's. Now: dissect
this list into groups with 'atomic' or 'lock' as you see fit,
preserving the program meaning as another unrolled thread of execution
is interspersed. How do you decide where it's OK to split the stream
and where it's not OK?
Why, in the Grand Scheme of things is: "... { read _money ... write
_money } ... " a correct splitting of the action stream,
while "... { read _money ... write _money } ... { read _money ...
write _money } ..." is broken,
but "... {{ read _money ... write _money } ... { read _money ... write
_money }} ..." is correct again?
Cliff
> On May 24, 8:11 am, cliffc <cli...@acm.org> wrote:
> > The problem with manual locking - and it applies equally well to
> > transactions - is that the there's no name-space-control over what
> > needs to be locked/transacted. The failure people have with locks
> > (and limited experience with transactions) is that they can't properly
> > name their shared variables. They *think* they can, until we start
> > looking hard, and then we keep finding more... and more that need to
> > be locked/transacted atomically. In short, people don't know where to
> > put the lock/unlock or where to bound the transactional region.
> > Having said that, locks have some advantages over transactions:
> > transparent performance being one of them.
> > Programs are busted if the locks are wrong (or transaction regions
> > don't cover all the variables they need to; Clojure isn't immune here)
> > AND they are busted if performance sucks. For 2-4 way machines the
> > issue is probably moot; for 8-32 way machines (standard servers these
> > days) - it matters. In a year every el-cheapo linux blade server out
> > there will be looking at 16-64 cpus. And of course for Azul, 100+
> > active cpus is the norm. I claim that in a year, most people will
> > either care (get bit by lack of scaling), or see that their need to
> > care within another year.
> > Requiring shared variables to have a special syntax, ala Ref, is a big
> > step forward here for both locks & transactions. You're reducing the
> > complexity of the problem via name-space control (only Ref's are
> > shared) and promoting immutable shared state. The STM issue is
> > orthogonal.
> > As evidence of that, suppose you replace your STM implementation with
> > a trivial single global lock. Are the programs more or less complex
> > than their locking counterparts? The program is as-correct and as-
> > complex as before (before you swap the STM implementation), and indeed
> > is exactly equal to the locking solution using a single global lock.
> > Suppose I can get a correct program using STM - then I also have a
> > correct program using a single global lock. STM only varies from
> > locking as I try to make the implementation more performant: for the
> > STM I trust the language implementor to "stripe" the locks under the
> > hood. For locks, I start using more than one lock. In both cases I
> > can also try to shrink the lock-hold-time (or reduce the size of the
> > STM region), or switch algorithms.
> > Summary: STM doesn't solve the Big Problem (lack of name-space
> > control). Ref's might solve the Big Problem - and solving the Big
> > Problem will be a big help to both locks & STM. Locks have
> > transparent performance and are thus easy to optimize. Optimizing
> > without good name-space control is a buggy process for both locks &
> > STM. I don't know how to optimize an STM implementation without
> > becoming an expert in the particulars of the STM runtime (and there
> > are so many to choose from!)
> > Cliff
> > On May 23, 6:00 pm, Rich Hickey <richhic...@gmail.com> wrote:
> > > One could as generically argue that systems with manual locking are
> > > usually broken, and therefore their behavior itself, never mind their
> > > performance, is unpredictable. That's been my experience with manual
> > > locking in the hands of mere mortal developers. It can be as difficult
> > > to understand the behavior of any single manually-concurrent program
> > > as to understand the performance characteristics of an STM. In the
> > > latter case, at least the STM is handling correctness for you, and all
> > > users of the same STM can share knowledge (and bug fixes and
> > > performance improvements), vs each application being its own Gordian
> > > knot. And in any case in which the STM is failing you performance-
> > > wise, you can opt out and use manual locks outside of transactions. To
> > > the extent you can use it, STM can drastically reduce the complexity
> > > of a system.
> > > I'm wary of unifying the discussion of concurrency with one about
> > > performance, as the problems of concurrency start with correctness,
> > > where the manual locking story, due to its complexity, is quite bad.
> > > Scalability is not a universal problem - some systems need to handle
> > > thousands of simultaneous connections - most don't, some need to
> > > leverage hundreds of CPUs in a single application - most don't. But
> > > every application that wants to leverage multiple cores needs to be
> > > correct.
> > > It would be no problem to instrument the Clojure STM references with
> > > fault counters that would allow one to know the exact per-reference
> > > contention level. Once known, the answers in both cases are similar -
> > > share less mutable state, don't have both long and short-lived
> > > transactions contend for the same data, check your success conditions
> > > ASAP etc.
> > > STM designs differ from one another quite a bit, so any general
> > > statements are difficult to assess. I think the level of granularity
> > > of the STM comes into play. Most of the STM papers I've read
> > > concentrate on creating lots of transactional cells with which they
> > > envision constructing concurrent data structures like the ones in
> > > java.util.concurrent. I don't think that's a good idea at all.
> > > Clojure encourages the use of immutable persistent data structures,
> > > which need no locking or coordination whatsoever in order to perform
> > > correctly in a concurrent situation, and STM references to support the
> > > appearance of identity-preserving change. It also encourages the use
> > > of java.util.concurrent and the like for caches and work queues - the
> > > best tools for the job.
> > > As far as I know, Clojure is the first STM that uses snapshot MVCC,
> > > avoiding both read logging and transaction restarts due to read
> > > invalidations. Clojure's STM also gives you the ability to 'ensure' a
> > > reference you later intend to read or write, thus providing some
> > > manual control over resource acquisition order (rather than just
> > > relying on the side effect of access). It also supports explicit
> > > commute, further reducing retries for commutative writes. I'll not
> > > claim its performance characteristics are at all proven, but its
> > > contention due to, and for, reading is lower than in programs that use
> > > manual locking, and lower than in STMs in which write transactions can
> > > cause read transactions to retry.
> > > Once you get to record-level STM granularity, like Clojure's, it's
> > > also a bit easier to draw parallels to the performance characteristics
> > > of the database systems it mimics, which have been doing similar
> > > things for decades.
> > > I don't consider STM performance any more or less of a research
> > > problem than determining the correctness of programs that do manual
> > > locking - there's still work to do.
> > > And of course, neither STM, nor any other mechanism, is
> ...
> read more »
