JIT Optimization and Weak References

Question

I have the following piece of code:

private final List<WeakReference<T>> slaves;

public void updateOrdering() {
  // removes void weak references 
  // and ensures that weak references are not voided 
  // during subsequent sort 
  List<T> unwrapped = unwrap();
  assert unwrapped.size() == this.slaves.size();
  // **** could be reimplemented without using unwrap() ****
  Collections.sort(this.slaves, CMP_IDX_SLV);
  unwrapped = null;// without this, ....
}

Method unwrap() just creates a list of T's referenced by the weak references in slaves and as a side effect eliminates the weak references referencing null in slaves. Then comes the sort which relies on that each member of slaves references some T; otherwise the code yields a NullPointerException.

Since unwrapped holds a reference on each T in slaves, during sorting no GC eliminates a T. Finally, unwrapped = null eliminates the reference on unwrapped and so releases GC again. Seems to work quite well.

Now my question:

If I remove unwrapped = null; this results in NullPointerExceptions when running many tests under some load. I suspect that the JIT eliminates List<T> unwrapped = unwrap(); and so GC applies to the T's in slaves during sorting.

Do you have another explanation? If you agree with me, is this a bug in the JIT?

I personally think that unwrapped = null should not be necessary, because unwrapped is removed from the frame as soon as updateOrdering() returns. Is there a specification what may be optimized and what is not?

Or did I do the thing in the wrong way? I have the idea to modify comparator that it allows weak references on null. What do you think about that?

Thanks for suggestions.

Add on (1)

Now I want to add some missing pieces of information: First of all Java version: java version "1.7.0_45" OpenJDK Runtime Environment (IcedTea 2.4.3) (suse-8.28.3-x86_64) OpenJDK 64-Bit Server VM (build 24.45-b08, mixed mode)

Then someone wanted to see method unwrap

private synchronized List<T> unwrap() {
List<T> res = new ArrayList<T>();
T cand;
WeakReference<T> slvRef;
Iterator<WeakReference<T>> iter = this.slaves.iterator();
while (iter.hasNext()) {
    slvRef = iter.next();
    cand = slvRef.get();
    if (cand == null) {
    iter.remove();
    continue;
    }
    assert cand != null;
    res.add(cand);
} // while (iter.hasNext())

return res;
}

Note that while iterating, void references are removed. In fact i replaced this method by

private synchronized List<T> unwrap() {
List<T> res = new ArrayList<T>();
for (T cand : this) {
    assert cand != null;
    res.add(cand);
}

return res;
}

using my own iterator but functionally this should be the same.

Then someone wantet the stacktrace. Here is a piece of it.

 java.lang.NullPointerException: null
 at WeakSlaveCollection$IdxComparator.compare(WeakSlaveCollection.java:44)
 at WeakSlaveCollection$IdxComparator.compare(WeakSlaveCollection.java:40)
 at java.util.TimSort.countRunAndMakeAscending(TimSort.java:324)
 at java.util.TimSort.sort(TimSort.java:189)
 at java.util.TimSort.sort(TimSort.java:173)
 at java.util.Arrays.sort(Arrays.java:659)
 at java.util.Collections.sort(Collections.java:217)
 at WeakSlaveCollection.updateOrdering(WeakSlaveCollection.java:183)

it points into the comparator, the line with the return.

static class IdxComparator 
    implements Comparator<WeakReference<? extends XSlaveNumber>> {
    public    int compare(WeakReference<? extends XSlaveNumber> slv1, 
              WeakReference<? extends XSlaveNumber> slv2) {
        return slv2.get().index()-slv1.get().index();
    }
} // class IdxComparator 

and finally,

 private final static IdxComparator CMP_IDX_SLV = new IdxComparator();

is an important constant.

Add on (2)

Observed now that indeed NPE occurs even if 'unwrapped = null' is present in updateOrdering().

Weak references may be removed by java runtime if no strict reference holds after jit optimization. The source code seems not important at all.

I solved the problem the following way:

public void updateOrdering() {
Collections.sort(this.slaves, CMP_IDX_SLV);
}

without any decoration inserted to prevent slaves to be garbage collected and the comparator in CMP_IDX_SLV enabled to handle weak references to null:

    public    int compare(WeakReference<? extends XSlaveNumber> slv1, 
              WeakReference<? extends XSlaveNumber> slv2) {
    XSlaveNumber sSlv1 = slv1.get();
    XSlaveNumber sSlv2 = slv2.get();
    if (sSlv1 == null) {
    return sSlv2 == null ? 0 : -1;
    }
    if (sSlv2 == null) {
    return +1;
    }
    assert sSlv1 != null && sSlv2 != null;

    return sSlv2.index()-sSlv1.index();
    }

As a side effect, ordering the underlying list List> slaves; puts the void weak references at the end of the list, where it can be collected later.

Answer 1

I examine your source code, and I got NullPointerException when JIT compile my method corresponding to your method "updateOrdering" and GC occurs during sorting.

But I got NullPointerException when Collections.sort whether with or without unwrapped = null. This maybe occurs difference between my sample source code and yours, or Java version difference. I will examine if you tell Java version.

I use java below version.

java version "1.7.0_40"
Java(TM) SE Runtime Environment (build 1.7.0_40-b43)
Java HotSpot(TM) 64-Bit Server VM (build 24.0-b56, mixed mode)

If you want to cheat on JIT compilation, the below code insert your source code instead unwrapped = null(e.g.). Then, JIT compilation doesn't eliminates unwrapped code.

long value = unwrapped.size() * unwrapped.size();
if(value * value % 3 == 1) {
  //Because value * value % 3 always is 1 or 0, this code can't reach. 
  //Insert into this the source code that use unwrapped array, for example, show unwrapped array.
}

