Java priority queue implementation - memory locality

I am trying to implement an efficient priority queue in Java. I got to a good implementation of a binary heap but it doesn't have the ideal cache performance. For this I started studying the Van Emde Boas layout in a binary heap which led me to a "blocked" version of a binary heap, where the trick is to calculate the children and parent indices.

Although I was able to do this开发者_运维技巧, the cache behavior (and running time) got worse. I think that the problem is: locality of reference is probably not being achieved, since it is Java - I'm not so sure if using an array of objects actually makes objects to be contiguous in memory in Java, can anyone confirm this please?

Also I would like very much to know what kind of data-structures Java's native PriorityQueue uses, if any would know.

In general, there is no good way to force your objects in the queue to occupy a contiguous chunk of memory. There are, however, some techniques that are suitable for special cases.

At a high level, the techniques involve using byte arrays and 'serializing' data to and from the array. This is actually quite effective if you are storing very simple objects. For example, if you are storing a bunch of 2D points + weights, you can simply write byte equivalent of the weight, x-coordinate, y-coordinate.

The problem at this point, of course, is in allocating instances while peeking/popping. You can avoid this by using a callback.

Note that even in cases where the object being stored itself is complex, using a technique similar to this where you keep one array for the weights and a separate array of references for the actual objects allows you to avoid following the object reference until absolutely necessary.

Going back to the approach for storing simple immutable value-type, here's an incomplete sketch of what you could do:

abstract class LowLevelPQ<T> {

  interface DataHandler<R, T> {
    R handle(byte[] source, int startLoc);
  }

  LowLevelPQ(int entryByteSize) { ... }
  abstract encode(T element, byte[] target, int startLoc);
  abstract T decode(byte[] source, int startLoc);
  abstract int compare(byte[] data, int startLoc1, int startLoc2);

  abstract <R> R peek(DataHandler<R, T> handler) { ... }
  abstract <R> R pop(DataHandler<R, T> handler) { ... }
}

class WeightedPoint {
  WeightedPoint(int weight, double x, double y) { ... }
  double weight() { ... }
  double x() { ... }
  ...
}

class WeightedPointPQ extends LowLevelPQ<WeightedPoint> {
  WeightedPointPQ() {
    super(4 + 8 + 8); // int,double,double
  }

  int compare(byte[] data, int startLoc1, int startLoc2) {
    // relies on Java's big endian-ness
    for (int i = 0; i < 4; ++i) {
      int v1 = 0xFF & (int) data[startLoc1];
      int v2 = 0xFF & (int) data[startLoc2];
      if (v1 < v2) { return -1; }
      if (v1 > v2) { return  1; }
    }
    return 0;
  }

  ...
}

I don't think it would. Remember, "arrays of objects" aren't arrays of objects, they are arrays of object references (unlike arrays of primitives which really are arrays of the primitives). I'd expect the object references are contiguous in memory, but since you can make those references refer to any objects you want whenever you want, I doubt there's any guarantee that the objects referred to by the array of references will be contiguous in memory.

For what it's worth, the JLS section on arrays says nothing about any guarantees of contiguousness.

I think there is some FUD going on here. It is basically inconceivable that any implementation of arrays would not use contiguous memory. And the way the term is used in the JVM specification when describing the .class file format makes it pretty clear that no other implementation is contemplated.

java.util.PriorityQueue uses a binary heap, as it says in the Javadoc, implemented via an array.