Can dosync transaction result computation be parallelized over multiple threads?
Andy Fingerhut
thread, and then that function calls other functions (which might have
their own dosyncs, which get bundled together with the original
transaction), then everything is fine. It seems common that all of
that work would be done sequentially, in a single thread.
But what if that thread that started the dosync did a pmap call, say,
and the function called on each of the elements of the collection
accessed Refs, and perhaps computed new values for some of them, and
those were not the same Refs that the original thread was accessing.
Do all of those get bundled together with the original transaction,
too?
If so, did it require anything special in the implementation to make
that work?
Thanks,
Andy
Chas Emerick
> thread, and then that function calls other functions (which might have
> their own dosyncs, which get bundled together with the original
> transaction), then everything is fine. It seems common that all of
> that work would be done sequentially, in a single thread.
>
> But what if that thread that started the dosync did a pmap call, say,
> and the function called on each of the elements of the collection
> accessed Refs, and perhaps computed new values for some of them, and
> those were not the same Refs that the original thread was accessing.
> Do all of those get bundled together with the original transaction,
> too?
Andy,
No -- absent some var/binding gymnastics (which are currently possible
but not very straightforward to do at the moment) -- a transaction is
associated with a single thread, period.
If your pmap call happens to initialize other transactions on other
threads, those transactions will be completed completely independently
of any transaction that may be in flight that initiated the pmap call
itself (or send or send-off or future, or whatever other asynchronous
mechanism at play).
That said, I would urge caution in circumstances like what you've
described. While you say that the refs being accessed in the other
threads' transactions aren't the same as the refs being accessed in
the parent transaction, you'll be in for some unpleasantness if that
ceases to be true at some point. e.g. the "child" transactions will
see the original value of any refs changed so far in the "parent"
transaction, the parent will not see any changes made to those refs by
the child transactions, and if a parent transaction is waiting on a
value being returned by a child transaction, and they both ensure or
ref-set or alter the same ref, then you're likely in for a deadlock.
> If so, did it require anything special in the implementation to make
> that work?
Migrating transactions across thread boundaries *is* possible by
judiciously copying thread-local bindings from one thread to another.
There is a low-level API on clojure.lang.Var, etc. for doing this, but
it's by no means pretty -- which I think is probably a good sign that
doing so is fundamentally a bad idea at the moment.
If and until a better approach is available, I'd say the best approach
would be to ensure that only *values* are going into your pmap calls
(as opposed to refs), as that's the only way to ensure that you're not
going to get tripped up by the thread-local nature of transactions.
I've done just the opposite in the recent past, and the result was a
lot of confusion and frustration, which ended up being part of
learning a lesson the hard way. :-/
Cheers,
- Chas
Meikel Brandmeyer
On Aug 13, 11:58 am, Chas Emerick <cemer...@snowtide.com> wrote:
> That said, I would urge caution in circumstances like what you've
> described.
Rich recommended that before. If possible, don't do
complicated calculations inside a transaction.
Sincerely
Meikel
Mark Volkmann
Above you say "if ... they both ensure or ref-set or alter the same
ref". I don't believe that can happen. Once one thread is successful
in doing an ensure, ref-set or alter to a given Ref, that Ref is
marked as having gotten a new in-transaction value in that transaction
(the tinfo field of the Ref object gets set). This happens before the
transaction commits. If another thread tries to do the same then
either it or the original transaction is going to retry. I don't
believe there is a possibility for deadlock here.
Hold on! There was a recent change in LockingTransaction.java that may
have made what I said above not exactly true! The LockingTransaction
lock method is what sets the tinfo field of a Ref. Previously the lock
method was called for an ensure, ref-set or alter. In the new version
it seems that lock is only called for ref-set and alter. Can someone
in the know confirm that this is the intended behavior? It seems that
with this change it is now possible for more than one thread to ensure
the same Ref as long as no thread has yet done a ref-set or alter on
the Ref.
--
R. Mark Volkmann
Object Computing, Inc.
Mark Volkmann
I just studied this further. Before the recent changes to
LockingTransaction.java, only one thread at a time could ensure a
given Ref. With the changes, any number of threads can ensure the same
Ref.
A key thing to know about this is that Ref.java uses a
ReentrantReadWriteLock. Each Ref has an associated
ReentrantReadWriteLock object. Those allow any number of threads to
simultaneously hold a read lock OR a single thread to hold a write
lock.
All the threads that have called ensure on the Ref hold a read lock
for it. If one of them later tries to write to the Ref (by calling
ref-set or alter on it), it will release the read lock it holds for
the Ref and attempt to get a write lock for it. If other threads still
hold that read lock, this attempt will fail and the transaction will
retry.
So it seems the biggest impact of the change can be summarized as
follows. In the past, once you successfully ensured a Ref, you knew
you could write to it later because no other thread could also ensure
it. Now you don't know that. You know you can stop other threads from
writing the Ref, but you won't be able to write the Ref as long as
other threads have also ensured it.
I'm not criticizing the change. There were likely good reasons for it.
Please let me know if I have interpreted anything incorrectly.
Chas Emerick
On Aug 14, 2009, at 8:53 PM, Mark Volkmann wrote:
> So it seems the biggest impact of the change can be summarized as
> follows. In the past, once you successfully ensured a Ref, you knew
> you could write to it later because no other thread could also ensure
> it. Now you don't know that. You know you can stop other threads from
> writing the Ref, but you won't be able to write the Ref as long as
> other threads have also ensured it.
>
> I'm not criticizing the change. There were likely good reasons for it.
>
> Please let me know if I have interpreted anything incorrectly.
Totally aside from the correctness of that analysis (which I've no
reason to doubt a.t.m.), I just want to clarify that I never actually
encountered any deadlocks (though I absolutely did burn a bunch of
cycles trying to figure out why some fn was seeing old values in
certain refs...due to the fn being involved in a pmap over a series of
objects that contained refs).
- Chas
Rich Hickey
While I appreciate that you are trying to understand the
implementation of the STM, understanding the semantics of the STM in
terms of its implementation is wrong-way-around.
The semantics are simpler, and the implementation is subject to
change. Retries will occur as needed to ensure the semantics, and no
one should be thinking in terms of "if I do this and another
transaction does that..." or read and write locks etc.
Rich
Mark Volkmann
>
> While I appreciate that you are trying to understand the
> implementation of the STM, understanding the semantics of the STM in
> terms of its implementation is wrong-way-around.
>
> The semantics are simpler, and the implementation is subject to
> change. Retries will occur as needed to ensure the semantics, and no
> one should be thinking in terms of "if I do this and another
> transaction does that..." or read and write locks etc.
I agree in general, but I think there are many reasons that a person
might want to understand what is happening under the covers. Here are
some of them.
1) learn interesting things from the design of Clojure STM
2) understand it well enough to become convinced that it works as advertised
3) implement STM for some other programming language using ideas
borrowed from the Clojure implementation
4) understand it well enough to be able to suggest improvements to it
5) understand it well enough to help with adding tool support (such as
tracking the number of times a transaction retries and why it retries
in order to tune usage)
If feel like I understand commute and ensure much better after
studying the code in LockingTransaction.java.
