Should I avoid compareAndSet with value-based classes?

classic Classic list List threaded Threaded
101 messages Options
123456
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Alex Otenko
It’s worse than that :-)

a = d;
a.x = 1;

What is d.x?

That’s the meaning of identity.


On 6 Jul 2017, at 22:57, Gil Tene <[hidden email]> wrote:


On Jul 6, 2017, at 1:56 PM, Alex Otenko <[hidden email]> wrote:

What’s wrong with “==“ doing a sensible default thing? Like, bitwise compare the “contents”? It’s certainly no slower than calling equals() that perhaps will do more than just bitwise-compare.

Nothing "wrong" with that if we had a good specification on WHEN it means that. And "when both sides of the == are instances of value-based classes" probably doesn't cut it.

To see why, the javac compiler won't let us write:
int i = 0;
Object o = new Object();
boolean b = (o == i);
That's because int is NOT AN OBJECT.

But javac absolutely does let us write:
Object o1 = getSomeObject();
Optional o2 = getSomeOtherObject();
boolean b = (o1 == o2);
What does that == mean? What can it mean without being "surprising"?

And while it's tempting to say that here:
Optional o1 = Optional.of(objA);
Optional o2 = Optional.of(objB);
boolean b = (o1 == o2);
The == means "compare the contents". What should it mean here:
Object o1 = Optional.of(objA);
Object o2 = Optional.of(objB);
boolean b = (o1 == o2);
I suspect that the curse of being the basterd children of Object will follow instances of value based classes around for generations to come… It will be curious to see how value types deal with this same problem in an eventual working syntax. 

I see no problem here.

If the compiler has no problem finding o2's equals() method, surely it can find its “==“ method.



What’s wrong with identityHashCode producing a code based on identityHashCodes of the “contents”, or the bit contents of the primitive members?

Similarly, identityHashCode already has a meaning for Object, where it will NOT be computed based on contents. Changing that for the basterd children of Object will create all sorts of in-fighting in the family:


The ugly duckling has to have immutable “contents”, because of “what’s d.x?” - or “mutating” produces a different value, which, again, exposes its non-Object-like nature. So identityHashCode as a hash of "contents" is not an issue.


Alex

Optional o1 = Optional.of(objA);
int ihc1 = System.identityHashCode(o1);
...
Object o2 = o1;
int ihc2 = System.identityHashCode(o2);
boolean b = (ihc1 == ihc2); // Is this allowed to be False?

Alex

On 6 Jul 2017, at 20:23, Gil Tene <[hidden email]> wrote:

I think that performant runtime checks can be added. When you haven't stuffed indentity-lacking things into other things that explore identity, things will be just as fast. When you do, they will blow up, and speed won't matter.

The larger problem of "surprising behavior" when passing a non-identity-capable thing (basterd child of Object) to some thing that expects Object and does object things with it at some future point in time (like maybe using identity for something) is likely to come at us hard when "codes like a class, works like an int" value types are introduced. IMO, it is "hard" (as in impractical) to compile-time check this stuff away completely. You can cover some (many?) cases, but runtime issues will always remain. The situation where people are appalled at what can happen with instances of value-based classes that they may pass to innocent Object-expecting things is just a glimpse of the future. IMO an exception is the least bad thing you can do to them. Much better than letting their code run.

— Gil.

On Jul 6, 2017, at 11:52 AM, Brian S O'Neill <[hidden email]> wrote:

Although it would be nice to have value-based classes truly supported, because the java.time classes are defined as ordinary classes, they can never change into becoming true value-based classes without breaking compatibility. You can't just change the definition of instance equality without completely breaking the language completely. Improper use of a weak value-based class should at the very least trigger a compiler warning, but a full runtime check is too extreme.

Consider how these checks are implemented by the compiler. Adding a runtime check would be equivalent to making every == check, cas, etc behave like a virtual method call. I wouldn't be terribly happy to see a performance regression introduced in something so fundamental and used everywhere.

Also consider problems resulting an exception thrown from the == operator. This isn't supposed to happen. Any piece of code which is designed to be fault tolerant (via exception handling) is now broken, because it assumed (correctly) that fundamental language design elements don't change.


