testing + debugging concurrency?
Raoul Duke
for dupes for folks on both.) this can be a wider-than-just-clojure
question, i'd very much appreciate pointers to papers, theory, etc.
how does one actually test concurrency (and then debug it)? like, how
can you write tests which claim to have "coverage" of the possible
interleavings?
thanks.
Rich Hickey
coverage of the interleavings, as in a real MT run the interleavings
are non-deterministic.
Most traditional concurrent programs satisfy themselves of their
correctness by some analysis of their locking strategy. When using
Clojure as designed, you are relying on my analysis of Clojure's STM
and Agents.
As far as agents, there is no interleaving, the execution strategy is -
> all operations are atomic. Agent actions cannot nest (i.e. the send
calls can nest, but the executions don't)
With the Refs and STM, the interleavings can become arbitrarily
complex and you shouldn't care. What matters is the degree of
contention, driven by the number of overlapping refs in any set of
transactions. This is something you can control by correct
partitioning of your data/logic, and setting appropriate transaction
sizes. You can do this with the knowledge that any transactions that
have no written-to refs in common don't interact.
Rich
Raoul Duke
Many thanks for the note.
> coverage of the interleavings, as in a real MT run the interleavings
> are non-deterministic.
> With the Refs and STM, the interleavings can become arbitrarily
> complex and you shouldn't care. What matters is the degree of
I agree that at some level it is good to be able to abstract out
caring about the issue, and that things like STM are helping the
higher levels get away from having to worry about it. And that seems
like a good thing.
But, being a devil for a moment, or just being interested in how one
robustly develops STM that for sure works, what does one do when stuck
at the level where non-determinism is something you really do have to
deal with?
I'm not expecting there to be much of a perfect answer given the fact
that testing can't prove the absence of bugs. But presumably there are
best practices / various ways / some theory about how to approach such
problems, and I wonder what those are for concurrency. Seems like the
usual things people would rely on in unit testing for single threaded
systems suddenly are nigh useless because their coverage metric
suddenly goes towards zero due to not being able to know and cover all
possible interleavings. E.g. Perhaps there are some approaches like
somehow tweaking the game and underlying rules such that you can prove
more things with more confidence, or rule things out? But then of
course you might be losing power of some sort as you do that. Do you
go for probabilistic testing? Or is there some abstract theory that
builds things from the ground up such that if converted correctly to
code really don't worry about interleavings - sorta full circle to STM
and back again to "ah but how do you really test that you converted it
to actual code correctly?" :-)
sincerely.
Christian Vest Hansen
gives you a framework for manually constructing interleavings. The
same page also have pointers to other approaches by IBM and others,
that run the test multiple times and more-or-less probablistically try
to hit a broad set of interleavings.
That said, I'm not terribly familiar with their use and value in practice.
[1]: http://www.cs.umd.edu/projects/PL/multithreadedtc/overview.html
--
Venlig hilsen / Kind regards,
Christian Vest Hansen.
Rich Hickey
code. This is an area that proves the inadequacy of testing.
Specifically re: Clojure and interleaving. As side-effects are
forbidden in transactions, the only impact of interleaving that
matters is lock acquisition order. Here's some of the reasoning behind
Clojure use of locks:
- All ref locks are grabbed atomically other than at commit. That is,
no code is called, while holding a ref lock, that could obtain another
ref lock.
- At commit time, altered refs are re-locked, having been flagged
(under the same per-ref lock) for ownership previously. These locks
are obtained after a one-try, one-way CAS state transition that would
block any other transaction looking to barge-in on (to steal ref
ownership, and abort) this one.
- Commuted refs' locks are obtained in a totally-sorted order, a known
deadlock-free method.
- All held locks are tracked, and are released in a finally block in
all code paths.
There's much more to it, but it goes along these lines.
For a simpler example, consider an application that numbers all locks,
and always takes the locks in sorted order. It is easy to reason that
such an app is deadlock-free, without testing any interleavings.
For non-STM apps, I presume there are people working on tools to
statically analyze execution paths and locking.
In the absence of any analysis, you can't trust the code.
Testing tells you very little, if anything at all.
Rich
Raoul Duke
> In the absence of any analysis, you can't trust the code.
> Testing tells you very little, if anything at all.
Analysis is important, to be sure. But there's Knuth's down-to-earth
truism "I have only proven it correct, not tested it" to be kept in
mind. I believe both analysis and testing are required before you can
get anywhere close to trusting some code. Given that, I'm interested
in hearing about theory, tools, best practices for either. For
example, taking all the locks in the same numbered order begs the
qustion how do you prove and test that a real-world system actually
does that?
There are probably as many answers to the vague question I'm asking as
there are people and systems. The thought I had in my head was "if you
are a regular single-threaded unit testing kind of person, what do you
do when you start into concurrency?" I agree that approaching
concurrency from the angle of "oh I wrote some unit tests and they
passed on my machine so ship it" is a zillion times more preposterous
in light of concurrency. So then one must move along the gamut towards
(a) tests which better take into consideration concurrency issues and
(b) even further, analysis.
Which then begs the questions of what theory and tools to check the
theory do people use? I get the impression it is all pretty academic
still, or perhaps there are non-academic tools which may be used but
they are bloody expensive. And, over all, that it will require a fair
bit of new learning and training.
If things like STM take care of it all for regular folks, I'm of
course excited about that. But unfortunately I don't yet have the good
fortune of working at that level, I have to live with regular
concurrent Java, and with people who seem to think that isn't so bad.
:-(
sincerely.
Rich Hickey
On Aug 6, 6:03 pm, "Raoul Duke" <rao...@gmail.com> wrote:
> hi Rich,
>
> > In the absence of any analysis, you can't trust the code.
> > Testing tells you very little, if anything at all.
>
> Analysis is important, to be sure. But there's Knuth's down-to-earth
> truism "I have only proven it correct, not tested it" to be kept in
> mind.
"During the past 50 years, I’ve written well over a thousand programs,
many of which have substantial size. I can’t think of even five of
those programs that would have been enhanced noticeably by parallelism
or multithreading."
> I believe both analysis and testing are required before you can
> get anywhere close to trusting some code. Given that, I'm interested
> in hearing about theory, tools, best practices for either. For
> example, taking all the locks in the same numbered order begs the
> qustion how do you prove and test that a real-world system actually
> does that?
Hopefully there's a single helper function that, given a set of
desired locks, does the sort and lock job. One thing's for sure - you
can't test for it.
There's a presumption in your question you refuse to relinquish - that
testing is useful here. I contend it isn't very useful.
>
> There are probably as many answers to the vague question I'm asking as
> there are people and systems. The thought I had in my head was "if you
> are a regular single-threaded unit testing kind of person, what do you
> do when you start into concurrency?"
difficult it is.
> I agree that approaching
> concurrency from the angle of "oh I wrote some unit tests and they
> passed on my machine so ship it" is a zillion times more preposterous
> in light of concurrency. So then one must move along the gamut towards
> (a) tests which better take into consideration concurrency issues and
> (b) even further, analysis.
>
strategy.
> Which then begs the questions of what theory and tools to check the
> theory do people use? I get the impression it is all pretty academic
> still, or perhaps there are non-academic tools which may be used but
> they are bloody expensive. And, over all, that it will require a fair
> bit of new learning and training.
>
> If things like STM take care of it all for regular folks, I'm of
> course excited about that. But unfortunately I don't yet have the good
> fortune of working at that level, I have to live with regular
> concurrent Java, and with people who seem to think that isn't so bad.
basic complexity level. Working in regular Java is even worse, as you
may not even have all mutation covered by locks in the first place.
At that point, I contend any single moderately complex application's
locking strategy is going to be as involved as Clojure's STM, or any
similar one, but substantially less regular. Placing all mutation
under a ref-like system is a huge win. Immutable data structures also
take whole chunks of code out of the scope of consideration for MT
problems.
But your question boils down to - how can we keep doing essentially
what we already do (writing imperative code and unit tests) and ensure
our programs will work well under concurrency. Clojure exists in part
because I think we can't.
Rich
Raoul Duke
many thanks for the thoughts!
> There's a presumption in your question you refuse to relinquish - that
> testing is useful here. I contend it isn't very useful.
> They are kidding themselves, IMO, at least when things go beyond some
yeah, i think i agree to a fair degree.
tho, i think there's a gamut of quality targets and expectations - it
seems to me that it must be the case that some folks don't really care
if things sometimes get 100% stuck as long as it doesn't happen
frequently and they can just reboot the sever and get another week
before it gets stuck. (it is scary when those people are even
developers, themselves, i'd expect them to know/desire better.)
> But your question boils down to - how can we keep doing essentially
> what we already do (writing imperative code and unit tests) and ensure
> our programs will work well under concurrency. Clojure exists in part
> because I think we can't.
Personally I don't really want to keep doing things the old way,
believe it or not. I didn't mean to imply that I think only imperative
approaches with unit testing are useful. I am just trying to find out
what other people's experience / thoughts are.
We probably differ in how much value we attach to the nebulous concept
of testing wrt concurrency; Even if somebody smart has really great
analysis, w/out tests I'll be skeptical of there not being bugs which
perhaps could have been unearthed via some sort of testing approach.
There is plenty of room for semantics around what the idea of
"testing" means, and I suspect that you believe in at least some basic
level of testing even for concurrency. Like, you do run your code
through an actual compiler not just to get bytecode out, but to find
errors - sometimes even ones which might impact concurrency - too,
presumably. :)
sincerely.
Rich Hickey
that in this area it is decidedly limited, and that some sort of
rational lock policy, amenable to analysis and confirmation in code,
takes precedence. My experience in the field has been there's too much
ad-hoc locking with lots of testing thrown at it, which doesn't work.
Rich
cliffc
I think somebody already mentioned Bill Pugh's locking tester, but
I'll mention it again:
http://www.cs.umd.edu/projects/PL/multithreadedtc/index.html
A presentation on testing concurrent programs:
http://developers.sun.com/learning/javaoneonline/2007/pdf/TS-2220.pdf
Here's a C/Java related talk on what a data-race is, but it doesn't
cover Clojure's Ref-style coding:
http://www.azulsystems.com/events/javaone_2008/2008_DebugDataRace.pdf
A google search found lots more papers; testing-concurrent-programs is
a very active topic in the research community right now.
Some experience on testing concurrent software:
HotSpot uses lock-ranking internally. There are roughly 60 named
(unique) locks in HS, and we use asserts to check that they are
acquired in rank-order. This is followed by extensive multi-threaded
testing (weeks of heavily multi-threaded program execution on high
core-count machines), to try and get decent coverage on the asserts.
In practice, it's worked out well enough (to prevent deadlock).
We still get the periodic bug due to not covering shared-memory
changes with the correct lock.
I write concurrent Java programs fairly often, but usually of the
small micro-benchmark style. I can generally both do complete code
inspection, and guarantee total schedule coverage with a few minutes
of heavy loading on an Azul box... which doesn't help this crowd very
much. I did model-checking on my Non-Blocking HashMap; another
difficult-to-use formal technique. Not something that scales to large
numbers of developers either.
Wish I had a better answer,
Cliff