on-heap array vs off-heap array

benchmark.sh

min@min-laptop:~/code/java/benchmark$ java TestMemoryAccessPatterns 1
0 - 2.55ns LINEAR_WALK
1 - 2.67ns LINEAR_WALK
2 - 2.16ns LINEAR_WALK
3 - 2.16ns LINEAR_WALK
4 - 2.16ns LINEAR_WALK
min@min-laptop:~/code/java/benchmark$ java TestMemoryAccessPatterns 2
0 - 8.11ns RANDOM_PAGE_WALK
1 - 7.98ns RANDOM_PAGE_WALK
2 - 8.02ns RANDOM_PAGE_WALK
3 - 7.96ns RANDOM_PAGE_WALK
4 - 7.95ns RANDOM_PAGE_WALK
min@min-laptop:~/code/java/benchmark$ java TestMemoryAccessPatterns 3
0 - 100.63ns RANDOM_HEAP_WALK
1 - 100.68ns RANDOM_HEAP_WALK
2 - 100.40ns RANDOM_HEAP_WALK
3 - 100.89ns RANDOM_HEAP_WALK
4 - 101.83ns RANDOM_HEAP_WALK
min@min-laptop:~/code/java/benchmark$ java TestMemoryAccessPatternsDirect 1
0 - 3.61ns LINEAR_WALK
1 - 3.73ns LINEAR_WALK
2 - 3.32ns LINEAR_WALK
3 - 3.32ns LINEAR_WALK
4 - 3.33ns LINEAR_WALK
min@min-laptop:~/code/java/benchmark$ java TestMemoryAccessPatternsDirect 2
0 - 8.34ns RANDOM_PAGE_WALK
1 - 8.59ns RANDOM_PAGE_WALK
2 - 7.85ns RANDOM_PAGE_WALK
3 - 7.79ns RANDOM_PAGE_WALK
4 - 7.78ns RANDOM_PAGE_WALK
min@min-laptop:~/code/java/benchmark$ java TestMemoryAccessPatternsDirect 3
0 - 102.90ns RANDOM_HEAP_WALK
1 - 99.91ns RANDOM_HEAP_WALK
2 - 99.49ns RANDOM_HEAP_WALK
3 - 99.57ns RANDOM_HEAP_WALK
4 - 99.44ns RANDOM_HEAP_WALK

TestMemoryAccessPatterns.java

public class TestMemoryAccessPatterns {
  private static final int LONG_SIZE = 8;
  private static final int PAGE_SIZE = 2 * 1024 * 1024;
  private static final int ONE_GIG = 1024 * 1024 * 1024;

  private static final int ARRAY_SIZE = (int) (ONE_GIG / LONG_SIZE);
  private static final int WORDS_PER_PAGE = PAGE_SIZE / LONG_SIZE;

  private static final int ARRAY_MASK = ARRAY_SIZE - 1;
  private static final int PAGE_MASK = WORDS_PER_PAGE - 1;

  private static final int PRIME_INC = 514229;

  private static final long[] memory = new long[ARRAY_SIZE];

  static {
    for (int i = 0; i < ARRAY_SIZE; i++) {
      memory[i] = 777;
    }
  }

  public enum StrideType {
    LINEAR_WALK {
      public int
          next(final int pageOffset, final int wordOffset, final int pos) {
        return (pos + 1) & ARRAY_MASK;
      }
    },

    RANDOM_PAGE_WALK {
      public int
          next(final int pageOffset, final int wordOffset, final int pos) {
        return pageOffset + ((pos + PRIME_INC) & PAGE_MASK);
      }
    },

    RANDOM_HEAP_WALK {
      public int
          next(final int pageOffset, final int wordOffset, final int pos) {
        return (pos + PRIME_INC) & ARRAY_MASK;
      }
    };

    public abstract int next(int pageOffset, int wordOffset, int pos);
  }

  public static void main(final String[] args) {
    final StrideType strideType;
    switch (Integer.parseInt(args[0])) {
    case 1:
      strideType = StrideType.LINEAR_WALK;
      break;

    case 2:
      strideType = StrideType.RANDOM_PAGE_WALK;
      break;

    case 3:
      strideType = StrideType.RANDOM_HEAP_WALK;
      break;

    default:
      throw new IllegalArgumentException("Unknown StrideType");
    }

    for (int i = 0; i < 5; i++) {
      perfTest(i, strideType);
    }
  }

