> On Jan 22, 2016, at 2:49 PM, Peter Levart <peter.lev...@gmail.com> wrote:
>
> Hi Gil,
>
> Thanks for taking a look at the Ephemerons for Java. It's great to have a big
> mind joining the discussion.
>
> On 01/22/2016 07:12 PM, Gil Tene wrote:
>> Peter,
>>
>> I've been following Ephemerons in other GC'ed environments, and wondering
>> when someone will bring it up for Java. Happy to see attentions given to it.
>> The "conditional weak reference hashmap/table/dictionary" use case seems to
>> be a common primary motivator, and it's a very valid one. Given that we
>> currently do completely concurrent ref processing (in Zing at least) for all
>> reference types, adding Ephemerons to the spec'ed behavior will add some
>> interesting challenges for keeping things concurrent, but I don't think that
>> it is fundamentally undoable (just "hard" and interesting to fully work out).
>
> The algorithm for processing ephemerons is not much different from that for
> processing normal references. It's just that it is iterative until it
> converges to a stable state. If you allow mutator threads to at least in some
> phases execute concurrently with normal reference processing then I suspect
> it should be possible to do that for ephemerons too, but I don't have a clue
> what tricks you perform to be able to allow mutator threads to be concurrent
> with reference processing.
>
>> Scanning through the proposal and Java class (mostly JavaDoc spec), I have
>> the following question:
>>
>> Do we really need a separate "ephemerally reachable" strength below week?
>> The was you extended the definition to the weak definition to say "An object
>> is weakly reachable if it is neither strongly nor softly reachable but can
>> be reached by traversing a weak reference or by traversing an ephemeron
>> through it's value while the ephemeron's key is at least weakly reachable."
>> would [naively] seem to be sufficient to add and fully describe the desired
>> Ephemeron behavior from a reference strength perspective.
>
> Ephemeron always touches definitions of at least two consecutive strengths of
> reachabilities. The prototype says:
>
> * <li> An object is <em>weakly reachable</em> if it is neither
> * strongly nor softly reachable but can be reached by traversing a
> * weak reference or by traversing an ephemeron through it's value while
> * the ephemeron's key is at least weakly reachable.
>
> * <li> An object is <em>ephemerally reachable</em> if it is neither
> * strongly, softly nor weakly reachable but can be reached by traversing an
> * ephemeron through it's key or by traversing an ephemeron through it's value
> * while it's key is at most ephemerally reachable. When the ephemerons that
> * refer to ephemerally reachable key object are cleared, the key object
> becomes
> * eligible for finalization.
Looking into this a bit more, I don't think the above is quite right.
Specifically, If an ephemeron's key is either strongly of softly reachable, you
want the value to remain appropriately strongly/softly reachable. Without this
quality, Ephemeron value referents can (and will) be prematurely collected and
finalized while the keys are not. This (IMO) needed quality not provided by the
behavior you specify…
For a correctly specified behavior, I think all strengths (from strong down)
need to be affected by key/value Ephemeron relationships, but without adding an
"ephemerally reachable" strength. E.g. I think you fundamentally need something
like this:
- "An object is <em>strongly reachable</em> if it can be reached by (a) some
thread without traversing any reference objects, or by (b) traversing the value
of an Ephemeron whose key is strongly reachable. A newly-created object is
strongly reachable by the thread that created it"
- "An object is <em>softly reachable</em> if it is not strongly reachable but
can be reached by (a) traversing a soft reference or by (b) traversing the
value of an Ephemeron whose key is softly reachable.
- "An object is <em>weakly reachable</em> if it is neither strongly nor softly
reachable but can be reached by (a) traversing a weak reference or by (b)
traversing the value of an ephemeron whose key is weakly reachable.
>
> But Ephemeron does not need a special reachability strength. It could be
> merged with WeakReference as far as the reachability of it's key is
> concerned. In that case it would touch at least the definitions of
> softly-reachable and weakly-reachable:
>
> * <li> An object is <em>softly reachable</em> if it is not strongly
> * reachable but can be reached by traversing a soft reference or
> * by traversing an ephemeron through it's value while
> * the ephemeron's key is at least softly reachable.
>
> * <li> An object is <em>weakly reachable</em> if it is neither
> * strongly nor softly reachable but can be reached by traversing a
> * weak reference (including ephemeron through it's key) or by traversing
> * an ephemeron through it's value while the ephemeron's key is at most
> * weakly reachable. When the weak references to a weakly-reachable
> * object are cleared (which includes ephemerons to a weakly-reachable key),
> * the object becomes eligible for finalization.
>
>
> Presently the hotspot handles different strengths of references by
> maintaining a distinct set of discovered references for each type and then
> processing these sets in sequence from the strongest to the weakest. If
> Ephemerons and WeakReferences were kept in the same discovered set, they
> would present the same reachability strength for their referent (called also
> the key in case of ephemeron).
>
>> Specifically, would modifying your implementation such that Ephemeron<K, V>
>> extended WeakReference<K> (instead of Reference<K>), and it's V value was
>> tracked with "private WeakReference<V> valueRef" (instead of "private V
>> value") [along with the semi-obvious internal changes that would result]
>> provide what is needed to support proper Ephemeron behavior we just added
>> the "…or by traversing an ephemeron through it's value while the ephemeron's
>> key is at least weakly reachable." to the spec'ed definition of "weakly
>> reachable" (and modified the associated JVM ref processing accordingly,
>> which you already have to do to support your wider definitions anyway)?
>
> In case the strength of ephemeron's key was the same as that of
> WeakReference's referent, it would make sense for Ephemeron to extend
> WeakReference, since it would then just be a special kind of WeakReference.
> But I don't think that changing "private V value" into "private
> WeakReference<V> valueRef" would buy anything in terms of processing
> algorithm simplicity. At least in hotspot it would increase the code
> complexity, since marking the ephemeron's value 'alive' as a consequence of
> finding it's key marked alive during iteration over the list of ephemerons
> and removing the current ephemeron from the pending list, would also require
> removing of the valuRef WeakReference from the pending list at the same time
> but that would require finding it in the list 1st, since it's a
> single-linked-list or removing it at next iteration which would increase the
> number of iterations through the pending set before the state converges...
>
> There's no problem in making the VM to treat the "private V value" specially.
> In HotSpot it is only required to update the OopMap for the Ephemeron class
> to exclude the value field - analogue to how this is done for Reference
> fields. There's no need for indirection through another WeakReference to get
> special treatment for value (exclusion from traversals).
I agree that the value fields does not need to be a Weakref, and the a "private
V value; /* Treated specially by GC */" can be used (much like Reference's
declaration of the referent field). So I take back my suggestion on that.
I still think that Ephemeron<K, V> should extend WeakReference<K>, since that
places already established rules and expectation on (a) when it will be
enqueued, (b) when the collector will clear it (when the the collector
encounters the <K> key being weakly reachable), and (c) that clearing of all
Ephemeron *and* WeakReference instances who share an identical key value is
done atomically, along with (d) all weak references to to any other
weakly-reachable objects from which that object is reachable through a chain of
strong and soft references. These last (c, d) parts are critically captured
since an Ephemeron *is a* WeakReference, and the statement in WeakReference
that says that "… it will atomically clear all weak references to that object
and all weak references to any other weakly-reachable objects from which that
object is reachable through a chain of strong and soft references." has a clear
application.
Here are some suggested edits to the JavaDoc to go with this suggested spec'ed
behavior:
/**
* Ephemeron<K, V> objects are a special kind of WeakReference<K> objects,
which
* hold two referents (a key referent and a value referent) and do not prevent
their
* referents from being made finalizable, finalized, and then reclaimed.
* In addition to the key referent, which adheres to the referent behavior of a
* WeakReference<K>, an ephemeron also holds a value referent whose reachabiliy
* strength is affected by the reachability strength of the key referent:
* The value referent of an Ephemeron instance is considered:
* (a) strongly reachable if the key referent of the same Ephemeron
* object is strongly reachable, or if the value referent is otherwise
strongly reachable.
* (b) softly reachable if it is not strongly reachable, and (i) the key
referent of
* the same Ephemeron object is softly reachable, or (ii) if the value
referent is otherwise
* softly reachable.
* (c) weakly reachable if it is not strongly or softly reachable, and (i) the
key referent of
* the same Ephemeron object is weakly reachable, or (ii) if the value
referent is otherwise
* weakly reachable.
* <p> When the collector clears an Ephemeron object instance (according to
the rules
* expressed for clearing WeakReference object instances), the Ephemeron
instance's
* key referent value referent are simultaneously and atomically cleared.
* <p> By convenience, the Ephemeron's referent is also called the key, and
can be
* obtained either by invoking {@link #get} or {@link #getKey} while the value
* can be obtained by invoking {@link #getValue} method.
*...
>
> Regards, Peter
>
>
>
> — Gil.
>>
>>> On Jan 17, 2016, at 10:18 AM, Peter Levart <peter.lev...@gmail.com>
>>> <mailto:peter.lev...@gmail.com> wrote:
>>>
>>> Hi,
>>>
>>> Ephemerons are special kind of references described by Barry Hayes [1]. In
>>> the simple variant, they contain two "referents". One is called the key,
>>> which can be viewed as a "weak" referent in the style of Java reference
>>> types (SoftReference, WeakReference, PhantomReference), the other is called
>>> the value, which is also treated specially by GC. It's reachability is
>>> dependent on the reachability of the key.
>>>
>>> Ephemerons solve the problem seen for example in the java.util.WeakHashMap
>>> when a value in this map directly or indirectly refers to it's key. Such
>>> entry will never be purged as the value is always reachable from the
>>> WeakHashMap instance and through the value, it's key is reachable too.
>>> There are other places where Ephemerons could be used - for example in
>>> ClassValue API. Try googling for "java ephemeron" (without quotes) to find
>>> out other situations where Ephemerons would be beneficial.
>>>
>>> If one was to implement Ephemerons in Java, the main question he would be
>>> asking is how Ephemeron(s) were supposed to interact with existing Java
>>> reference types. Hayes only defines their behavior in isolation, but Java
>>> already has 4 "weak" reference types with different "strengths":
>>> SoftReference, WeakReference, FinalReference (for implementing
>>> finalization) and PhantomReference. In the prototype I choose to define
>>> Ephemerons as a new reference type with it's own "strength" for the key
>>> referent positioned between WeakReference and FinalReference. It would be
>>> possible to merge it with an existing reference type like WeakReference or
>>> position it between SoftReference and WeakReference or even entirely "on
>>> the top" of the strength list, but I think it would not be wise to position
>>> it below FinalReference or even PhantomReference. What's best is an open
>>> question. What is also not so obvious is how to define the reachability of
>>> the Ephemeron's value and it's interaction with exis
>>> ting refe
>>> rence types. I think I defined it soundly (see the reachability types in
>>> the javadoc of [4]). The reason for defining the reachability of the value
>>> to alternate between ephemeraly-reachable and weakly-reachable and not
>>> between ephemeraly-reachable and strongly-reachable, while theoretically
>>> possible, is the desire to have a separate phase of processing for each
>>> reachability strength, like it is done currently, and which doesn't affect
>>> the performance of processing of existing reference types.
>>>
>>> Having skimmed through the reference processing code in the VM for a couple
>>> of times, I thought it should not be too complicated to implement another
>>> type of "weak" reference. Encouraged by how little changes were needed to
>>> remove the sun.misc.Cleaner special type of reference [2], I began
>>> experimenting and came up with a prototype that seems to work [3]. Luckily
>>> most of the logic to process Reference objects in VM is encapsulated in the
>>> ReferenceProcessor class and this logic is invoked from various GC
>>> implementations of the hotspot. Changes needed are therefore mostly
>>> localized to this class. The webrev also contains recent changes from
>>> JDK-8143847 [2] that have not yet propagated to the jdk9-dev repo. When
>>> they do, I will prepare a rebased webrev without those changes.
>>>
>>> I'm publishing this prototype here to get the answer to the main question:
>>> Is there an interest to have Ephemeron reference type in Java?
>>>
>>> Given that there was interest, I would also like to initiate a discussion
>>> about:
>>> - What would be the most appropriate "strength" of reachabillity for
>>> Epehmeron referents (key and value) and the desired interactions with
>>> existing reachabilities.
>>> - The prototype itself. Since I'm new to this part of code (that's my 1st
>>> not so shallow dive into the VM), I surely must have missed places that
>>> should be changed. Although the prototype seems to work, I have not created
>>> extensive tests for the functionality and have not exposed it to all the
>>> various GC algorithms and situations yet. I could use some advise on how to
>>> exercise all GC algorithm combinations possible in the VM (what flags to
>>> use, for example).
>>>
>>> Regards, Peter
>>>
>>> [1]
>>> https://static.aminer.org/pdf/PDF/000/522/273/ephemerons_a_new_finalization_mechanism.pdf
>>>
>>> <https://static.aminer.org/pdf/PDF/000/522/273/ephemerons_a_new_finalization_mechanism.pdf>
>>> [2] https://bugs.openjdk.java.net/browse/JDK-8143847
>>> <https://bugs.openjdk.java.net/browse/JDK-8143847>
>>> [3] http://cr.openjdk.java.net/~plevart/misc/Ephemeron/
>>> <http://cr.openjdk.java.net/~plevart/misc/Ephemeron/>
>>> [4]
>>> http://cr.openjdk.java.net/~plevart/misc/Ephemeron/webrev.jdk.01/src/java.base/share/classes/java/lang/ref/Ephemeron.java.html
>>>
>>> <http://cr.openjdk.java.net/~plevart/misc/Ephemeron/webrev.jdk.01/src/java.base/share/classes/java/lang/ref/Ephemeron.java.html>
>>>
>>> P.S.
>>>
>>> To wet some appetite, with the above prototype (applied to current
>>> jdk9-dev), it is possible to run the following example:
>>>
>>> import java.lang.ref.Ephemeron;
>>> import java.util.ArrayList;
>>> import java.util.List;
>>>
>>> public class EphemeronTest {
>>>
>>> static class Key {
>>> final int i;
>>>
>>> Key(int i) {
>>> this.i = i;
>>> }
>>>
>>> @Override
>>> public String toString() {
>>> return "k" + i;
>>> }
>>> }
>>>
>>> static class Value {
>>> final Key key;
>>>
>>> Value(Key key) {
>>> this.key = key;
>>> }
>>>
>>> @Override
>>> public String toString() {
>>> return "v(" + key + ")";
>>> }
>>> }
>>>
>>> static class Eph extends Ephemeron<Key, Value> {
>>> public Eph(Key key, Value value) {
>>> super(key, value);
>>> }
>>>
>>> @Override
>>> public String toString() {
>>> return getKey() + "=" + getValue();
>>> }
>>> }
>>>
>>> static void test(int size, boolean forwardChaining) throws Exception {
>>> System.out.println();
>>> System.out.println((forwardChaining ? "Forward" : "Backward") +
>>> " chaining of value->key ...");
>>> System.out.println();
>>> List<Eph> ephs = new ArrayList<>(size);
>>>
>>> Key k1 = new Key(1);
>>> {
>>> Key kp = k1;
>>> for (int i = 2; i <= size; i++) {
>>> Key ki = new Key(i);
>>> ephs.add(
>>> forwardChaining
>>> ? new Eph(kp, new Value(ki))
>>> : new Eph(ki, new Value(kp))
>>> );
>>> kp = ki;
>>> }
>>> ephs.add(
>>> forwardChaining
>>> ? new Eph(kp, new Value(k1))
>>> : new Eph(k1, new Value(kp))
>>> );
>>> kp = null;
>>> }
>>>
>>> System.gc();
>>> System.out.println("1: " + ephs);
>>> k1.getClass(); // reachabilityFence
>>>
>>> k1 = null;
>>> System.gc();
>>> System.out.println("2: " + ephs);
>>> }
>>>
>>> public static void main(String[] args) throws Exception {
>>>
>>> int size = (args.length < 1)
>>> ? 5
>>> : Math.max(2, Integer.parseInt(args[0]));
>>>
>>> test(size, true);
>>> test(size, false);
>>> }
>>> }
>>>
>>>
>>> Which prints:
>>>
>>> Forward chaining of value->key ...
>>>
>>> 1: [k1=v(k2), k2=v(k3), k3=v(k4), k4=v(k5), k5=v(k1)]
>>> 2: [null=null, null=null, null=null, null=null, null=null]
>>>
>>> Backward chaining of value->key ...
>>>
>>> 1: [k2=v(k1), k3=v(k2), k4=v(k3), k5=v(k4), k1=v(k5)]
>>> 2: [null=null, null=null, null=null, null=null, null=null]
>>>
>>>
>>> If you compile the JDK with --enable-debug and use the following VM
>>> switches when running: -XX:+PrintGCDetails -XX:+TraceReferenceGC, you can
>>> also observe the inner workings of the reference processing, including
>>> Ephemerons.
>>>
>
