Как я могу написать на Java структуру данных, подобную массиву, которая использует длинные индексы, используя современные небезопасные API?

Массивы в Java ограничены Integer.MAX_VALUE по начальной емкости и индексируемым элементам (около 2 миллиардов). Я хотел бы написать класс структуры данных, который вместо этого использует long.

Я знаю, что широко распространены два метода:

  1. Используйте массив массивов
  2. Используйте API в sun.misc.Unsafe, чтобы вручную выделять большие фрагменты памяти и получать к ним доступ.

Я не хочу использовать массив массивов, и использование sun.misc.Unsafe категорически не рекомендуется, поскольку приводит к появлению предупреждений компиляции, которые невозможно отключить обычными методами.

Начиная с Java 9, начались попытки стандартизировать и заменить sun.misc.Unsafe добавлением java.lang.invoke.VarHandle в JEP 193 . Затем в Java 22 было добавлено java.lang.foreign.MemorySegment в JEP 454 . JEP 471, который появится в Java 23, объявит устаревшие методы доступа к памяти в sun.misc.Unsafe и будет удален.

Итак, похоже, что должен быть способ использовать существующие API VarHandle и MemorySegment для записи длинного массива на Java. Как мне это сделать?

Любопытный. Зачем вам нужен массив длиннее Integer.MAX_VALUE?. Это огромный объем данных (даже для примитивного массива), который нужно хранить в памяти, что можно считать нормальным. И из-за этого ограничения, возможно, Java не является подходящим языком для этого.

WJS 06.06.2024 18:02

@WJS Может быть вариант использования, когда массив и индексы работают вместе сложным образом. Но за исключением некоторых языков, таких как JavaScript, где массив на самом деле является картой, Java резервирует выделенную память. Так что да, для Java такой большой массив кажется немного странным.

Slevin 06.06.2024 18:07

@Slevin Возможно, альтернативой будет карта с измененными inititial capacity и load factor. По крайней мере, это поддержало бы «индексы».

WJS 06.06.2024 18:12

Необходимость иметь структуру данных, содержащую более 2 миллиардов элементов, не является странным требованием. Это для давно существующей программы проверки моделей TLA+, которая была написана на Java примерно в 2000 году. Это не новый проект, в котором я могу выбрать язык, и будьте уверены, это не тот язык, с которым вы не сможете справиться. более 2 миллиардов элементов.

ahelwer 06.06.2024 18:36

Я был бы очень удивлен, если бы существовал подход получше, чем массивы массивов.

Louis Wasserman 06.06.2024 19:03

неполная идея: class BigIntArray { ValueLayout.OfInt LAYOUT = ValueLayout.JAVA_INT_UNALIGNED; BigIntArray(long length) { memory = Arena.ofAuto().allocate(LAYOUT, length); } int get(long index) { return memory.get(LAYOUT, index); } void set(long index, int value) { memory.set(LAYOUT, index value); } }

user85421 06.06.2024 20:01
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
4
6
172
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы можете использовать SegmentAllocator::allocate(MemoryLayout,long) для создания MemorySegment , который можно использовать как массив «объектов», представленных заданным MemoryLayout. Затем вы можете обернуть сегмент в класс Java, чтобы инкапсулировать «доступ к массиву».

Обратите внимание, что это означает, что данные должны иметь возможность помещаться в память вне кучи. Другими словами, данные должны быть примитивом Java или, для более сложных типов, MemorySegment. Вы не сможете заполнить массив произвольными ссылочными типами Java. Если вы хотите обрабатывать сложные элементы как объекты Java, вам придется написать класс, который обертывает MemorySegment. По крайней мере, это единственный известный мне подход.


Примитивные типы

Для примитивных типов это относительно просто:

import java.lang.foreign.MemorySegment;
import java.lang.foreign.SegmentAllocator;
import java.lang.foreign.ValueLayout;
import java.util.Objects;

public final class LargeIntArray {

  public static final ValueLayout.OfInt LAYOUT = ValueLayout.JAVA_INT_UNALIGNED;
  
  private final MemorySegment segment;
  private final long length;

