Реализация приоритетной очереди Java - локальность памяти

В общем, нет хорошего способа заставить ваши объекты в очереди занимать непрерывный кусок памяти. Однако есть некоторые методы, которые подходят для особых случаев.

На высоком уровне методы включают использование байтовых массивов и «сериализацию» данных в массив и из него. На самом деле это довольно эффективно, если вы храните очень простые объекты. Например, если вы храните набор 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;
  }

  ...
}

Я не думаю, что это было бы. Помните, что «массивы объектов» — это не массивы объектов, это массивы ссылок на объекты (в отличие от массивов примитивов, которые на самом деле являются массивами примитивов). Я ожидаю, что ссылки на объекты будут непрерывными в памяти, но поскольку вы можете сделать эти ссылки ссылающимися на любые объекты, которые вы хотите, когда захотите, я сомневаюсь, что есть какие-либо гарантии, что объекты, на которые ссылается массив ссылок, будут непрерывными в памяти.

Что бы это ни стоило, в разделе JLS о массивах говорится ничего о каких-либо гарантиях смежности.

Я думаю, что здесь происходит какой-то FUD. В принципе немыслимо, чтобы любая реализация массивов не использовала непрерывную память. И то, как этот термин используется в спецификации JVM при описании формата файла .class, ясно дает понять, что никакая другая реализация не рассматривается.

java.util.PriorityQueue использует двоичную кучу, как сказано в Javadoc, реализованную через массив.