  private static void
      perfTest(final int runNumber, final StrideType strideType) {
    final long start = System.nanoTime();

    int pos = -1;
    long result = 0;
    for (int pageOffset = 0; pageOffset < ARRAY_SIZE; pageOffset +=
        WORDS_PER_PAGE) {
      for (int wordOffset = pageOffset, limit = pageOffset + WORDS_PER_PAGE; wordOffset < limit; wordOffset++) {
        pos = strideType.next(pageOffset, wordOffset, pos);
        result += memory[pos];
      }
    }

    final long duration = System.nanoTime() - start;
    final double nsOp = duration / (double) ARRAY_SIZE;

    if (104287174656L != result) {
      throw new IllegalStateException();
    }

    System.out.format("%d - %.2fns %s\n", Integer.valueOf(runNumber),
        Double.valueOf(nsOp), strideType);
  }
}

TestMemoryAccessPatternsDirect.java

import java.lang.reflect.Field;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;

import sun.misc.Unsafe;
import sun.nio.ch.DirectBuffer;

public class TestMemoryAccessPatternsDirect {
  private static final int LONG_SIZE = 8;
  private static final int PAGE_SIZE = 2 * 1024 * 1024;
  private static final int ONE_GIG = 1024 * 1024 * 1024;

  private static final int ARRAY_SIZE = (int) (ONE_GIG / LONG_SIZE);
  private static final int WORDS_PER_PAGE = PAGE_SIZE / LONG_SIZE;

  private static final int ARRAY_MASK = ARRAY_SIZE - 1;
  private static final int PAGE_MASK = WORDS_PER_PAGE - 1;

  private static final int PRIME_INC = 514229;

  private static final ByteBuffer memory = ByteBuffer
      .allocateDirect(ARRAY_SIZE << 3).order(ByteOrder.nativeOrder());

  private static final long address = ((DirectBuffer) memory).address();

  public static final Unsafe unsafe;

  static {
    try {
      Field f = Unsafe.class.getDeclaredField("theUnsafe");
      f.setAccessible(true);
      unsafe = (Unsafe) f.get(null);
    } catch (Exception e) {
      throw new AssertionError(e);
    }
  }

  static {
    for (int i = 0; i < ARRAY_SIZE; i++) {
      unsafe.putLong(address + (i << 3), 777);
    }
  }

  public enum StrideType {
    LINEAR_WALK {
      public int
          next(final int pageOffset, final int wordOffset, final int pos) {
        return (pos + 1) & ARRAY_MASK;
      }
    },

    RANDOM_PAGE_WALK {
      public int
          next(final int pageOffset, final int wordOffset, final int pos) {
        return pageOffset + ((pos + PRIME_INC) & PAGE_MASK);
      }
    },

    RANDOM_HEAP_WALK {
      public int
          next(final int pageOffset, final int wordOffset, final int pos) {
        return (pos + PRIME_INC) & ARRAY_MASK;
      }
    };

    public abstract int next(int pageOffset, int wordOffset, int pos);
  }

  public static void main(final String[] args) {
    final StrideType strideType;
    switch (Integer.parseInt(args[0])) {
    case 1:
      strideType = StrideType.LINEAR_WALK;
      break;

    case 2:
      strideType = StrideType.RANDOM_PAGE_WALK;
      break;

    case 3:
      strideType = StrideType.RANDOM_HEAP_WALK;
      break;

    default:
      throw new IllegalArgumentException("Unknown StrideType");
    }

    for (int i = 0; i < 5; i++) {
      perfTest(i, strideType);
    }
  }

  private static void
      perfTest(final int runNumber, final StrideType strideType) {
    final long start = System.nanoTime();

    int pos = -1;
    long result = 0;
    for (int pageOffset = 0; pageOffset < ARRAY_SIZE; pageOffset +=
        WORDS_PER_PAGE) {
      for (int wordOffset = pageOffset, limit = pageOffset + WORDS_PER_PAGE; wordOffset < limit; wordOffset++) {
        pos = strideType.next(pageOffset, wordOffset, pos);
        result += unsafe.getAddress(address + (pos << 3));
      }
    }

    final long duration = System.nanoTime() - start;
    final double nsOp = duration / (double) ARRAY_SIZE;

    if (104287174656L != result) {
      throw new IllegalStateException();
    }

    System.out.format("%d - %.2fns %s\n", Integer.valueOf(runNumber),
        Double.valueOf(nsOp), strideType);
  }
}

hi,your code is copy from Martin Thompson.

Yes, you are right. This is only a code fragment for testing. I just added a DirectBuffer accessing, comparing those two access patterns.

Hello Min,
Just read your slides and I'm interested in your implementation. Is it possible to share me your code for the single-producer single-consumer? Thanks a lot!