[Перевод] 10 миллиардов целых чисел входят в массив16.10.2024 20:30

Как эксперимент с 64-битным Pharo Smalltalk удивил меня.

Хранение 10 миллиардов экземпляров SmallInteger в массиве в Pharo Smalltalk 13.0

32-битная вечеринка, которая не хочет заканчиваться

Я не программировал на Smalltalk профессионально со времен Y2K и в те времена сталкивался только с 32-битными версиями Smalltalk. Периодически я пробую разные штуки в Pharo‑диалекте Smalltalk, у которого есть 64-битная версия уже несколько лет. Я долго ждал появления опенсорс‑версии Smalltalk с поддержкой 64-битного адресного пространства. Я использовал 64-битные версии Java на протяжении последних 18 лет.

Я давно думал, когда уже Java сделает встроенную поддержку больших массивов, а именно массивов с длиной больше 2³¹-1. The Java Collections Framework и все фреймворки, реализующие встроенные интерфейсы коллекций, таких как Collection, List, Set, Map не поддерживают размер больше int. Максимальное количество значений, которые можно хранить в массиве Java — 2³¹-1. Для всех применений и целей это создает ограничение, позволяющее нам хранить чуть больше 2 миллиардов объектов или встроенных типов в массиве в Java. Есть сторонние библиотеки, которые предоставляют BigArrays, такие как fastutil, а также мы можем симулировать большие массивы самостоятельно за счет многомерных массивов в Java, но этим становится сложно управлять. Лучше использовать проверенную временем стороннюю библиотеку, чем натыкаться на сложно тестируемые и диагностируемые баги.

Мне было интересно, может ли 64-битный Pharo Smalltalk хранить больше 2³¹-1 элементов в массиве. Я знаю один способ проверить это. Мне потребуется много оперативной памяти для этого. На счастье, я купил новый Mac Book Pro M2 Max в прошлом году с 96 ГБ RAM, чтобы иметь возможность проводить эксперименты и тесты с большим использованием памяти.

Новый MacBook Pro M3 Max поддерживает до 128ГБ памяти. Это значительный прыжок по сравнению с прошлым годом, когда я купил MacBook Pro M2 Max с 96GB RAM. 128ГБ это в 2 раза больше по сравнению с моим десятилетним ведром Mac Pro на рабочем столе и в 8 раз больше десятилетнего MacBook Pro. Mac Pro из 2019 поддерживает аж до 1.5ТБ оперативной памяти. Текущая конфигурация Apple Silicon Mac Pro (2023) предлагает конфигурацию до 192ГБ, что в 3 раза больше моего 10-летнего Mac Pro. Я предполагаю, что через 10 лет мы увидим 256+ ГБ памяти в хай‑энд пользовательских ноутбуках и более терабайта на десктопах.

Примечание: Серверные машины могут иметь терабайты памяти уже сейчас.

Кому нужно больше 2 миллиардов элементов в массиве?

Мне никогда не требовалось хранить больше сотни миллионов элементов в List за последние 20 лет. Это все еще достаточно большое количество элементов и это было необходимо для моих задач в 2006 году. Я уверен, что есть люди, которые решают задачи, требующие хранения огромного количества данных в памяти.

На земле сейчас предположительно около 8.2 миллиардов человек. Для того, чтобы хранить ссылки на каждого человека в памяти, потребовалось бы 4 массива Java. Хранение 8.2 миллиардов простых объектов Person в памяти было бы очень затратно. Под простым объектом Person я подразумеваю класс Person с фамилией, именем и отчеством в виде String. Размер самого массива составил бы более 65ГБ (~8.2 миллиардов x 8 байт на ссылку). Затраты на экземпляры Person потребовало бы значительно больше памяти, чем мне доступно на MacBook Pro с 96 ГБ памяти. Давайте предположим примерно 8.2 миллиарда на 32 байта для экземпляров Person, что составило бы ~262ГБ. В сумме нам потребовалось бы 327ГБ памяти чтобы уместить всех людей включая их фамилии, имена и отчества в памяти. Мы могли бы создать пул из имен в виде String, в котором было бы примерно несколько сотен миллионов вхождений, так что нам потребовалось бы около 32 ГБ, а то и больше для хранения экземпляров String. На данный момент это не совсем доступно на обычном пользовательском железе. Это было бы возможно на хай‑энд серверах с терабайтами памяти.