  public LargeIntArray(SegmentAllocator allocator, long length) {
    this.segment = allocator.allocate(LAYOUT, length);
    this.length = length;
  }

  public MemorySegment address() {
    return MemorySegment.ofAddress(segment.address());
  }

  public int get(long index) {
    return segment.getAtIndex(LAYOUT, index);
  }

  public void set(long index, int element) {
    segment.setAtIndex(LAYOUT, index, element);
  }

  public long length() {
    return length;
  }
}

Для каждого из примитивных типов Java существует ValueLayout.OfXXX интерфейсов.


Сложные типы

Для более сложных типов данных вы будете работать с MemorySegment вместо примитивных типов:

import java.lang.foreign.AddressLayout;
import java.lang.foreign.MemoryLayout;
import java.lang.foreign.MemorySegment;
import java.lang.foreign.SegmentAllocator;
import java.lang.foreign.ValueLayout;

public final class LargeArray {

  private final MemorySegment segment;
  private final long length;
  private final AddressLayout layout;

  public LargeArray(SegmentAllocator allocator, MemoryLayout elementLayout, long length) {
    this.segment = allocator.allocate(elementLayout, length);
    this.layout = ValueLayout.ADDRESS.withTargetLayout(elementLayout);
    this.length = length;
  }

  public AddressLayout layout() {
    return layout;
  }

  public MemorySegment address() {
    return MemorySegment.ofAddress(segment.address());
  }

  public MemorySegment get(long index) {
    return segment.getAtIndex(layout, index);
  }

  public void set(long index, MemorySegment element) {
    segment.setAtIndex(layout, index, element);
  }

  public long length() {
    return length;
  }
}

Улучшенная инкапсуляция

Одним из потенциальных улучшений является создание класса Java, который обертывает MemorySegment, представляющий «объекты». Это сделает работу с массивом более естественной на стороне Java. Во-первых, вам нужен общий способ сопоставления MemorySegment и класса Java:

import java.lang.foreign.MemoryLayout;
import java.lang.foreign.MemorySegment;
import java.util.Objects;
import java.util.function.Function;

public interface ElementDescriptor<T> {

  public static <T> ElementDescriptor<T> of(
      MemoryLayout layout,
      Function<MemorySegment, T> toElement,
      Function<T, MemorySegment> toAddress) {
    Objects.requireNonNull(layout);
    Objects.requireNonNull(toElement);
    Objects.requireNonNull(toAddress);
    return new ElementDescriptor<>() {
      @Override
      public MemoryLayout layout() {
        return layout;
      }

      @Override
      public T elementFrom(MemorySegment segment) {
        if (segment.equals(MemorySegment.NULL)) {
          return null;
        }
        return toElement.apply(segment);
      }

      @Override
      public MemorySegment addressOf(T element) {
        if (element == null) {
          return MemorySegment.NULL;
        }
        return toAddress.apply(element);
      }
    };
  }

  MemoryLayout layout();

  T elementFrom(MemorySegment segment);

  MemorySegment addressOf(T element);
}

Тогда вам нужно обновить LargeArray для работы с вышеперечисленным:

import java.lang.foreign.AddressLayout;
import java.lang.foreign.MemorySegment;
import java.lang.foreign.SegmentAllocator;
import java.lang.foreign.ValueLayout;

public final class LargeArray<T> {

  private final MemorySegment segment;
  private final long length;
  private final AddressLayout layout;
  private final ElementDescriptor<T> descriptor;

  public LargeArray(SegmentAllocator allocator, long length, ElementDescriptor<T> descriptor) {
    this.segment = allocator.allocate(descriptor.layout(), length);
    this.layout = ValueLayout.ADDRESS.withTargetLayout(descriptor.layout());
    this.length = length;
    this.descriptor = descriptor;
  }

  public AddressLayout layout() {
    return layout;
  }

  public MemorySegment address() {
    return MemorySegment.ofAddress(segment.address());
  }

  public T get(long index) {
    return descriptor.elementFrom(segment.getAtIndex(layout, index));
  }