On 2017-07-06 11:15 AM, Gil Tene wrote:
David, the below is a (potentially good) argument for not allowing the creation of subclasses of Object that do not have well defined support identity, identity comparison, identity hashing, or synchronization, since Object supports all those, things that hold Object instances may very well make use of them.
But that horse has long fled the barn. We can argue that value-based classes should not have been specified in Java 8. Or that the future value types should not be derived from Object. But the first case is already in the Java spec, and the second is likely coming (and is sneakily able to use the first as a precedent).
For the "how should we specify things?" discussion, I'm actually squarely on the side of "things with no identity should never have been derived from Object" of this argument. E.g. I would advise other language specifications to avoid making the same mistake, either by not giving the base Object class identity to begin with, or by creating a separate orthogonal type hierarchy for value types and "value based" classes. However, I don't see a way to "fix" the mistake already made, and we have to deal with the language and the machine as spec'ed, not as we wish it were. And so does anyone writing code in the language.
In the context of that reality, we are discussing what correct uses of those new "basterd children of Object" are. And since the basterds clearly have no identity, using any logic that relies on identity behavior in any way is wrong.
Sent from my iPad
On Jul 6, 2017, at 10:53 AM, Gil Tene <[hidden email] <[hidden email]>> wrote:
Hence my suggestion that identity-based operations on instances of value-based classes should throw exceptions... Right now they silently do unpredictable things, and should be avoided in any case (but harder to know/find when you accidentally use them).

Sent from my iPad

On Jul 6, 2017, at 10:46 AM, Alex Otenko <[hidden email] <[hidden email]>> wrote:

Are they subclasses of Object or not? If they are not, no questions. If they are, someone still needs to explain how exactly the “identity based operations” can be avoided safely.

List<j.u.Optional> is just a List underneath, and searching for an item may use “identity based operations”, whether you want it or not - depending on what implementation of List you happen to use.

Alex

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Andrew Haley
In reply to this post by Gil Tene-2
On 06/07/17 17:33, Gil Tene wrote:

> We could further discuss whether or not the JVM is allowed to
> "falsely" indicate that == is true (or that != is false) even when
> the instances differ in value (so are not .equals()). It is.

No it isn't, unless you believe that the paragraph on value-based
classes overrides the JLS.  For it to do so, the definition of
reference equality would have to change.  Right now, all it says is
"At run time, the result of == is true if the operand values are both
null or both refer to the same object or array; otherwise, the result
is false."  I suppose you could argue that in the context of a
value-based class the notion of "same object" is vacuous, but that
would be a heck of a stretch.

> Doing that may certainly surprise anyone who uses the identity based
> == for anything to do with instances of value-based classes, even
> tho using it would be silly given that == might obviously be
> always-false. For example, I could see how someone may mistakenly
> try to use == as an "optimization" on the assumption that if they
> get lucky and == is true, .equals() must be true as well, and that
> evaluating == might be cheaper, but they would still "do the right
> thing" in the != case. But that would be a mistake, and a clear
> violation of the "don't do that" admonition above.

Frankly, I don't believe it.  Any JVM which did what you suggest would
IMO be in violation of the JLS and the JVM specification.  It is
possible that the definition of reference equality will be changed, but
that would require the incompatible specification change to be
discussed.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Should I avoid compareAndSet with value-based classes?

Andrew Haley
In reply to this post by Gil Tene-2
On 06/07/17 20:12, Gil Tene wrote:

> The answer to this is generally "But… concurrency!". Which is why
> this is an ok place to chat about it probably. With no identity, how
> do you achieve atomic updates? Michael's MutableClock example
> (scroll down) of wanting to (potentially concurrently) add duration
> amounts to some notion of a point in time, while avoiding the
> potential for "losing" an add racy situations, requires some sort of
> synchronization. Since Instant is not mutable, and we are
> necessarily trying to atomically replace one Instant value with
> another, we have a problem with the notion that these values have no
> identity (and therefore no way to do a proper CAS on).

In practice it doesn't matter, because you don't need to CAS a
reference to an Instant: all you need to do is to wrap all of the
updates to that reference in synchronized blocks.  Readers don't need
anything more than for that reference to be volatile.  The
immutability of Instant and the sequential consistency of volatile
provide all the guarantees that anyone needs or are possible.