My examination result is below.

• If JIT don't optimize my method corresponding to updateOrdering, no NullPointerException occurs.
• If JIT optimize my method, then NullPointerException occurs at some point.
• If JIT optimize my method inserting the above source code cheating JIT compiler, then no NullPointerException occurs.

So, I(and you) suggest JIT optimze eliminates unwrapped code, then NullPointerException occurs.

By the way, if you want to show JIT compiler optimization, you invoke java with -XX:+PrintCompilation.
If you want to show GC, with -verbose:gc.

Just for information, my sample source code is below.

public class WeakSampleMain {
    private static List<WeakReference<Integer>> weakList = new LinkedList<>();
    private static long sum = 0;
    public static void main(String[] args) {
        System.out.println("start");
        int size = 1_000_000;
        for(int i = 0; i < size; i++) {
            Integer value = Integer.valueOf(i);
            weakList.add(new WeakReference<Integer>(value));
        }
        for(int i = 0; i < 10; i++) {
            jitSort();
        }
        GcTask gcTask = new GcTask();
        Thread thread = new Thread(gcTask);
        thread.start();
        for(int i = 0; i < 100000; i++) {
            jitSort();
        }
        thread.interrupt();
        System.out.println(sum);
    }

    public static void jitSort() {
        List<Integer> unwrappedList = unwrapped();
        removeNull();
        Collections.sort(weakList, 
                new Comparator<WeakReference<Integer>>() {

                    @Override
                    public int compare(WeakReference<Integer> o1,
                            WeakReference<Integer> o2) {
                        return Integer.compare(o1.get(), o2.get());
                    }
        }
                );
        for(int i = 0; i < Math.min(weakList.size(), 1000); i++) {
            sum += weakList.get(i).get();
        }
        unwrappedList = null;
//          long value = (sum + unwrappedList.size());
//          if((value * value) % 3 == 2) {
//              for(int i = 0; i < unwrappedList.size(); i++) {
//                  System.out.println(unwrappedList.get(i));
//              }
//          }
    }

    public static List<Integer> unwrapped() {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(WeakReference<Integer> ref : weakList) {
            Integer i = ref.get();
            if(i != null) {
                list.add(i);
            }
        }
        return list;
    }

    public static void removeNull() {
        Iterator<WeakReference<Integer>> itr = weakList.iterator();
        while(itr.hasNext()) {
            WeakReference<Integer> ref = itr.next();
            if(ref.get() == null) {
                itr.remove();
            }
        }
    }

    public static class GcTask implements Runnable {
        private volatile int result = 0;
        private List<Integer> stockList = new ArrayList<Integer>();
        public void run() {
            while(true) {
                if(Thread.interrupted()) {
                    break;
                }
                int size = 1000000;
                stockList = new ArrayList<Integer>(size);
                for(int i = 0; i < size; i++) {
                    stockList.add(new Integer(i));
                }
                if(System.currentTimeMillis() % 1000 == 0) {
                    System.out.println("size : " + stockList.size());
                }
            }
        }

        public int getResult() {
            return result;
        }
    }
}

Answer 2

As of Java 9, the correct way to prevent the JIT from discarding unwrapped is to use Reference.reachabilityFence:

public void updateOrdering() {
  List<T> unwrapped = unwrap();
  Collections.sort(this.slaves, CMP_IDX_SLV);
  Reference.reachabilityFence(unwrapped);
}

The presence of the reachabilityFence call causes unwrapped to be considered strongly reachable before the call, preventing collection of unwrapped or its elements until the sort completes. (The strange way in which reachabilityFence's effects seem to propagate backward in time is because it behaves primarily as a JIT directive.) Without reachabilityFence, unwrapped can be collected once the JIT can prove it will never again be accessed, even though the variable is still in scope.

Answer 3

Your question

If I remove unwrapped = null; this results in NullPointerException when running many tests under some load.

According to my understanding I do not think so that unwrapped = null; makes any difference.
Yes, I have also read that making objects = null sometime increases the probability the object referenced will be GC'ed but I don't think it matters here because once the method ends, scope of unwrapped ends and is eligible for GC'ed and in your function sorting Collections.sort(this.slaves, CMP_IDX_SLV); is done prior to unwrapped = null; so it make no sense the you get NPE when adding or removing them.

I think it is just a coincidence that you get NPE, I believe if you run the test again you will get NPE with that statement also.

If you read Java Documentation

Weak reference objects, which do not prevent their referents from being made finalizable, finalized, and then reclaimed. Weak references are most often used to implement canonicalizing mappings.
Suppose that the garbage collector determines at a certain point in time that an object is weakly reachable. At that time 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. At the same time it will declare all of the formerly weakly-reachable objects to be finalizable. At the same time or at some later time it will enqueue those newly-cleared weak references that are registered with reference queues.

So it is really possible when you constructed the List from unwrap() some objects might have been marked finalized and while your Collection.sort is working some WeakRefrence are assigned null. And the point stated by Mattias Buelens is perfectly valid you'll always lose in a fight against the compiler.

If you agree with me, is this a bug in the JIT?

No surely not, I completely disagree with you.

I have the idea to modify comparator that it allows weak references on null. What do you think about that?

I think it will solve your one problem of NPE but your requirement removes void weak references and ensures that weak references are not voided during subsequent sort is not satisfied.
Rather try to call unwrap once again, this will reduce the window for NPE to almost zero,

List<T> unwrapped = unwrap();
unwrapped = unwrap(); //Again to eliminate the chances for NPE as now we would have 
           //already made strong refrences to all objects which have not been `null`