Это заставило меня задуматься. Что если бы мы начали с объекта меньше, чем Person и вместо этого использовали, например, SmallInteger в Pharo Smalltalk. Я начал экспериментировать с созданием массивов больше 2³¹-1 в Pharo. В процессе эксперимента я узнаю, что в Pharo Smalltalk есть значительные оптимизации для SmallInteger. Вместо хранения ссылок на объекты SmallInteger, инлайнятся сами значения SmallInteger. Это ощущалось как обещанные нам в Project Valhalla типы значений из мира Java. Я понял это, немного покопавшись и экспериментируя с простым методом sizeInMemory. Я не сразу понял происходящее, когда сообщаемый размер экземпляров SmallInteger был равен нулю. Это давало мне понять, что SmallInteger обрабатывался в языке каким‑то особым образом. Я также был удивлен, что SmallInteger выходил за рамки максимального значения int в Java.

Transcript show: SmallInteger maxVal.

// Prints - 1152921504606846975
// SmallInteger  -> 1,152,921,504,606,846,975
// Max Java long -> 9,223,372,036,854,775,807

Это значение больше похоже на long в Java. Значение Long.MAX_VALUE в Java равно 9,223,372,036,854,775,807.

В этой статье рассказывается про максимальное значение SmallInteger в Smalltalk, а также про то как хранятся сами значения вместо ссылок. SmallInteger использует 61 бит вместо 64.

Наибольшим отличием между SmallInteger в Smalltalk и long в Java это то, что происходит при добавлении единицы к максимальному значению.

В Smalltalk мы получаем LargePositiveInteger. Динамическая типизация спешит на помощь.

Transcript cr; show: SmallInteger maxVal.
Transcript cr; show: SmallInteger maxVal class.
Transcript cr; show: SmallInteger maxVal + 1. 
Transcript cr; show: (SmallInteger maxVal + 1) class.

// Prints
// 1152921504606846975
// SmallInteger
// 1152921504606846976
// LargePositiveInteger

Когда мы добавляем 1 к максимальному значению SmallInteger, Smalltalk динамически создает экземпляры LargePositiveInteger. Это преимущество динамического языка, в котором все является объектом.

В Java мы получаем тихое, но потенциально смертельное переполнение.

System.out.println(BigInteger.valueOf(Long.MAX_VALUE));
System.out.println(BigInteger.valueOf(Long.MAX_VALUE + 1));

// Prints
// 9223372036854775807
// -9223372036854775808

Добавление 1 к максимальному значению long приводит к переполнению и результат становится отрицательным. Мы не можем динамически изменить тип из long в какой‑либо другой в Java. Что было long остается long, что было short — также остается short. Это один из тех моментов, когда статическая типизация вытягивает короткую соломинку. Мы научились находить обходные пути для этого в Java.

Давайте закончим на этом и перейдем к нашим экспериментам.

Эксперименты

Я не мог остановиться на реализации на Smalltalk, не попробовав реализовать это в Java. Pharo Smalltalk дал мне все нужные инструменты. Я использовал комбинацию библиотек fastutil и Eclipse Collections для повторения эксперимента в Java. Одна из положительных сторон Java в богатой экосистеме, участники которой создали множество решений для большей части задач, с которой вы можете столкнуться.

Версия Pharo Smalltalk

