Java 优先级队列实现 - 内存局部性

Question

我正在尝试在Java中实现一个高效的优先级队列。我得到了二进制堆的良好实现，但它没有理想的缓存性能。为此，我开始研究二进制堆中的Van Emde Boas布局，这使我找到了二进制堆的"阻塞"版本，其中的诀窍是计算子索引和父索引。

虽然我能够做到这一点，但缓存行为（和运行时间）变得更糟。我认为问题是：引用的位置可能没有实现，因为它是 Java - 我不太确定使用对象数组是否真的使对象在 Java 中的内存中连续，任何人都可以确认这一点请问？

另外，我非常想知道Java的本机PriorityQueue使用什么样的数据结构，如果有的话。

Answer 1

通常，没有好方法可以强制队列中的对象占用连续的内存块。但是，有一些技术适用于特殊情况。

在高级别上，这些技术涉及使用字节数组和将数据"序列化"到数组和从数组"序列化"数据。如果您存储非常简单的对象，这实际上非常有效。例如，如果您要存储一堆 2D 点 + 权重，您可以简单地写入相当于权重、x 坐标、y 坐标的字节。

当然，此时的问题在于在偷看/弹出时分配实例。您可以通过使用回调来避免这种情况。

请注意，即使在存储的对象本身很复杂的情况下，使用类似于此的技术，即为权重保留一个数组，为实际对象保留一个单独的引用数组，也可以避免遵循对象引用，直到绝对必要。

回到存储简单的不可变值类型的方法，下面是您可以执行的操作的不完整草图：

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;
  }
  ...
}

Answer 2

我认为不会。 请记住，"对象数组"不是对象的数组，它们是对象引用的数组（不像基元数组，它实际上是基元的数组）。 我希望对象引用在内存中是连续的，但由于您可以随时使这些引用引用您想要的任何对象，我怀疑是否有任何保证引用数组引用的对象在内存中是连续的。

对于它的价值，关于数组的 JLS 部分没有提到任何连续性的保证。

Answer 3

我认为这里有一些 FUD。基本上无法想象数组的任何实现都不会使用连续内存。在描述.class文件格式时，JVM规范中使用该术语的方式非常清楚地表明没有考虑其他实现。

java.util.PriorityQueue 使用二进制堆，正如它在 Javadoc 中所说的那样，通过数组实现。