I doubt that a synchronized block is going to perform much more badly
than spinning in a CAS loop, especially in the presence of high
contention.  In the many readers/few writers situation that Michael
describes this is the optimal solution.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Alex Otenko
No, not only updates, but reads, too.

If you assume non-atomic updates, the problem becomes just like with volatile long - has to use synchronized block for all accesses.

Alex

> On 7 Jul 2017, at 10:20, Andrew Haley <[hidden email]> wrote:
>
> On 06/07/17 20:12, Gil Tene wrote:
>
>> The answer to this is generally "But… concurrency!". Which is why
>> this is an ok place to chat about it probably. With no identity, how
>> do you achieve atomic updates? Michael's MutableClock example
>> (scroll down) of wanting to (potentially concurrently) add duration
>> amounts to some notion of a point in time, while avoiding the
>> potential for "losing" an add racy situations, requires some sort of
>> synchronization. Since Instant is not mutable, and we are
>> necessarily trying to atomically replace one Instant value with
>> another, we have a problem with the notion that these values have no
>> identity (and therefore no way to do a proper CAS on).
>
> In practice it doesn't matter, because you don't need to CAS a
> reference to an Instant: all you need to do is to wrap all of the
> updates to that reference in synchronized blocks.  Readers don't need
> anything more than for that reference to be volatile.  The
> immutability of Instant and the sequential consistency of volatile
> provide all the guarantees that anyone needs or are possible.
>
> I doubt that a synchronized block is going to perform much more badly
> than spinning in a CAS loop, especially in the presence of high
> contention.  In the many readers/few writers situation that Michael
> describes this is the optimal solution.
>
> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Alex Otenko
(of course, for platforms that don’t support atomic 64-bit writes)

Alex

> On 7 Jul 2017, at 10:23, Alex Otenko <[hidden email]> wrote:
>
> No, not only updates, but reads, too.
>
> If you assume non-atomic updates, the problem becomes just like with volatile long - has to use synchronized block for all accesses.
>
> Alex
>
>> On 7 Jul 2017, at 10:20, Andrew Haley <[hidden email]> wrote:
>>
>> On 06/07/17 20:12, Gil Tene wrote:
>>
>>> The answer to this is generally "But… concurrency!". Which is why
>>> this is an ok place to chat about it probably. With no identity, how
>>> do you achieve atomic updates? Michael's MutableClock example
>>> (scroll down) of wanting to (potentially concurrently) add duration
>>> amounts to some notion of a point in time, while avoiding the
>>> potential for "losing" an add racy situations, requires some sort of
>>> synchronization. Since Instant is not mutable, and we are
>>> necessarily trying to atomically replace one Instant value with
>>> another, we have a problem with the notion that these values have no
>>> identity (and therefore no way to do a proper CAS on).
>>
>> In practice it doesn't matter, because you don't need to CAS a
>> reference to an Instant: all you need to do is to wrap all of the
>> updates to that reference in synchronized blocks.  Readers don't need
>> anything more than for that reference to be volatile.  The
>> immutability of Instant and the sequential consistency of volatile
>> provide all the guarantees that anyone needs or are possible.
>>
>> I doubt that a synchronized block is going to perform much more badly
>> than spinning in a CAS loop, especially in the presence of high
>> contention.  In the many readers/few writers situation that Michael
>> describes this is the optimal solution.
>>
>> --
>> Andrew Haley
>> Java Platform Lead Engineer
>> Red Hat UK Ltd. <https://www.redhat.com>
>> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email]
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Andrew Haley
In reply to this post by Alex Otenko
On 07/07/17 10:23, Alex Otenko wrote:
> No, not only updates, but reads, too.
>
> If you assume non-atomic updates, the problem becomes just like with
> volatile long - has to use synchronized block for all accesses.

No.  There is one reference to the Instant, reference updates are
atomic, and Instant itself is immutable, so none of its state becomes
visible before all of its fields are initialized.  I do not believe
that it is necessary for readers to be synchronized.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Kirk Pepperdine
In reply to this post by Stephen Colebourne-2

