Re: request for advice: safepoints in the JSR 292 spec
On Dec 15, 2010, at 1:31 AM, John Rose wrote: > On Dec 13, 2010, at 12:19 AM, Rémi Forax wrote: >> On 12/12/2010 05:02 PM, Rich Hickey wrote: >>> Rémi's synchronized block only coordinates the activities of >>> updaters. >>> Other threads may, and in some cases may have to, see some of the >>> setTarget results prior to the sync call, which could be a mess. The >>> point of syncTargets is to make the setting and the visibility >>> atomic, >>> which synchronized cannot do. > > Yes, syncTargets would be very powerful. But it would also be hard to > require of all JVMs. Speaking only for HotSpot, we don't do > everything > with safepoints, because they are expensive. We use racy updates > whenever we can get away with it. The cost of a racy update is the > co-existence of two states, unpredictably visible to various threads. > I think that's a normal complexity cost for doing good language > implementations. > > I think mapping a global atomic update to the JMM would require > more "magic edges" in the happens-before graph. The proposal > I posted, while weaker, has a correspondingly simpler impact on > the JMM. This is another way of observing that JVMs are likely to > have an easier time of adding the proposed functionality. > > So a globally atomic update is harder to implement and harder > to specify. It is also overkill for a common use case, which is > delayed optimization of call sites. See below... > >> Rich, >> I don't think you can provide an optimized method handle when >> syncing but >> more probably a default generic method that will later installs a >> fast path. > > Thanks, Remi, for explaining this. I'm going to pile on here. > > (I have one comment on your code; see below.) > > I think of the pattern Remi sketches as a 2-phase commit. > > Phase 0 and phase 2 are long-term phases. Phase 1 is brief but not > atomic. > > Phase 0 is the reign of the old target T0, before any MCS.setTarget. > > Phase 1 starts when metadata locks are grabbed. > Under the locks, MCS.setTarget installs a default generic method T1. > (This is analogous to the JVM trick of setting a call site to the > "unlinked" state.) > > T1 is not racy. It is careful to grab a reader lock on metadata. > It is likely to install an optimized method T2, via a simple > setTarget. > This may happen after an invocation count, or after user-level > profiling. > (Therefore, it does not make sense to try to guess at T2 during > phase 1.) > > The MCS.sync operation is performed during phase 1, after all > relevant setTargets are done. It has the effect of excluding threads > from observing target T0. (I.e., it "flushes" T0 from the system.) > > Phase 2 starts when metadata locks are released. During phase 2, > individual threads eventually execute T1. T1 lazily decides to > install T2. > (Or several equivalent versions of T2.) > > Threads which observe T1 (because of caching or inlining) will perform > sync actions which will force them to observe more recent call site > targets. > > During phase 0, T2 cannot be observed. During phase2, T0 cannot be > observed. > The intermediate target T1 can be observed during any phase. > > Compare that with Rich's proposed atomic syncTargets operation, > which would exclude phase 1 and target T1, for better and worse. > > Another way of comparing syncTargets with setTarget+sync is > simply to syncTargets excludes target T1 from phase 0, whereas > the weaker proposal does not exclude T1. > > This weakness can also be described in terms of two reader > threads, a Fast Reader and a Slow Reader. The Fast Reader > sees the result of the writer's setTarget of T1 in the same > nanosecond. The Slow Reader sees only T0 until it is > forced to pick up T1 by the sync operation. > > This API has several presumptions: - There is some singular global metadata. - It is protected by a lock. What if it is an immutable structure in an AtomicReference and modified via CAS? Or passed by value to targets/ handles? - Call sites will always use a two-phase update, i.e. they will need to rediscover their binding vs directly target it (during metadata update) given their cached data and the new metadata. You are piggybacking on this presumption to provide a consistency hook (blocking on the read lock). While T1 is not strictly MT racy (given the adoption of this pattern wholesale), it is prone to error, in that should the update phase interleave ordinary code and setTarget calls, it can see an inconsistent state (i.e. nothing keeps call sites the update thread encounters from moving to T1.5 prior to the sync call, since the updater thread holds the lock). Many dynamic language implementations use their own dynamic code in a way that could trip over this. This is an API that only works correctly given an extremely constrained pattern of use. That's fine, if unfortunate, but needs to go in the docs I think. It is essential that the pattern be - grab the
Re: [jvm-l] Re: request for advice: safepoints in the JSR 292 spec
On Dec 15, 2010, at 7:04 AM, Rémi Forax wrote:
>>> default generic method (reader):
>>> synchonized(masterLock) {
>>> // check arguments
>>> // use meta data to create a fast path
>>> }
>> (This next line should also be synchronized. -- JRR)
>>
>>> setTarget(guard + fastpath);
>
> Correct me if I'm wrong.
> Le last line can be in the synchronized block but it don't have to.
> The JMM guarantees that the current thread will see the new target (T2).
> Other threads can see T1 and in that case will update to a T2' which is
> semantically equivalent to T2.
> It's a racy update.
Racy updates have the risk of not getting picked up by Slow Reader threads.
But, as you point out, in this case T1 synchronizes any Slow Reader and forces
him to see T2.
So, you're right.
I guess the principle is that racy updates are OK as long as the previous state
(T1) is allowed and will eventually force all readers to go to the new state
(T2).
-- John
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
Re: [jvm-l] Re: request for advice: safepoints in the JSR 292 spec
On Dec 15, 2010, at 3:08 PM, John Rose wrote:
> On Dec 15, 2010, at 7:04 AM, Rémi Forax wrote:
>
default generic method (reader):
synchonized(masterLock) {
// check arguments
// use meta data to create a fast path
}
>>> (This next line should also be synchronized. -- JRR)
>>>
setTarget(guard + fastpath);
>>
>> Correct me if I'm wrong.
>> Le last line can be in the synchronized block but it don't have to.
>> The JMM guarantees that the current thread will see the new target
>> (T2).
>> Other threads can see T1 and in that case will update to a T2'
>> which is
>> semantically equivalent to T2.
>> It's a racy update.
>
> Racy updates have the risk of not getting picked up by Slow Reader
> threads.
>
> But, as you point out, in this case T1 synchronizes any Slow Reader
> and forces him to see T2.
>
> So, you're right.
>
> I guess the principle is that racy updates are OK as long as the
> previous state (T1) is allowed and will eventually force all readers
> to go to the new state (T2).
>
Why can't T3 happen between the synchronized block and the setUpdate
call, and get overwritten with a T1-based decision?
Rich
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
Re: [jvm-l] Re: request for advice: safepoints in the JSR 292 spec
On 12/15/2010 10:03 PM, Rich Hickey wrote:
>
> On Dec 15, 2010, at 3:08 PM, John Rose wrote:
>
>> On Dec 15, 2010, at 7:04 AM, Rémi Forax wrote:
>>
> default generic method (reader):
> synchonized(masterLock) {
> // check arguments
> // use meta data to create a fast path
> }
(This next line should also be synchronized. -- JRR)
> setTarget(guard + fastpath);
>>>
>>> Correct me if I'm wrong.
>>> Le last line can be in the synchronized block but it don't have to.
>>> The JMM guarantees that the current thread will see the new target
>>> (T2).
>>> Other threads can see T1 and in that case will update to a T2' which is
>>> semantically equivalent to T2.
>>> It's a racy update.
>>
>> Racy updates have the risk of not getting picked up by Slow Reader
>> threads.
>>
>> But, as you point out, in this case T1 synchronizes any Slow Reader
>> and forces him to see T2.
>>
>> So, you're right.
>>
>> I guess the principle is that racy updates are OK as long as the
>> previous state (T1) is allowed and will eventually force all readers
>> to go to the new state (T2).
>>
>
> Why can't T3 happen between the synchronized block and the setUpdate
> call, and get overwritten with a T1-based decision?
>
> Rich
>
It can. I was wrong.
setTarget() has to be in the synchronized block.
Rémi
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
Re: [jvm-l] Re: request for advice: safepoints in the JSR 292 spec
On Dec 15, 2010, at 2:27 PM, Rémi Forax wrote: >> Why can't T3 happen between the synchronized block and the setUpdate call, >> and get overwritten with a T1-based decision? >> >> Rich >> > > It can. I was wrong. > setTarget() has to be in the synchronized block. Foo; I agree. The T1 update can float into the far future and screw things up (overwriting T3). In our EG meeting this morning we decided to provide better usage guides in the javadoc. Rich, I'm going to think a while about your alternative proposal of syncTargets and swapTarget: On Dec 15, 2010, at 9:22 AM, Rich Hickey wrote: > The benefits of syncTargets and swapTarget from an API perspective are that, > given appropriate regard for the expense of syncTargets - you can't get it > wrong, the API itself delivers the coordination semantics, there is no > elaborate pattern to replicate, and the field of use is broader. Quick responses: SyncTargets would be a true global atomic transaction, with barriers in both directions to floating reads and writes. If you were willing to update the targets one at a time, but still wanted two-way barriers, you could use VolatileCallSite, and file a performance bug for JVMs to optimize the case of a stable volatile. The CAS idea does not translate well to function pointers, because they are necessarily opaque. (Function equivalence is undecidable...) The Object.equals method on them is pretty meaningless. I think you would need a double-CAS of some sort, which replaced a pair with a new version. I think I need a better understanding of how STM techniques are implemented on a generic JVM, and what the pain points are. -- John ___ mlvm-dev mailing list mlvm-dev@openjdk.java.net http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