Я начал с 5 миллиардов экземпляров SmallInteger в Array в Pharo. После того, как это сработало, я увеличил общее количество до 8.2 миллиарда. Все еще работало. Потом я попробовал 10 миллиардов. Все еще работало. Я был сильно удивлен. Я не думал, что у меня достаточно памяти для хранения 10 миллиардов экземпляров. Это потому, что я не понимал на тот момент, как Smalltalk обрабатывает «экземпляры» SmallInteger.

Ниже приведен исходный код для эксперимента с 10 миллиардами. Вам потребуется 96 ГБ памяти, из которых около 85 должны быть свободны для выполнения этого кода. Можно уменьшить значение до 5 миллиардов, если у вас 64 ГБ памяти.

|array sum|

array := (1 to: 10000000000) collect: [ :each | each * 2 ].
sum := array sum.

Transcript cr; show: array size class.
Transcript cr; show: array size.
Transcript cr; show: sum.
Transcript cr; show: sum class.

(1 to: 10000000000 by: 1000000000) do: [ :index | Transcript cr; 
 show: 'index: '; 
 show: index; 
 show: ' value: '; 
 show: (array at: index);
 show: ' ';
 show: (array at: index) class ].

Transcript cr; show: 'Array memory (bytes) '; 
  show: array sizeInMemory. 