> On Jul 6, 2017, at 11:29 PM, Stephen Colebourne <[hidden email]> wrote:
>
> Given:
>
> Instant i1 = Instant.ofEpochMilli(2);
> Instant i2 = Instant.ofEpochMilli(2);
>
> In Java 8:
>
> i1.equals(i2) is true
> i1 == i2  is false
>
> And in some future version, i1 == i2  might be true.
>
> But this is not especially radical. Java 10 could introduce a cache in
> the factory method that always returns the same instance. In fact,
> there already is a cache if you call
> Instant.ofEpochMilli(0);
>
> The key phrase in
> http://download.java.net/java/jdk9/docs/api/java/lang/doc-files/ValueBased.html
> is "A program may produce unpredictable results if it attempts to
> distinguish two references to equal values of a value-based class".
> IMO, the intent is to tell everyone that they shouldn't try to tell
> the difference between two instances using ==, and if they do their
> program may change meaning in the future (ie. be unpredictable, but
> not stupidly unpredictable as some in the thread are suggesting).

I’m sorry but of the reasons I previously stated, this is broken.

— Kirk

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Should I avoid compareAndSet with value-based classes?

Doug Lea
In reply to this post by Andrew Haley
On 07/07/2017 05:20 AM, Andrew Haley wrote:

> In practice it doesn't matter, because you don't need to CAS a
> reference to an Instant: all you need to do is to wrap all of the
> updates to that reference in synchronized blocks.  Readers don't need
> anything more than for that reference to be volatile.  The
> immutability of Instant and the sequential consistency of volatile
> provide all the guarantees that anyone needs or are possible.
>
> I doubt that a synchronized block is going to perform much more badly
> than spinning in a CAS loop, especially in the presence of high
> contention.  In the many readers/few writers situation that Michael
> describes this is the optimal solution.
>

Although amenable to the VarHandle tweak of using getAcquire
(vs implicit getVolatile) for reads. This tiny loosening of sequential
consistency might improve performance on ARM and POWER.
It's the Volatile/locked-write, acquiring-read pattern mentioned in
  http://gee.cs.oswego.edu/dl/html/j9mm.html#mixedvolatilesec

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Alex Otenko
In reply to this post by Andrew Haley
If you are updating a reference, then CAS can also work. If you are talking about imitating update of the reference by mutating inlined object contents, then you do need synchronized for readers.

Alex

> On 7 Jul 2017, at 10:32, Andrew Haley <[hidden email]> wrote:
>
> On 07/07/17 10:23, Alex Otenko wrote:
>> No, not only updates, but reads, too.
>>
>> If you assume non-atomic updates, the problem becomes just like with
>> volatile long - has to use synchronized block for all accesses.
>
> No.  There is one reference to the Instant, reference updates are
> atomic, and Instant itself is immutable, so none of its state becomes
> visible before all of its fields are initialized.  I do not believe
> that it is necessary for readers to be synchronized.
>
> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Doug Lea
On 07/07/2017 08:27 AM, Alex Otenko wrote:
> If you are updating a reference, then CAS can also work. If you are
> talking about imitating update of the reference by mutating inlined
> object contents, then you do need synchronized for readers.

Or use a StampedLock, with initial optimistic read, falling
back to read-lock, as in the javadoc examples for StampedLock:
http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/locks/StampedLock.html

(This is an extension of the SC-write, acquire-read pattern in
my last post.)

-Doug



