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.