Transcript cr; show: 'Elements memory (bytes) '; 
  show: (array sumNumbers: #sizeInMemory). 

Результат кода ниже:

SmallInteger
10000000000
100000000010000000000
LargePositiveInteger
index: 1 value: 2 SmallInteger
index: 1000000001 value: 2000000002 SmallInteger
index: 2000000001 value: 4000000002 SmallInteger
index: 3000000001 value: 6000000002 SmallInteger
index: 4000000001 value: 8000000002 SmallInteger
index: 5000000001 value: 10000000002 SmallInteger
index: 6000000001 value: 12000000002 SmallInteger
index: 7000000001 value: 14000000002 SmallInteger
index: 8000000001 value: 16000000002 SmallInteger
index: 9000000001 value: 18000000002 SmallInteger
Array memory (bytes) 80000000016
Elements memory (bytes) 0

Эти результаты показывают, что у SmallInteger нет дополнительных затрат на сами экземпляры. Их значения инлайнятся в Array. Так что нам требуется только память под сам Array, что составляет около 80 ГБ.

Версия Java с fastutil

Ниже исходный код для эксперимента с 10 миллиардами в Java. Вам также потребуется 96 ГБ памяти, из которых 85 свободны. Я добавил аргумент ‑Xmx85g в командной строке. Вы также можете снизить количество до 5 миллиардов, если у вас 64 ГБ оперативной памяти. Для большого списка long использовалась fastutil. Для суммирования BigInteger — Eclipse Collections. Зачем потребовалось использовать BigInteger вы увидите дальше.

В первую очередь я добавил библиотеку fastutil в зависимости Maven.

    it.unimi.dsi
    fastutil
    8.5.14

Затем я написал тест, использующий LongBigArrayBigList для хранения 10 миллиардов long’ов. Это примерно равнозначно массиву из 10 миллиардов элементов SmallInteger в Smalltalk.

@Test
public void fastutilTenBillion()
{
    LongBigArrayBigList longs = new LongBigArrayBigList(10_000_000_000L);
    LongStream.rangeClosed(1, 10_000_000_000L)
            .forEach(l -> longs.add(l * 2));

    long sum = longs.longStream().sum();
    BigInteger bigSum = longs.longStream()
            .boxed()
            .collect(Collectors2.summingBigInteger(BigInteger::valueOf));

    System.out.println("size: " + longs.size64());
    System.out.println("long sum: " + sum);
    System.out.println("BigInteger sum: " + bigSum);

    for (long l = 0; l < 10_000_000_000L; l += 1_000_000_000L)
    {
        System.out.println("index: " + l + " value: " + longs.getLong(l));
    }
}

Результаты следующие:

size: 10000000000
long sum: 7766279641452241920
BigInteger sum: 100000000010000000000
index: 0 value: 2
index: 1000000000 value: 2000000002
index: 2000000000 value: 4000000002
index: 3000000000 value: 6000000002
index: 4000000000 value: 8000000002
index: 5000000000 value: 10000000002
index: 6000000000 value: 12000000002
index: 7000000000 value: 14000000002
index: 8000000000 value: 16000000002
index: 9000000000 value: 18000000002

Теперь, первое что вы вероятно заметите, если не сталкивались с этим — в Java индексы начинаются с 0, а в Smalltalk — с 1. Эти значения корректны. Нам нужно лишь помнить это при сравнении результатов.

Другой момент, это то что суммы long и BigInteger отличаются. Но почему?

Следующий тест покажет нам причины:

@Test
public void longMaxValue()
{
    BigInteger maxLong = BigInteger.valueOf(Long.MAX_VALUE);
    BigInteger sum = new BigInteger("100000000010000000000");
    System.out.println(maxLong);
    System.out.println(sum);
}

Результаты:

9223372036854775807    // Max Long Value in Java
100000000010000000000  // Sum of 10 billion long values

Максимальное значение long на два разряда короче, чем сумма. Сумма десяти миллиардов чисел, умноженных на 2, составляет значение, превышающее максимальное значение long в Java. Поэтому мне потребовалось собрать BigInteger для суммы чисел из String — само значение слишком велико для long. Я изначально не предполагал, что этот тест приведет к переполнению значения long, это более характерно для значений int. Максимальное значение long ОГРОМНО, но, как показала практика, недостаточно огромно.

Когда я понял, что сумма некорректна, я решил попробовать использовать Collectors2.summingBigInteger() Collector из Eclipse Collections. Это неплохо справлялось с задачей с одним недостатком — мне требовалось упаковывать значения long из LongStream в Long и затем повторно в BigInteger. Возможно, я бы придумал способ просто использовать метод collect на LongStream, если бы продолжил разбираться с кодом чуть дольше, но это потребовало бы mutating result, так что я решил не заморачиваться.

Размышления об ограничениях

Большей части разработчиков на данный момент не нужны массивы длиной больше 2³¹-1 элементов. Это скорее всего будет справедливо и в следующем году. Но на протяжении 5, 10, 20 лет эта цифра будет постепенно затрагивать все больше разработчиков по мере распространения работы с большими объемами данных. Коллекции размером в 2³¹-1 элементов могут стать более сложными в использовании. У нас уже есть готовые решения для Java, если нам нужна сумма больше int или long. Иногда может быть трудно писать быстро и корректно работающий код, когда упираешься в лимиты примитивов или массивов.

В конце 1980х и начале 1990х никому не требовалось больше 640К ОЗУ. Теперь мы можем приобрести 128ГБ на пользовательских ноутбуках. Наши правнуки, возможно, будут смеяться, когда услышат, как мы страдали, используя 64-битные вычисления. Тенденции в железе говорят нам, что прогресс не останавливается.

Когда мы сталкиваемся с ограничениями в железе или софте, нам приходится находить решения. Я работал в условиях с ограниченным количеством памяти с момента, когда начал профессиональную разработку в конце 1980х. Железо и софт всегда находили способ идти в ногу со временем. И когда этого не происходит, нам приходится становиться изобретательными.

У Java есть много важных проблем, которые необходимо решить и я не уверен, когда проблема максимального размера массива станет приоритетной. Я предполагаю, что в следующем десятилетии. И пока этого не произойдет, такие библиотеки как fastutil могут помочь решать задачи уже сейчас.

Вещь, которая продолжает восхищать меня в Smalltalk — это способность адаптироваться. Добавь еще немного — и вот, казалось бы, ты должен лететь с обрыва, но нет — Smalltalk приятно удивит тебя и вернет другой тип, способный обработать твой запрос. И мне часто не хватает этой его особенности.

© Habrahabr.ru