Как эксперимент с 64-битным Pharo Smalltalk удивил меня.
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.
<dependency> <groupId>it.unimi.dsi</groupId> <artifactId>fastutil</artifactId> <version>8.5.14</version> </dependency>Затем я написал тест, использующий 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 приятно удивит тебя и вернет другой тип, способный обработать твой запрос. И мне часто не хватает этой его особенности.
ссылка на оригинал статьи https://habr.com/ru/articles/851200/
Добавить комментарий