>
> Alex
>
>> On 7 Jul 2017, at 10:32, Andrew Haley <[hidden email]> wrote:
>>
>> On 07/07/17 10:23, Alex Otenko wrote:
>>> No, not only updates, but reads, too.
>>>
>>> If you assume non-atomic updates, the problem becomes just like
>>> with volatile long - has to use synchronized block for all
>>> accesses.
>>
>> No.  There is one reference to the Instant, reference updates are
>> atomic, and Instant itself is immutable, so none of its state
>> becomes visible before all of its fields are initialized.  I do not
>> believe that it is necessary for readers to be synchronized.
>>
>> -- Andrew Haley Java Platform Lead Engineer Red Hat UK Ltd.
>> <https://www.redhat.com> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035
>> 332F A671
>
> _______________________________________________ Concurrency-interest
> mailing list [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Doug Lea
In reply to this post by Remi Forax

On 07/06/2017 10:48 AM, Remi Forax wrote:
>
> Value types have no identity so no identityHashCode.

But all instances accessible by multiple threads are contained by
an object with an identity (or transitively so).
So for example container-hash plus offset might suffice.

(This is veering too far off topic; let's take followups elsewhere.)

-Doug

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Andrew Haley
In reply to this post by Alex Otenko
On 07/07/17 13:27, Alex Otenko wrote:

> If you are updating a reference, then CAS can also work.

Well, that is the subject of some contention here, because the spec
*explicitly* says you should not compare quality, and that is what a
CAS does.  But the re is no need for a CAS; synchronized will do, and
it allows you to call equals() rather than using reference equality.

In practice, avoiding the use of reference equality is not a problem.
That is my point.

> If you are talking about imitating update of the reference by
> mutating inlined object contents,

You're not in this case.

> then you do need synchronized for readers.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Should I avoid compareAndSet with value-based classes?

David M. Lloyd-3
In reply to this post by Andrew Haley
On Fri, Jul 7, 2017 at 4:20 AM, Andrew Haley <[hidden email]> wrote:
> In practice it doesn't matter, because you don't need to CAS a
> reference to an Instant: all you need to do is to wrap all of the

I think you must have meant, "In practice it doesn't matter _in this
particular case_".  The problem of general data structures which use
CAS for updates matters very much in practice.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Should I avoid compareAndSet with value-based classes?

Andrew Haley
On 07/07/17 14:41, David Lloyd wrote:
> On Fri, Jul 7, 2017 at 4:20 AM, Andrew Haley <[hidden email]> wrote:
>> In practice it doesn't matter, because you don't need to CAS a
>> reference to an Instant: all you need to do is to wrap all of the
>
> I think you must have meant, "In practice it doesn't matter _in this
> particular case_".  The problem of general data structures which use
> CAS for updates matters very much in practice.

I'm talking about the problem of atomically updating an instance of a
value-based class while multiple threads are accessing it.  Unless I
am very much mistaken this thread is about no other subject.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Should I avoid compareAndSet with value-based classes?

David M. Lloyd-3
On Fri, Jul 7, 2017 at 8:52 AM, Andrew Haley <[hidden email]> wrote:

> On 07/07/17 14:41, David Lloyd wrote:
>> On Fri, Jul 7, 2017 at 4:20 AM, Andrew Haley <[hidden email]> wrote:
>>> In practice it doesn't matter, because you don't need to CAS a
>>> reference to an Instant: all you need to do is to wrap all of the
>>
>> I think you must have meant, "In practice it doesn't matter _in this
>> particular case_".  The problem of general data structures which use
>> CAS for updates matters very much in practice.
>
> I'm talking about the problem of atomically updating an instance of a
> value-based class while multiple threads are accessing it.  Unless I
> am very much mistaken this thread is about no other subject.

By my reading of the thread, most of it, if not all of it, is about
the more general problem of atomically updating a reference with CAS
and the behavior of the "compare" part in relation to value classes.
There is a clear problem if you don't know that your target type is a
value class and your JVM aggressively optimizes them in a way which
breaks referential equality in an unexpected way.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Gil Tene-2
In reply to this post by Andrew Haley

> On Jul 7, 2017, at 1:39 AM, Andrew Haley <[hidden email]> wrote:
>
> On 06/07/17 17:33, Gil Tene wrote:
>
>> We could further discuss whether or not the JVM is allowed to
>> "falsely" indicate that == is true (or that != is false) even when
>> the instances differ in value (so are not .equals()). It is.
>
> No it isn't, unless you believe that the paragraph on value-based
> classes overrides the JLS.  For it to do so, the definition of
> reference equality would have to change.  Right now, all it says is
> "At run time, the result of == is true if the operand values are both
> null or both refer to the same object or array; otherwise, the result
> is false."  I suppose you could argue that in the context of a
> value-based class the notion of "same object" is vacuous, but that
> would be a heck of a stretch.
>
>> Doing that may certainly surprise anyone who uses the identity based
>> == for anything to do with instances of value-based classes, even
>> tho using it would be silly given that == might obviously be
>> always-false. For example, I could see how someone may mistakenly
>> try to use == as an "optimization" on the assumption that if they
>> get lucky and == is true, .equals() must be true as well, and that
>> evaluating == might be cheaper, but they would still "do the right
>> thing" in the != case. But that would be a mistake, and a clear
>> violation of the "don't do that" admonition above.
>
> Frankly, I don't believe it.  Any JVM which did what you suggest would
> IMO be in violation of the JLS and the JVM specification.  It is
> possible that the definition of reference equality will be changed, but
> that would require the incompatible specification change to be
> discussed.

The argument would be (as you note above in the "heck of a stretch") that the field we use to talk about the instance is not a reference, but something else. Because a reference is an object identity, and value-based classes have no object identity. So it is something else. A "value identifier" of some sort. And the == operator is simply undefined on that something else. It certainly doesn't have the meaning of "IFF == is true then the value is the same" (which may be want we'd want it to mean). And it can't possibly mean "if == is the same the the object identity is the same" because there is no identity…

The "ugly" part of all this is that the compiler (and the way this stuff is derived from Object) will let you write this stuff about identity that doesn't exist, so we get to argue over what it means, and what reasonable or unreasonable ways to deal with undefined operations on non-existent identity would be.

When discussing how far a "reasonable" JVM would go:

1.  I'd agree with you that I would feel too nervous about making this undefined-behavior == operation evaluate as true for non-equal values.
 [this shouldn't make people writing Java code "comfortable" with interpreting the operand to mean that the values must be equal. It is still undefined. And this is still wrong code to write. But I'm going to want to avoid arguing too much about it, so...]

2. I would feel completely comfortable with == evaluating as always false, and != evaluating as always-true.
[Those are clearly possible and valid results. The "reference" *could* be taken away at any point, and freely replaced with something else for which .equals() is true. So acting like that happens every single time is completely reasonable. This is what makes CAS useless BTW, since it may always fail even with no contention.]

3. The exception-throwing thing is IMO the healthy way to go IMO. I.e. throw some runtime exception when encountering an indentity-based operation on an instance of a value-based class. Hard to argue that "an exception should not be thrown here" given the clear warnings in the spec. My worry is mostly about coverage. Throwing exceptions in all cases where identity based operations are attempted would clearly be right, and healthy. But doing so only in some cases (and leaving some undefined behavior executing paths that don't throw exceptions) doesn't solve the problem [and may make things worse by encouraging false confidence]. Since no one *requires* us to throw an exception right now, JVM implementors will probably keep taking the lazy approach and not work hard on trying to achieve complete coverage. And since don't do it at all" is probably better/easier to verify than "do it in some places but not in others", we'll probably avoid it altogether for now. This *may* change when value-based optimizations materialize.


>
> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Should I avoid compareAndSet with value-based classes?

Gil Tene-2
In reply to this post by Andrew Haley

On Jul 7, 2017, at 6:52 AM, Andrew Haley <[hidden email]> wrote:

On 07/07/17 14:41, David Lloyd wrote:
On Fri, Jul 7, 2017 at 4:20 AM, Andrew Haley <[hidden email]> wrote:
In practice it doesn't matter, because you don't need to CAS a
reference to an Instant: all you need to do is to wrap all of the

I think you must have meant, "In practice it doesn't matter _in this
particular case_".  The problem of general data structures which use
CAS for updates matters very much in practice.

I'm talking about the problem of atomically updating an instance of a
value-based class while multiple threads are accessing it.  Unless I
am very much mistaken this thread is about no other subject.

You are right. That's the subject of the thread. And in some cases locking (on something other than the reference to the value-based class) will be perfectly sufficient. But in cases where people seek lock-free or wait-free operations, locking may not be an acceptable thing. E.g. Clocks and Instants are starting to show up in the low latency paths of FinServ software due to MiFID 2 requirements, and that sort of code often tries to avoid locking like the plague…

For reference, here are my variants of Michael's originally posted MutableClock (which is the thing that started this thread, I believe). They is still lock free, and CAS's on a boxed Instant to avoid the "compare" on undefined identity. MutableClock still supports sharing updates across clock instances, but UnsharedMutableClock is a [I think correct] variant where "shared updates" are not supported, and caches the Instant for faster read access.

public class MutableClock {

public static MutableClock create(final Instant instant, final ZoneId zone) {
return new MutableClock(
new AtomicReference<>(new BoxedInstant(instant)),
zone);
}

private final AtomicReference<BoxedInstant> instantHolder;
private final ZoneId zone;

private MutableClock(
final AtomicReference<BoxedInstant> instantHolder,
final ZoneId zone) {
this.instantHolder = instantHolder;
this.zone = zone;
}

public Instant instant() {
return instantHolder.get().getInstant();
}

public ZoneId getZone() {
return zone;
}

public void setInstant(final Instant newInstant) {
instantHolder.get().setInstant(newInstant);
}

public void add(final Duration amountToAdd) {
boolean success;
do {
BoxedInstant currentBoxedInstance = instantHolder.get();
BoxedInstant newBoxedInstant =
new BoxedInstant(currentBoxedInstance.getInstant().plus(amountToAdd));
success = instantHolder.compareAndSet(currentBoxedInstance, newBoxedInstant);
} while (!success);
}

public MutableClock withZone(final ZoneId newZone) {
// conveniently, AtomicReference also acts as a
// vehicle for "shared updates" between instances:
return new MutableClock(instantHolder, newZone);
}

private static class BoxedInstant {
private Instant instant;

BoxedInstant(final Instant instant) {
setInstant(instant);
}

Instant getInstant() {
return instant;
}

void setInstant(final Instant instant) {
if (instant == null) {
throw new UnsupportedOperationException("null instants are unsupported");
}
this.instant = instant;
}
}
}

public class UnsharedMutableClock {

public static UnsharedMutableClock create(final Instant instant, final ZoneId zone) {
return new UnsharedMutableClock(
new AtomicReference<>(new BoxedInstant(instant)),
zone);
}

private final AtomicReference<BoxedInstant> instantHolder;
private final ZoneId zone;
private Instant cachedInstant;
private volatile boolean cacheIsValid = false;

private UnsharedMutableClock(
final AtomicReference<BoxedInstant> instantHolder,
final ZoneId zone) {
this.instantHolder = instantHolder;
this.zone = zone;
this.cachedInstant = instantHolder.get().getInstant();
}

public Instant instant() {
if (!cacheIsValid) {
cachedInstant = instantHolder.get().getInstant();
}
return cachedInstant;
}

public ZoneId getZone() {
return zone;
}

public void setInstant(final Instant newInstant) {
instantHolder.get().setInstant(newInstant);
cacheIsValid = false;
}

public void add(final Duration amountToAdd) {
boolean success;
do {
BoxedInstant currentBoxedInstance = instantHolder.get();
BoxedInstant newBoxedInstant =
new BoxedInstant(currentBoxedInstance.getInstant().plus(amountToAdd));
success = instantHolder.compareAndSet(currentBoxedInstance, newBoxedInstant);
} while (!success);
cacheIsValid = false;
}

private static class BoxedInstant {
private Instant instant;

BoxedInstant(final Instant instant) {
setInstant(instant);
}

Instant getInstant() {
return instant;
}

void setInstant(final Instant instant) {
if (instant == null) {
throw new UnsupportedOperationException("null instants are unsupported");
}
this.instant = instant;
}
}

}




--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Kirk Pepperdine
In reply to this post by Gil Tene-2
>
> 3. The exception-throwing thing is IMO the healthy way to go IMO. I.e. throw some runtime exception when encountering an indentity-based operation on an instance of a value-based class. Hard to argue that "an exception should not be thrown here" given the clear warnings in the spec. My worry is mostly about coverage. Throwing exceptions in all cases where identity based operations are attempted would clearly be right, and healthy. But doing so only in some cases (and leaving some undefined behavior executing paths that don't throw exceptions) doesn't solve the problem [and may make things worse by encouraging false confidence]. Since no one *requires* us to throw an exception right now, JVM implementors will probably keep taking the lazy approach and not work hard on trying to achieve complete coverage. And since don't do it at all" is probably better/easier to verify than "do it in some places but not in others", we'll probably avoid it altogether for now. This *may* change when value-based optimizations materialize.

I think I’d have to (violently) disagree with this. There is a reason no one requires you to throw an exception when expressing equality and that is because this is a guaranteed property in the runtime. Without it you lose a fundamental property of the runtime.

— Kirk

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Should I avoid compareAndSet with value-based classes?

Andrew Haley
In reply to this post by Gil Tene-2
On 07/07/17 18:02, Gil Tene wrote:
>
> And in some cases locking (on something other than the reference to
> the value-based class) will be perfectly sufficient. But in cases
> where people seek lock-free or wait-free operations, locking may not
> be an acceptable thing. E.g. Clocks and Instants are starting to
> show up in the low latency paths of FinServ software due to MiFID 2
> requirements, and that sort of code often tries to avoid locking
> like the plague…

Mmm, but then the question is whether something like this is more
performant than locking:

>     public void add(final Duration amountToAdd) {
>         boolean success;
>         do {
>             BoxedInstant currentBoxedInstance = instantHolder.get();
>             BoxedInstant newBoxedInstant =
>                     new BoxedInstant(currentBoxedInstance.getInstant().plus(amountToAdd));
>             success = instantHolder.compareAndSet(currentBoxedInstance, newBoxedInstant);
>         } while (!success);
>     }

I'd argue that it's may well not be, because in the mostly-uncontended
case acquiring a lock will sail straight through with no significant
delay -- certainly no more than the compareAndSet we see here.  In the
highly-contended case, locking may be preferable to the inter-thread
thrashing this CAS loop might cause.  At least one of the threads
would acquire the lock, and at least one of them would make some
forward progress.  And the readers would be simpler and faster.  The
lock used could be a fast spinlock: it doesn't have to block at the OS
level.  But to know for sure you'd have to measure some real
application behaviour.

And the meta-question is whether people who avoid locking like the
plague, even when it really is the simplest and cleanest thing to do,
are doing it for good reasons or following a cargo cult.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Should I avoid compareAndSet with value-based classes?

Gil Tene-2
In reply to this post by Kirk Pepperdine

On Jul 7, 2017, at 10:04 AM, Kirk Pepperdine <[hidden email]> wrote:


3. The exception-throwing thing is IMO the healthy way to go IMO. I.e. throw some runtime exception when encountering an indentity-based operation on an instance of a value-based class. Hard to argue that "an exception should not be thrown here" given the clear warnings in the spec. My worry is mostly about coverage. Throwing exceptions in all cases where identity based operations are attempted would clearly be right, and healthy. But doing so only in some cases (and leaving some undefined behavior executing paths that don't throw exceptions) doesn't solve the problem [and may make things worse by encouraging false confidence]. Since no one *requires* us to throw an exception right now, JVM implementors will probably keep taking the lazy approach and not work hard on trying to achieve complete coverage. And since don't do it at all" is probably better/easier to verify than "do it in some places but not in others", we'll probably avoid it altogether for now. This *may* change when value-based optimizations materialize.

I think I’d have to (violently) disagree with this. There is a reason no one requires you to throw an exception when expressing equality and that is because this is a guaranteed property in the runtime. Without it you lose a fundamental property of the runtime.

Synchronous exceptions can be thrown for example because (https://docs.oracle.com/javase/specs/jls/se7/html/jls-11.html#jls-11.1.2):
  • evaluation of an expression violates the normal semantics of the Java programming language (§15.6), such as an integer divide by zero.

  • an error occurs while loading, linking, or initializing part of the program (§12.2§12.3§12.4); in this case, an instance of a subclass of LinkageError is thrown.

  • an internal error or resource limitation prevents the Java Virtual Machine from implementing the semantics of the Java programming language; in this case, an instance of a subclass of VirtualMethodError is thrown. [GT: this is mis-spelled in the spec. Should be VirtualMachineError]. 


I'd hope to have it qualify under the first bullet, but it is not listed in the specific list of runtime exception causes in 15.6. However, evaluating an == expression where one of the operands is an instance of a value-based class (and has no identity) can probably qualify under "an internal error or resource limitation prevents the Java Virtual Machine from implementing the semantics of the Java programming language" (third bullet). Especially when the Java SE spec explicitly says "Use of such identity-sensitive operations on instances of value-based classes may have unpredictable effects". 

Separately, asynchronous exceptions can be thrown anywhere in the code. E.g. An OOME can hit a == point in the code too.

I'd rather not make such exceptions a subclass of VirtualMachineError would be better tho...


— Kirk


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
123456