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

Question

我正在尝试在Java中实现一个高效的优先队列。我已经得到了一个二叉堆的良好实现，但它的缓存表现并不理想。因此，我开始学习Van Emde Boas布局中的二叉堆，这使我了解到了“阻塞”版本的二叉堆，其中诀窍是计算子节点和父节点的索引。

虽然我已经做到了这一点，但缓存行为（和运行时间）变得更糟了。我认为问题是：可能没有实现引用局部性，因为这是Java - 我不确定在Java中使用对象数组是否会使对象在内存中连续，请有人确认一下吗？ 此外，我也非常想知道Java的本地PriorityQueue使用哪种数据结构，如果有人知道的话。

- nuno

---

对象数组是对象的引用数组。对象位于堆中。很抱歉，没有任何局部性。 - Vladimir Dyuzhev

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

  ...
}

- Dilum Ranatunga

---

虽然我相信这样的版本会在缓存内存方面表现良好，但当我寻找像连续元素这么简单的东西时，它肯定会产生很多开销。无论如何，感谢您的关心 =） - nuno

是的，当您存储大量元素但每次只访问其中少数元素时，这种方法是可行的。 - Dilum Ranatunga

顺便问一下，在这个实现中，你是用什么样的数据结构来存储元素的？是字节数组、字节缓冲区还是类似的东西？ - nuno

是的，一个字节数组。这是PQ算法的经典数组，其中元素[0]位于顶部，元素[2i]，元素[2i + 1]的优先级低于元素[i]。唯一的细节是所有索引都需要乘以entryByteSize。 - Dilum Ranatunga

Answer 2

我认为不会。请记住，“对象数组”不是对象数组，它们是对象引用的数组（与原始类型的数组不同，后者确实是原始类型的数组）。我期望对象引用在内存中是连续的，但由于您可以随时将这些引用引用到任何您想要的对象，我怀疑数组引用的对象是否在内存中是连续的。

就其价值而言，JLS关于数组的部分没有提到任何连续性的保证。

- QuantumMechanic

---

有没有一种方法可以强制Java数据结构中的对象连续？我一直在浏览，发现了这个https://dev59.com/p1HTa4cB1Zd3GeqPTamw#4107431。我想我会尝试这个，虽然我不太自信它在堆上下文中表现良好。谢谢。 - nuno

只有基本类型的数组可以将它们存储在同一堆块中。没有办法强制将 Object 的子类放置在相邻的地址中。 - Vladimir Dyuzhev

为了澄清这个话题，现在我的研究已经更加清晰了。Java不允许数组元素的连续性，但是有一些需要考虑的问题，比如分配时间（如果元素紧密实例化，JVM / GC很可能会分配连续的空间），此外，如果我们需要更深入地了解，还有一些JVM级别和垃圾回收实现的优化点（例如Jikes通过识别“热”字段来实现局部优化GC）。 - nuno

Answer 3

我认为这里存在一些误解。任何数组的实现都基本上不可避免地使用连续的内存。而在JVM规范中描述.class文件格式时使用的术语非常清楚，没有考虑其他的实现方式。

java.util.PriorityQueue使用二叉堆，正如Javadoc中所述，它是通过数组实现的。

- user207421

---

那么，值得尝试实现一个对缓存敏感/无视缓存的优先队列（或者其他数据结构）吗？我了解到原生的Java优先队列使用了二叉堆，但我不知道它是基于数组的。然而，当我对比了我的版本和Java的优先队列时，发现Java的缓存行为要好得多 - 我想知道他们使用了什么样的方法来实现这一点。我已经搜索过了，但没有找到相关信息。 - nuno

他们似乎没有使用任何方法论，只是使用了一个相当基本的二叉堆实现。如果你想要对自己的代码进行评论，请发布它。 - user207421