performance issue with nullable value type

Remi Forax forax at univ-mlv.fr
Mon Jan 7 14:44:36 UTC 2019


Hi all,
with the last patch of Tobias, i was able to write a code that iterate an over array with a value type nullable or not.

The first way is to use a non nullable value type + a method hasNext() that indicate if the cursor is at the end

  static value class FlatCursor {
    private final int[] array;
    private final int index;
    
    private FlatCursor(int[] array, int index) {
      this.array = array;
      this.index = index;
    }
    
    Tuple current() {
      return new Tuple(index, array[index]);
    }
    
    boolean hasNext() {
      return index < array.length;
    }
    
    FlatCursor next() {
      return new FlatCursor(array, index + 1);
    }
  }
  
  private static FlatCursor flatIndexedElements(int[] array) {
    return new FlatCursor(array, 0);
  }

  public int sum_flat_indexedElements() {
    var sum = 0;
    for(var cursor = flatIndexedElements(ARRAY); cursor.hasNext(); cursor = cursor.next()) {
      var tuple = cursor.current();
      sum += tuple.index + tuple.element;
    }
    return sum;
  }

the second version is to use a nullable value type and stop if it's null

  static value class Cursor {
    private final int[] array;
    private final int index;
    
    private Cursor(int[] array, int index) {
      this.array = array;
      this.index = index;
    }
    
    Tuple current() {
      return new Tuple(index, array[index]);
    }
    
    Cursor.box next() {
      Cursor.box box;
      if (index + 1 == array.length) {
        box = null;
      } else {
        box = new Cursor(array, index + 1);
      }
      return box;
    }
  }
  
  private static Cursor.box indexedElements(int[] array) {
    Cursor.box box;
    if (array.length == 0) {
      box = null;
    } else {
      box = new Cursor(array, 0);
    }
    return box;
  }
  
  private static Cursor fix(Cursor.box cursor) {
    return cursor;
  }

  public int sum_indexedElements() {
    var sum = 0;
    for(var cursor = indexedElements(ARRAY); cursor != null; cursor = fix(cursor).next()) {
      var tuple = fix(cursor).current();
      sum += tuple.index + tuple.element;
    }
    return sum;
  }
  

The main issue is that the version is that it's very slow compared to the non nullable version
(the sum_loop is the version is just a plain loop)
Benchmark                                    Mode  Cnt    Score   Error  Units
TupleLoopBenchMark.sum_flat_indexedElements  avgt    9   41.514 ± 0.156  us/op
TupleLoopBenchMark.sum_indexedElements       avgt    9  332.060 ± 4.846  us/op
TupleLoopBenchMark.sum_loop                  avgt    9   41.169 ± 0.384  us/op


I believe that if a nullable value type is on stack, the VM should try to flatten the type by adding a boolean indicating if the value is null or not.

Rémi


More information about the valhalla-dev mailing list