  public void set(long index, T element) {
    segment.setAtIndex(layout, index, descriptor.addressOf(element));
  }

  public long length() {
    return length;
  }
}

И, наконец, вам нужна структура данных. Например, вот структура Point с координатами x и y:

import static java.lang.foreign.ValueLayout.JAVA_INT;

import java.lang.foreign.MemoryLayout;
import java.lang.foreign.MemoryLayout.PathElement;
import java.lang.foreign.MemorySegment;
import java.lang.foreign.SegmentAllocator;
import java.lang.foreign.StructLayout;
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.Objects;

public final class Point {

  public static final StructLayout LAYOUT;
  public static final ElementDescriptor<Point> DESCRIPTOR;

  private static final VarHandle X;
  private static final VarHandle Y;

  static {
    LAYOUT = MemoryLayout.structLayout(JAVA_INT.withName("x"), JAVA_INT.withName("y"));

    var x = LAYOUT.varHandle(PathElement.groupElement("x"));
    X = MethodHandles.insertCoordinates(x, 1, 0L);

    var y = LAYOUT.varHandle(PathElement.groupElement("y"));
    Y = MethodHandles.insertCoordinates(y, 1, 0L);

    DESCRIPTOR = ElementDescriptor.of(LAYOUT, Point::new, Point::address);
  }

  private final MemorySegment segment;

  public Point(SegmentAllocator allocator) {
    segment = allocator.allocate(LAYOUT);
  }

  public Point(MemorySegment segment) {
    this.segment = Objects.requireNonNull(segment);
  }

  public MemorySegment address() {
    return MemorySegment.ofAddress(segment.address());
  }

  public int getX() {
    return (int) X.get(segment);
  }

  public void setX(int x) {
    X.set(segment, x);
  }

  public int getY() {
    return (int) Y.get(segment);
  }

  public void setY(int y) {
    Y.set(segment, y);
  }

  @Override
  public String toString() {
    return "Point(x = " + getX() + ", y = " + getY() + ")";
  }
}

Пример использования

Вот пример использования LargeArray<Point>:

import java.lang.foreign.Arena;

public class Main {

  public static void main(String[] args) throws Throwable {
    try (var arena = Arena.ofConfined()) {
      var array = new LargeArray<Point>(arena, 10L, Point.DESCRIPTOR);

      // populate array
      for (long i = 0; i < array.length(); i++) {
        var point = new Point(arena);
        point.setX((int) i);
        point.setY((int) i * 2);
        array.set(i, point);
      }

      // show modification of element in array
      var midPoint = array.get(5L);
      midPoint.setX(42);
      midPoint.setY(117);

      // print array contents
      for (long i = 0; i < array.length(); i++) {
        System.out.printf("array[%d] = %s%n", i, array.get(i));
      }
    }
  }
}

Выход:

array[0] = Point(x=0, y=0)
array[1] = Point(x=1, y=2)
array[2] = Point(x=2, y=4)
array[3] = Point(x=3, y=6)
array[4] = Point(x=4, y=8)
array[5] = Point(x=42, y=117)
array[6] = Point(x=6, y=12)
array[7] = Point(x=7, y=14)
array[8] = Point(x=8, y=16)
array[9] = Point(x=9, y=18)

Примечания

Несколько примечаний:

  • Приведенные выше примеры не обязательно являются лучшими способами реализации «больших массивов» с помощью FFM.

  • Возможно, вы захотите реализовать классы массива Iterable.

  • Возможно, вы захотите добавить в классы массива один или несколько конструкторов, принимающих MemorySegment. Это облегчит использование массивов, выделенных в собственном коде. В таких случаях убедитесь, что MemorySegment имеет правильный размер; см. методы reinterpret. Последнее также применимо к таким классам, как Point.

  • Возможно, вы захотите добавить возможность выбора между выровненным и невыровненным.

  • Возможно, лучше использовать segment.reinterpret(0L) для возврата адреса массива/структуры данных, чтобы возвращаемый MemorySegment имел ту же область видимости, а не всегда находился в глобальной области видимости.

Другие вопросы по теме