Оглавление:

Геодата
Экскурс в формат файлов геодаты .l2j
- Ячейка (Cell/Layer Data)
- Виды блоков .l2j
Стартовые данные
Переиспользование FlatBlock
Одна высота в ComplexBlock
Базовая высота в ComplexBlock
Базовая высота в ComplexBlock и общий nswe
Мало разных высот в ComplexBlock
Мало разных высот в ComplexBlock и общий nswe
MultilayerBlock без пропусков
Индексированный MultilayerBlock
Индексированный MultilayerBlock до 32 слоев
GeoDriverBytes
GeoDriverBytesMmap
Заключение

C чего все началось

В позапрошлом году вышла статья https://habr.com/ru/articles/814529/ про синхронизацию позиции персонажа между клиентом и сервером в Lineage 2. После прочтения появилось желание перенести эту логику в свои сырцы от когда-то разрабатываемого сервера и, возможно, запустить его где-то для себя и старых друзей поразвлекаться. Понятное дело, что современного ПК с кучей рам, хорошим процом и nvme дисками при желании было бы за глаза даже для запуска тысяч игроков, но заниматься организацией доступа из дикого интернета на свой ПК желания не было, да и обеспечивать постоянный доступ - дело такое себе. В наличии была самая дешманная впска у хостера F с доменом, но с сильно ограниченными ресурсами: одно ядро и 512Мб рам. Мягко скажем, памяти маловато.

Наспех восстановил сырцы, актуализировал сборку под современные версии java и либ, запустил - потребление хипа примерно 400Мб на старте. Без геодаты. А с геодатой - 1200Мб.

И тут появился спортивный интерес влезть в 512Мб, да еще и с геодатой.

Результатом стал оптимизированный драйвер геодаты, зашаренный на гитхабе https://github.com/mosinnik/l2-geo, репорт о потенциальном баге в JDK и эта статья.

Геодата

Как выглядит геодата в клиенте. Скрин из https://www.youtube.com/watch?v=gdQb54ryFDQ

Что это такое можно понять по выдержке с сайта https://l2-scripts.ru/index.php?show_aux_page=48

Для чего она? Для мобов не существует стен как в принципе и для чаров, упёршись в стену и буксуя на месте вы всё таки меняете свои координаты, мобы проскакивают их шустрее. По скольку для мобов мир - ровное плато, агрессивные вас заметят и атакуют если окажетесь в их радиусе даже если находитесь за стеной и не видите их. Геодата поможет вам от этого избавиться, если сказать короче геодата - информация о всех препятствиях имеющихся в клиенте игры. Поэтому геодата существует для разных хроник, геодата интерлюда будет считаться не полной для эпилога к примеру.
Геодата это математическое описание территории, включая стены замков деревьев ит.п. ... с помощью геодаты сервер может отслеживать всех игроков и мобов относительно их территориального нахождение и не давать мобам стрелять и ходить сквозь стены а также игроки не могут проходить сквозь стены (особено используя ботов)
Если говорить нормальными словами, то это означет, что раньше ОТОБРАЖАЕМЫЕ стены и РЕАЛЬНЫЕ стены по расчетам сервера были несколько смещены относительно друг друга. С данным явлением визуально раньше можно было ознакомиться во многих катакомбах - это когда мобы в стенах или в полу, и приблизившись к стене есть реальный шанс в нее влипнуть.
Геодата(Geodata) - это инструмент, который позволяет проконтролировать некоторые действия клиента (а именно - передвижение и взаимодействие с другими объектами с точки зрения геометрического положения в пространстве). Вся карта представляет собой геометрическую сетку, которая состоит из конечного набора прямоугольников (в частном случае - квадратов), соединеных между собой по их сторонам.

Более подробно и наглядно в видео: https://www.youtube.com/watch?v=gdQb54ryFDQ

Нам важно из этого, что она используется иногда для построения пути и позволяет на стороне сервера проверить, видит ли один персонаж другого и может ли атаковать, т.е. фактически основные действия игроков и мобов.

Геодата у меня .l2j, найденная в закромах неизвестного происхождения, но для поиграться ее достаточно.

Экскурс в формат файлов геодаты .l2j

Вся карта в мире lineage 2 поделена на регионы. С каждыми новыми хрониками карта расширялась, и добавлялись новые регионы. Для Interlude таких регионов 176, хотя фактические непустая геодата есть только для 132.

Карта мира Lineage 2 Interlude с пронумерованными регионами

Размер каждого региона - 256х256 блоков. Каждый блок - 8х8 ячеек (cell). Каждая ячейка 16х16 игровых координат.

Немного цифр:

Блок - 8х8 ячеек (2^3) - 64 ячейки - 128х128 координат (2^7)
Регион - 256х256 блоков (2^8) - 65536 блоков - 4_194_304 ячеек - 32_768х32_768 координат (2^15)
Мир - 11х16 региона - 176 регионов - 11_534_336 блока - 738_197_504 ячеек - 360_448х524_288 игровых координат (X и Y соответственно).

Игровой мир Lineage 2 по высоте имеет размер 32768 (2^15) (координата Z от -16384 до 16383).

Ячейка (Cell/Layer Data)

Сервер должен понимать для каждой ячейки ее высоту и можно ли из нее попасть в соседнюю. Соседние ячейки те, которые соприкасаются по сторонам, таких 4 по каждому направлению, а диагональная информация не хранится и вычисляется при необходимости. Для хранения информации о возможности пройти нужно по одному биту на каждую сторону. Совокупность этих 4 бит в коде принято обозначать nswe по первым буквам сторон света.

Как ранее было уже сказано, для хранения 2^15 значений высоты нужно было бы выделить 15 бит информации. Но для целей сервера и оценки расстояний/высот супер точность не нужна, и можно обрезать часть информации в 3-х младших битах, сделав из высоты ближайшее кратное числу 8. Это накладывает отпечаток, но нам пока неважно.

Таким образом, на хранение высоты вместо 15 бит можно выделить 12, добавить к ним 4 бита nswe - 16 бит, что умещается в стандартный тип short.

Осталось только определить порядок следования:
- старшие биты [15, 4] - высота
- младшие [3, 0] - nswe

Пример формирования cellData и получения из него составных частей:

byte srcNswe = 0b1001;
short srcHeight = -2110;

System.out.println("srcHeight = 0b" + Integer.toBinaryString(srcHeight).substring(16));
// srcHeight = 0b1111011111000010

short cellData = (short) (((srcHeight & 0xFFFFFFF8) << 1) | srcNswe);

System.out.println("cellData = 0b" + Integer.toBinaryString(cellData).substring(16));
// cellData = 0b1110111110001001 

short height = (short) ((cellData & 0xFFFFFFF0) >> 1);

System.out.println("height = " + height);
System.out.println("height = 0b" + Integer.toBinaryString(height).substring(16));
// height = -2112
// height = 0b1111011111000000

byte nswe = (byte) (cellData & 0x000F);

System.out.println("nswe = 0b" + Integer.toBinaryString(nswe));
// nswe = 0b1001

Виды блоков .l2j

Формат .l2j пошел от L2J Server команды (https://l2jserver.com/) Их репа еще активна и исходный код блоков можно глянуть тут https://bitbucket.org/l2jserver/l2j-server-geo-driver/src/master/src/main/java/com/l2jserver/geodriver/blocks/.

Внутри одного .l2j файла хранятся данные одного региона, а значит, фиксированное количество блоков (65536). Для каждого блока записывается сначала 1 байт с типом блока, следом за которым идут данные самого блока. Формат данных внутри каждого типа блока различен и описан далее. За разбор данных блока отвечает код соответствующего класса (см. конструкторы классов).

FlatBlock

Код типа - 1.

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

В .l2j для такого блока хранится только высота, причем не смещенная и может быть не выровненная, т.к. нет необходимости хранить nswe.

Итого на такой блок выделяется 2 байта помимо типа.

Для получения высоты ячейки из такого блока достаточно вернуть сохраненную для всего блока без дополнительных манипуляций.

ComplexBlock

Код типа - 2.

Для более сложных случаев:

когда есть ячейки внутри блока с непроходимостью и нужно задействовать nswe. Например, есть непроходимых объекты на равнинной местности (деревья, камни, заборы и т.п.), и нужно предотвратить возможность персонажа пройти или выпустить стрелу через них насквозь
когда перепад высот значительный или нужно контролировать высоту более гранулярно. Как правило, это относится к лестницам и склонам
смешанные случаи, например, отвесная стена обрыва - в одном направлении можно без проблем переместиться (сверху вниз), а взобраться уже нельзя (снизу вверх), при этом надо контролировать большую разницу высот

В .l2j для такого блока хранится 8х8 = 64 ячейки и для каждой сохраняется выровненная высота и nswe как отмечено в разделе Ячейка (Cell/Layer Data).

Итого на такой блок выделяется 2х64 = 128 байт помимо типа. Данные после вычитки хранятся в массиве short[], как и были прочитаны из файла без трансформаций.

Для получения высоты ячейки или nswe из такого блока необходимо:

1) по переданным координатам вычислить смещение данных внутри массива - делается тривиальным способом, т.к. размеры фиксированы

int cellOffset = ((geoX & 0x07) << 3) + (geoY & 0x07);

// или в более читаемом виде 
int cellOffset = ((geoX % IBlock.BLOCK_CELLS_X) * IBlock.BLOCK_CELLS_Y) + (geoY % IBlock.BLOCK_CELLS_Y);

2) далее по этому смещению вычитываем из массива short и из него извлекаем высоту или nswe как было показано ранее в Ячейка (Cell/Layer Data).

MultilayerBlock

Код типа - 3.

Первые два типа блоков для каждой координаты (x, y) внутри блока могли выдать только одну высоту, однако в мире Lineage 2 есть подземелья, есть башни, есть пещеры, т.е. многоуровневые области, и на каждом уровне нужно хранить информацию о высоте этого уровня и nswe. В таких случаях используется MultilayerBlock.

В .l2j для такого блока также хранится 8х8 = 64 ячеек, но теперь их стоит воспринимать как столбец-ячейка, содержащий слои (layer). Важно отметить, что для любой координаты в блоке будет как минимум одна высота - в мире Lineage 2 нет дырок "в никуда", и даже под морем есть дно с геодатой. Но в пределах такого блока количество слоев в разных столбцах может быть разное.

Для такого столбца хранится количество слоев (layers count) и по каждому слою указывается высота и nswe в формате Ячейка (Cell/Layer Data).

Итого на такой блок выделяется не фиксированное количество памяти - по сбору статистики от 125 до 2950 байт. Данные после вычитки хранятся в массиве byte[], как и были прочитаны из файла без трансформаций.

Для получения высоты ячейки или nswe из такого блока необходимо уже потрудиться, т.к. мы не можем не то что сразу найти данные слоя, так еще позиция начала данных для конкретного столбца нам сходу неизвестна из-за нефиксированного количества слоев в предыдущих ячейках. Поэтому алгоритм следующий:

по переданным координатам вычисляем номер столбца N внутри блока - делается аналогично вычислению позиции ячейки для ComplexBlock
вычитываем все данные с начала блока, пропуская сами данные слоев - берем 1 байт с количеством слоев в столбце, считаем где начинается следующий, сдвигаем позицию к нему. И так делаем N раз
после получения смещения начала столбца N в массиве байт можно уже вычитать все относящиеся к нему данные и сразу обработать, например найти ближайший слой к переданной Z координате
по найденному подходящему слою уже возвращаем высоту или nswe

Как видно, на любой запрос есть вероятность обойти весь блок данных хоть и прыжками, но это 64 чтения количеств слоев в худшем случае.

Стартовые данные

Перед началом оптимизаций надо бы зафиксировать какие-то метрики для последующего сравнения.

Для оценки занимаемой памяти будет использоваться либа jol (org.openjdk.jol:jol-core), для бенчмарков - jmh.

В коде можно глянуть в тест loadAll, там загружаем все блоки геодаты в GeoDriver и выводим его мемори футпринт (GraphLayout.toFootprint()):

     COUNT       AVG       SUM   DESCRIPTION
    617883       322 199541800   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
   2698780       144 388624320   [S
   2698780        16  43180480   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
   7562313        16 120997008   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    617883        16   9886128   ru.mosinnik.l2eve.geodriver.blocks.MultilayerBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
  14195975           805755128   (total)

Пару слов о футпринте jol:
COUNT - число объектов (экземпляров/инстансов) такого-то класса
AVG - средний размер объекта в байтах
SUM - общее количество памяти, занимаемой всеми объектами данного класса
DESCRIPTION - класс или тип массива с классом
(total) - суммарные значения

Важно: если ComplexBlock хранит в себе только массив short[], то объем самого массива будет засчитан в статистику [S , т.е. SUM равное 43180480 для ComplexBlock означает сколько выделено на обслуживание объектов без самих массивов. Разделим 43180480 на 2698780 и получим 16 - AVG. Таким образом не получится из такой статистики напрямую оценить объем реально занимамой памяти одного блока - нужно запустить выдачу футпринта для конкретного экземпляра блока, и тогда статистика по одному блоку будет полезна. Нам сейчас достаточно общей статистики.

Итого на старте из исходных файлов .l2j суммарного объема 534Мб получилось в хипе 805Мб на 14.2кк объектов, которые так или иначе внутри экземпляра GeoDriver. Т.к. мы знаем что у нас всего три вида блоков, каждый из блоков либо не содержит массива (для Flat), либо содержит массив short (для Complex), либо массив byte (для Multilayer), то можно прикинуть что:

FlatBlock - 7.5кк штук, занимают 121Мб
ComplexBlock - 2.7кк штук, занимают 43+388=431Мб
MultilayerBlock - 617к штук, занимают 10+199=219Мб
[L...IBlock - массив ссылок на блоки внутри регионов, 166 штук (по числу загруженных регионов) на 43.5Мб - это только массив ссылок на блоки и фактически не несет в себе полезных данных (позже мы к этому вернемся)

Это будет отправная точка для оптимизаций.

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

Первой оптимизацией очевидно будет переиспользовать экземпляры FlatBlock, т.к. у нас их аж 7.2кк, хотя высот в клиенте всего 32к - разница в два порядка. Сбор статистики показал, что всего встречается 1498 различных высоты во всех FlatBlock.

Банальная хешмапа и computeIfAbsent для хранения и переиспользования блоков и вот результат:

     *COUNT*       AVG       SUM   DESCRIPTION
    617883       322 199541800   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
   2698780       144 388624320   [S
   2698780        16  43180480   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
      1498        16     23968   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    617883        16   9886128   ru.mosinnik.l2eve.geodriver.blocks.MultilayerBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
   6635160           684782088   (total)

Теперь осталось 1498 экземпляров FlatBlock и выделенная память теперь только 24кб, считай 121Мб (15% от предыдущего) на ровном месте. Хорошее начало, но так легко больше не будет.

Одна высота в ComplexBlock

После работ с FlatBlock возникла мысль, а нет ли таких ComplexBlock, у которых тоже одна высота как у FlatBlock. Сбор статистики показал, что да есть такие, хоть и количество небольшое - всего 23821, но идея пришла, надо реализовать.

Сбор статистики и первичная предобработка тут и для последующих блоков реализована в BlockManager, в нем как раз и происходит отбор среди ComplexBlock тех, которые с одной высотой. Для них уже производится последующая пересборка в виде нового класса.

Реализация в классе OneHeightComplexBlock, код типа - 4.

Внутри OneHeightComplexBlock будет поле типа short для хранения единой высоты и массива byte[] для хранения nswe каждой ячейки - получается по 1 байту на 64 nswe и 2 байта на высоту - 64 + 2 = 66 байт. В теории экономия по 128-66=62 байт на блок, всего 62 х 23821=1_476_902 байт экономии. Не густо как и ожидалось, но это экономия.

Смотрим результат:

     COUNT       AVG       SUM   DESCRIPTION
    641704       313 201447480   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
   2674959       144 385194096   [S
   2674959        16  42799344   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
      1498        16     23968   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    617883        16   9886128   ru.mosinnik.l2eve.geodriver.blocks.MultilayerBlock
     23821        24    571704   ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
   6635160           683448112   (total)

JOL показывает выигрыш в 1_333_976 байта (0.2% от предыдущего). Расхождение с тем что ожидали на 142_926 байта, что ровно по 6 байт на блок, ищем где просчитался.

Посмотрим GraphLayout блоков по отдельности:

ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock@685cb137d footprint:
     COUNT       AVG       SUM   DESCRIPTION
         1       144       144   [S
         1        16        16   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
         2                 160   (total)
         
ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock@3bfdc050d footprint:
     COUNT       AVG       SUM   DESCRIPTION
         1        80        80   [B
         1        24        24   ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock
         2                 104   (total)

И детальнее ClassLayout (ClassLayout.parseInstance(X).toPrintable()):

ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock object internals:
OFF  SZ      TYPE DESCRIPTION               VALUE
  0   8           (object header: mark)     0x00000342e589b811 (hash: 0x42e589b8; age: 2)
  8   4           (object header: class)    0x0108d8e8
 12   4   short[] ComplexBlock.data         [-9941, -9845, -9765, -9685, -9605, -9509, -9429, -9345, -9941, -9845, -9765, -9685, -9605, -9509, -9429, -9345, -9941, -9845, -9765, -9685, -9605, -9509, -9429, -9345, -9941, -9845, -9765, -9685, -9605, -9509, -9429, -9345, -9941, -9845, -9765, -9685, -9605, -9509, -9429, -9345, -9941, -9845, -9765, -9685, -9605, -9509, -9429, -9345, -9941, -9845, -9765, -9685, -9605, -9509, -9429, -9345, -9941, -9845, -9765, -9685, -9605, -9509, -9429, -9345]
Instance size: 16 bytes
Space losses: 0 bytes internal + 0 bytes external = 0 bytes total

---

ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock object internals:
OFF  SZ     TYPE DESCRIPTION                    VALUE
  0   8          (object header: mark)          0x000001dfee028011 (hash: 0xdfee0280; age: 2)
  8   4          (object header: class)         0x0108d1f0
 12   2    short OneHeightComplexBlock.height   -4992
 14   2          (alignment/padding gap)        
 16   4   byte[] OneHeightComplexBlock.nswes    [15, 7, 15, 15, 15, 15, 15, 15, 15, 7, 15, 15, 15, 15, 15, 15, 15, 7, 15, 15, 15, 15, 15, 15, 15, 7, 15, 15, 15, 15, 15, 15, 15, 7, 15, 15, 15, 15, 15, 15, 15, 7, 15, 15, 15, 15, 15, 15, 15, 7, 15, 15, 15, 15, 15, 15, 15, 7, 15, 15, 15, 15, 15, 15]
 20   4          (object alignment gap)         
Instance size: 24 bytes
Space losses: 2 bytes internal + 4 bytes external = 6 bytes total

На выравнивании (alignment/padding gap) внутренней переменной для высоты и ссылки на массив теряем искомые 6 байт. Можно было высоту и интом хранить. Жаль, но оставляем.

Получение высоты - возврат сохраненной, а nswe ищется по аналогии с ComplexBlock.

(Т.к. nswe занимает всего 4 бита, а в байте 8, то можно было бы уплотнить массив nswe, храня по два на байт. Но тогда сильно бы усложнилась логика обработки, а экономии какой-то значимой не добиться, поэтому пока остается как есть. Хотя далее я это все-равно реализую в другом типе блоков.)

Базовая высота в ComplexBlock

Идем дальше. В статистике было найдено достаточно большое количество ComplexBlock блоков, у которых высоты ячеек не сильно отличаются между собой. А тех, у которых разница (дельта) между минимальной и максимальный высотами не превышает 120 нашлось 1_520_960. Много, хороший потенциал.

120 - не просто число, а максимальное число, влезающее в 7 бит с зануленными младшими 3 битами. Ввиду выравнивания мы знаем, что эти младшие биты константно занулены и остаются 4 значащих бита. Если сохранить минимальную высоту и считать ее базовой, а для каждой ячейки пересобрать данные, заменив 16 битный short на 8 битный byte, то в этом байте старшие 4 бита можно отвести под кодирование дельты от базовой высоты, а младшие оставить для nswe, как и до этого.

Реализация в классе BaseHeightComplexBlock, код типа - 5.

Внутри BaseHeightComplexBlock храним базовую высоту - short (2 байта) и массив byte[] (по байту на ячейку). Суммарно 2+64=66 байт, как и у OneHeightComplexBlock. Ожидаемая экономия на один блок аналогично 62, но вспоминая OneHeightComplexBlock и ClassLayout сразу прикидываем, что экономия будет 56 байт на блок. Итого ожидаемое 56 х 1_520_960 = 85_173_760, 85Мб (12% от предыдущего), солидно.

Смотрим:

     COUNT       AVG       SUM   DESCRIPTION
   2162664       149 323124280   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
   1153999       144 166175856   [S
   1520960        24  36503040   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightComplexBlock
   1153999        16  18463984   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
      1498        16     23968   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    617883        16   9886128   ru.mosinnik.l2eve.geodriver.blocks.MultilayerBlock
     23821        24    571704   ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
   6635160           598274352   (total)

И да действительно 683448112-598274352=85_173_760, как и ожидалось.

Получение высоты и nswe производится фактически как и для с ComplexBlock, но для высоты идет суммирование базовой и дельты. Ну и добавляется немного битовой магии для восстановления самой дельты из 4 бит.

private int getCellHeight(int geoX, int geoY) {
	int cellOffset = ((geoX & 0x07) << 3) + (geoY & 0x07);
	int height = (data[cellOffset] & 0x0000_00F0) >> 1;
	return height + baseHeight;
}

Базовая высота в ComplexBlock и общий nswe

Как ни странно, среди ComplexBlock были встречены такие, у которых одинаковый nswe у всех ячеек. Как правило, это склоны и лестницы. Общий nswe можно вынести в поле, тогда для подхода из BaseHeightComplexBlock у нас освобождается 4 бита и можно не ограничиваться дельтой в 120, а искать до 2040 - 11 бит (8 значащих и 3 всегда зануленных). Тогда во внутреннем массиве byte будет храниться только дельта от базовой высоты.

Подходящих под такие условия блоков набралось 1_531_897, но часть из них подпадают и под условия для предыдущего BaseHeightComplexBlock. Чистых без пересекаемых - 441_778. Нужно будет определиться какой из типов лучше.

Реализация в классе BaseHeightOneNsweComplexBlock, код типа - 6.

Внутри BaseHeightOneNsweComplexBlock храним высоту - short (2 байта) и массив byte[] - по байту на ячейку и еще nswe в байтовом поле. Суммарно 2+64+1=67 байт. Ожидаемая экономия на один блок аналогично 61, но опять же ClassLayout:

ru.mosinnik.l2eve.geodriver.blocks.BaseHeightOneNsweComplexBlock object internals:
OFF  SZ     TYPE DESCRIPTION                                VALUE
  0   8          (object header: mark)                      0x0000038953734009 (hash: 0x89537340; age: 1)
  8   4          (object header: class)                     0x0108e2a0
 12   2    short BaseHeightOneNsweComplexBlock.baseHeight   -4576
 14   1     byte BaseHeightOneNsweComplexBlock.nswe         7
 15   1          (alignment/padding gap)                    
 16   4   byte[] BaseHeightOneNsweComplexBlock.data         [-110, 125, 104, 83, 63, 42, 21, 0, -110, 125, 104, 83, 63, 42, 21, 0, -110, 125, 104, 83, 63, 42, 21, 0, -110, 125, 104, 83, 63, 42, 21, 0, -110, 125, 104, 83, 63, 42, 21, 0, -110, 125, 104, 83, 63, 42, 21, 0, -110, 125, 104, 83, 63, 42, 21, 0, -110, 125, 104, 83, 63, 42, 21, 0]
 20   4          (object alignment gap)                     
Instance size: 24 bytes
Space losses: 1 bytes internal + 4 bytes external = 5 bytes total

А значит будет опять же не 61, а 56 байт экономии на блок - получается для экономии памяти не важно будет ли блок отнесен к BaseHeightComplexBlock или к BaseHeightOneNsweComplexBlock.

Приоритет BaseHeightOneNsweComplexBlock:

     COUNT       AVG       SUM   DESCRIPTION
   2604442       137 358466520   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
    712221       144 102559824   [S
    430841        24  10340184   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightComplexBlock
   1531897        24  36765528   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightOneNsweComplexBlock
    712221        16  11395536   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
      1498        16     23968   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    617883        16   9886128   ru.mosinnik.l2eve.geodriver.blocks.MultilayerBlock
     23821        24    571704   ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
   6635160           573534784   (total)

Приоритет BaseHeightComplexBlock:

     COUNT       AVG       SUM   DESCRIPTION
   2604442       137 358466520   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
    712221       144 102559824   [S
   1520960        24  36503040   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightComplexBlock
    441778        24  10602672   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightOneNsweComplexBlock
    712221        16  11395536   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
      1498        16     23968   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    617883        16   9886128   ru.mosinnik.l2eve.geodriver.blocks.MultilayerBlock
     23821        24    571704   ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
   6635160           573534784   (total)

Разница только в количествах объектов каждого типа, а total ожидаемо одинаковый в обоих случаях, а экономия составила 24_739_568 байта, почти 25Мб (4% от предыдущего).

Получение высоты производится фактически как и для с BaseHeightComplexBlock с поиском данных дельты ячейки и прибавка базовой высоты, а nswe возвращается как есть из поля. Тут можно было бы предположить, что в этой реализации будет проще отдавать nswe и это позволит получить прирост производительности над предыдущим вариантом - проверим позже в бенчах (спойлер: оба варианта проигрывают обычному CompexBlock).

Промежуточный итог: к этому моменту нас уже экономия 232Мб (28.8% от изначального), треть срезали, но еще даже не близко заветные 512Мб даже под геодату.

Мало разных высот в ComplexBlock

Смотрим статистику дальше, что можно еще придумать. Раз были блоки, у которых дельта по высоте меньше 120, т.е. всего 16 разных значений дельт, то наверняка есть такие блоки, у которых тоже может быть 16 различных значений хоть и с большей дельтой. Тогда можно будет 4 бита, использованные под дельту перепрофилировать в индекс в массиве просто высот.

Такой подход называется сжатием с использованием словаря (dictionary compression).

Статистика показывает, что таких блоков 1_564_633, но часть опять же подходит и под BaseHeightComplexBlock. Тех что не пересекаются 87_144, маловато, но оценим.

Реализация в классе FewHeightsComplexBlock, код типа - 7.

Внутри FewHeightsComplexBlock содержится массив short[] для высот и массив byte[] для хранения nswe и индексов - получается по 1 байту на nswe с индексом на каждую ячейку и 2хN байт на высоты. Высот может быть до 16. Получается размер от 64+2 до 64+32. Ожидаемая экономия от 32 до 62, в среднем какая-то экономия будет. Замеряем:

     COUNT       AVG       SUM   DESCRIPTION
   2691586       135 365438040   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
    712221       131  93405400   [S
    430841        24  10340184   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightComplexBlock
   1531897        24  36765528   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightOneNsweComplexBlock
    625077        16  10001232   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
     87144        24   2091456   ru.mosinnik.l2eve.geodriver.blocks.FewHeightsComplexBlock
      1498        16     23968   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    617883        16   9886128   ru.mosinnik.l2eve.geodriver.blocks.MultilayerBlock
     23821        24    571704   ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
   6722304           572049032   (total)

Выхлоп - 1_485_752, 1.5Мб (0.26% к предыдущему). Средняя экономия на новый тип блока 17 байт. Далеко от ожидаемого, смотрим ClassLayout:

ru.mosinnik.l2eve.geodriver.blocks.FewHeightsComplexBlock object internals:
OFF  SZ      TYPE DESCRIPTION                      VALUE
  0   8           (object header: mark)            0x000003e6b17a1811 (hash: 0xe6b17a18; age: 2)
  8   4           (object header: class)           0x0108d8e8
 12   4    byte[] FewHeightsComplexBlock.data      [11, 27, 43, 59, 75, 91, 107, 127, 11, 27, 43, 59, 75, 91, 107, 127, 11, 27, 43, 59, 75, 91, 107, 127, 11, 27, 43, 59, 75, 91, 107, 127, 11, 27, 43, 59, 75, 91, 107, 127, 11, 27, 43, 59, 75, 91, 107, 127, 11, 27, 43, 59, 75, 91, 107, 127, 11, 27, 43, 59, 75, 91, 107, 127]
 16   4   short[] FewHeightsComplexBlock.heights   [-4976, -4928, -4888, -4848, -4808, -4760, -4720, -4680]
 20   4           (object alignment gap)           
Instance size: 24 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

Размер самого класса больше ComplexBlock (16 против 24). На этом потеряли 697_152 байт. Была бы экономия 25 байт, но это даже не 32 минимальных ожидаемых.

Видим что количество byte[] массивов ([B в стате) увеличилось на те же 87_144 по количеству блоков нового типа, на них ушло дополнительно 6_971_520 байт по 80 на каждый, 64 - сам размер массива и 16 байт на обслуживание структуры. Т.е. тут дополнительная потеря вылезла в 16 байт. С ними получаем 41 байт экономии, которые хотелось бы получить.

Таким образом, накладных расходов набралось на 24 байта на блок, но даже так это экономия, идем дальше.

Получение высоты и nswe производится фактически как и для с ComplexBlock. А для высоты из массива байт из старших бит вытаскивается индекс, по индексу возвращается уже готовая высота.

Мало разных высот в ComplexBlock и общий nswe

По аналогии с BaseHeightOneNsweComplexBlock поищем в статистике, есть ли среди FewHeightsComplexBlock содержащие только один общий nswe на блок. Если бы не было более оптимальных BaseHeight блоков, то походит 1_082_789, но с их учетом отбирает на себя только 1_214. Очевидно, супер экономии не получить, но чисто для проформы глянем чисто из спортивного интереса.

Реализация в классе FewHeightsOneNsweComplexBlock, код типа - 8.

Здесь уже попробуем реализовать уплотнение данных в data блоке, которое не сделал в BaseHeightOneNsweComplexBlock. Т.к. у нас освободилось 4 бита nswe, которые можно так же отдать под индекс и тогда в одном байте массива data будет содержаться два индекса по 4 бита, и размер этого массива уменьшится вдвое с 64 до 32 байт. Сразу глянем ClassLayout:

ru.mosinnik.l2eve.geodriver.blocks.FewHeightsOneNsweComplexBlock object internals:
OFF  SZ      TYPE DESCRIPTION                             VALUE
  0   8           (object header: mark)                   0x000001efe8886801 (hash: 0xefe88868; age: 0)
  8   4           (object header: class)                  0x0108eeb8
 12   1      byte FewHeightsOneNsweComplexBlock.nswe      14
 13   3           (alignment/padding gap)                 
 16   4    byte[] FewHeightsOneNsweComplexBlock.data      [0, 0, 0, 0, 17, 17, 17, 17, 34, 34, 34, 34, 51, 51, 51, 51, 68, 68, 68, 68, 85, 85, 85, 85, 102, 102, 102, 102, 119, 119, 119, 119]
 20   4   short[] FewHeightsOneNsweComplexBlock.heights   [-3560, -3264, -2968, -2680, -2384, -2088, -1792, -1496]
Instance size: 24 bytes
Space losses: 3 bytes internal + 0 bytes external = 3 bytes total

Сам класс остался таким же по размеру, а связанный массив байт уменьшится на 32 байта, т.е. ожидаем 32х1214 = 38_848 байт экономии, смешно даже, но что имеем.

     COUNT       AVG       SUM   DESCRIPTION
   2691586       135 365399192   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
    712221       131  93405400   [S
    430841        24  10340184   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightComplexBlock
   1531897        24  36765528   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightOneNsweComplexBlock
    625077        16  10001232   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
     85930        24   2062320   ru.mosinnik.l2eve.geodriver.blocks.FewHeightsComplexBlock
      1214        24     29136   ru.mosinnik.l2eve.geodriver.blocks.FewHeightsOneNsweComplexBlock
      1498        16     23968   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    617883        16   9886128   ru.mosinnik.l2eve.geodriver.blocks.MultilayerBlock
     23821        24    571704   ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
   6722304           572010184   (total)

Считаем 572049032-572010184 = 38848, как и ожидалось без лишних потерь. Если вернемся и аналогично доработаем OneHeightComplexBlock, то это даст дополнительные 32х23821=762_272 байт экономии, возможно в будущем так и сделаю.

Сборка массива data и получение потом индексов теперь усложняется. Для четных номеров ячеек храним индекс в младших битах, для нечетных - в старших. Вооружаемся битовыми операторами, и в итоге код получения высоты выглядит так:

	int cellOffset = ((geoX & 0x07) << 3) + (geoY & 0x07);
	int heightIndex;
	if ((cellOffset & 0x01) == 0) {
		heightIndex = data[cellOffset / 2] & 0x0F;
	} else {
		heightIndex = (data[cellOffset / 2] >> 4) & 0x0F;
	}
	return heights[heightIndex];

Уже во время написания статьи увидел, что тут можно обойтись без if:

	int cellOffset = ((geoX & 0x07) << 3) + (geoY & 0x07);
	int heightIndex = (data[cellOffset >> 1] >> ((cellOffset & 0x01) << 2)) & 0x0F;
	return heights[heightIndex];

Уход от if дал 5% производительности:

// if-else
Benchmark                                                  (blockType)   Mode  Cnt     Score     Error  Units
GeoDriverBenchParams.getNextLowerZ  FEW_HEIGHTS_ONE_NSWE_COMPLEX_BLOCK  thrpt    5  9750,755 ± 210,820  ops/s

// bit ops
Benchmark                                                  (blockType)   Mode  Cnt      Score     Error  Units
GeoDriverBenchParams.getNextLowerZ  FEW_HEIGHTS_ONE_NSWE_COMPLEX_BLOCK  thrpt    5  10217,562 ± 508,475  ops/s

Промежуточный итог: больше с ComplexBlock ничего придумать не получилось, попытки менять приоритеты применения к какой-то экономии не привели, поэтому переходим к MultilayerBlock блокам.

MultilayerBlock без пропусков

В MultilayerBlock в первой и по факту единственной идеей для оптимизации памяти было выделение количества слоев в столбцах-ячейках для случаев, когда количество слоев в в каждом столбце одинаково, т.е. можно вынести в одно поле и сэкономить сразу 63 байт на блок. По статистике таких блоков 253_993, ожидаемая экономия 16_001_559 байт, 16Мб.

Реализация в NoHolesMultilayerBlock, код типа - 9.

Выносим количество слоев в свое поле, а исходный массив байт данных о слоях пересобираем сразу в short[]. Ожидая казусы с потерями из-за нового поля в классе смотрим ClassLayout:

ru.mosinnik.l2eve.geodriver.blocks.NoHolesMultilayerBlock object internals:
OFF  SZ      TYPE DESCRIPTION                          VALUE
  0   8           (object header: mark)                0x000002fd756d0811 (hash: 0xfd756d08; age: 2)
  8   4           (object header: class)               0x0108e2a0
 12   1      byte NoHolesMultilayerBlock.layersCount   2
 13   3           (alignment/padding gap)              
 16   4   short[] NoHolesMultilayerBlock.data          [-9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057, -9969, -31057]
 20   4           (object alignment gap)               
Instance size: 24 bytes
Space losses: 3 bytes internal + 4 bytes external = 7 bytes total

24 байта, против 16 для просто MultilayerBlock, 8 байт потери из-за нового поля и цена поля 8 а не 1 байт, т.е. экономия не 63, а 56 байт - 56х253993=14_223_608.

Смотрим результат:

     COUNT       AVG       SUM   DESCRIPTION
   2437593       111 271821128   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
    966214       176 170727912   [S
    430841        24  10340184   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightComplexBlock
   1531897        24  36765528   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightOneNsweComplexBlock
    625077        16  10001232   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
     85930        24   2062320   ru.mosinnik.l2eve.geodriver.blocks.FewHeightsComplexBlock
      1214        24     29136   ru.mosinnik.l2eve.geodriver.blocks.FewHeightsOneNsweComplexBlock
      1498        16     23968   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    363890        16   5822240   ru.mosinnik.l2eve.geodriver.blocks.MultilayerBlock
    253993        24   6095832   ru.mosinnik.l2eve.geodriver.blocks.NoHolesMultilayerBlock
     23821        24    571704   ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
   6722304           557786576   (total)

572010184-557786576=14_223_608, 14Мб (2,5% от предыдущего).

Получение высоты и nswe теперь значительно упростилось по сравнению с исходным MultilayerBlock, т.к. мы знаем, что каждый столбец занимает N записей в массиве, и можно легко найти позицию начала столбц

Погоняем бенчмарки:

Benchmark                                             (blockType)   Mode  Cnt     Score     Error  Units
GeoDriverBenchParams.getNextLowerZ_old  NO_HOLES_MULTILAYER_BLOCK  thrpt    5  1152,441 ± 123,538  ops/s
GeoDriverBenchParams.getNextLowerZ      NO_HOLES_MULTILAYER_BLOCK  thrpt    5  4825,315 ± 212,839  ops/s

Почти пятикратный рост производительности, очень существенно. Главный профит связан с тем, что теперь нет необходимости пробегаться по массиву данных и искать в нем место, где начинается нужный нам столбец.

Индексированный MultilayerBlock

Как и писал ранее, идей по оптимизации памяти для MultilayerBlock больше не появилось, потому что специфика работы алгоритмов поиска ближайшего/ниже/вышележащих относительно искомой точки в пространстве накладывает больший ограничения. Однако прирост скорости в NoHolesMultilayerBlock дал понять, что избавление от постоянного пробега по массиву данных дает хороший буст, надо эту практику применить и для остальных MultilayerBlock.

Реализация в MultilayerIndexedBlock, код типа - 9.

Реализуем индексирование для позиций начала столбцов в исходном массиве байт. Мы знаем, что в MultilayerBlock всегда 64 столбца, максимальный размер данных блока в моей геодате примерно 3кб, т.е. нам достаточно 12 бит (3к < 2^12), а значит, будем использовать массив short[] для хранения индексов. Пробегаемся по данным, собираем индексы, сохраняем в массив и вуаля:

Benchmark                                            (blockType)   Mode  Cnt     Score    Error  Units
GeoDriverBenchParams.getNextLowerZ_old  INDEXED_MULTILAYER_BLOCK  thrpt    5  1019,331 ± 23,953  ops/s
GeoDriverBenchParams.getNextLowerZ      INDEXED_MULTILAYER_BLOCK  thrpt    5  2789,704 ± 68,163  ops/s

В 2.7 раза быстрее, но какой ценой:

     COUNT       AVG       SUM   DESCRIPTION
   2437593       111 271821128   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
   1330104       167 223128072   [S
    430841        24  10340184   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightComplexBlock
   1531897        24  36765528   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightOneNsweComplexBlock
    625077        16  10001232   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
     85930        24   2062320   ru.mosinnik.l2eve.geodriver.blocks.FewHeightsComplexBlock
      1214        24     29136   ru.mosinnik.l2eve.geodriver.blocks.FewHeightsOneNsweComplexBlock
      1498        16     23968   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    363890        24   8733360   ru.mosinnik.l2eve.geodriver.blocks.IndexedMultilayerBlock
    253993        24   6095832   ru.mosinnik.l2eve.geodriver.blocks.NoHolesMultilayerBlock
     23821        24    571704   ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
   7086194           613097856   (total)

Памяти теперь выделяется больше на 55_311_280 байт, 55Мб (почти 10% к предыдущему), откатило все сэкономленное от NoHolesMultilayerBlock в трехкратном размере. Производительность нравится, но к ней вернемся позже.

Получение высоты и nswe по сути аналогично NoHolesMultilayerBlock, только начало данных столбца берется из массива по номеру столбца, а не вычисляется.

Индексированный MultilayerBlock до 32 слоев

Какое-то время MultilayerIndexedBlock был финальной версией, и уже велась работа над GeoDriverBytes и перестройкой работы под единый массив данных - это будет описано далее. Но чтобы не разрывать повествование про оптимизации самих блоков, опишу здесь.

Очень заметная разница в производительности между NoHolesMultilayerBlock и IndexedMultilayerBlock не давала покоя. Сбор jfr профилей при выполнении jmh тестов подсветил вполне очевидное - заметное время уходило на обращения к массивами данных на вычитку порций данных:

в NoHolesMultilayerBlock - у нас по факту одно чтение из поля и дальше N чтений данных слоев в столбце
в IndexedMultilayerBlock - тут чтение индекса из массива, по индексу чтение номера слоев и дальше N парных чтений по байту и из этой пары уже восстанавливаются данные слоя Получается в Indexed в два раза больше чтений и это неплохо сходится с соотношением скорости работы реализаций.

Осталось придумать как избавиться от дополнительных чтений. Заметка раз - надо избавиться от парного чтения байт на одинарное чтение сразу short. Заметка два - нужно откуда-то эффективно получать количество слоев для столбцов.

Первое будет очевидно выполнимо, если избавиться от номеров слоев в массиве байт данных блока, тогда там останутся только данные слоев, и их можно упаковать в массив short[], а в индексах будет храниться позиция внутри такого массива.

Для второго оценим сколько вообще у нас бывает слоев в столбцах в MultilayerBlock, считаем статистику - максимально 21 слой для моей геодаты, влезает в 32 (2^5), т.е. достаточно 5 бит информации.

Если получится в 11 бит упаковывать индексы в массиве данных слоев, то там же можно будет в 5 старших бит уложить количество слоев, а младшие 11 будут самим индексом. По статистике максимальный размер данных блока 3Кб, делим по два байта (размер short) - ~1500 записей в массиве слоев, т.е. максимальный индекс укладывается с запасом в 2048 (2^11), для которых надо 11 бит, которые у нас как раз и остались. Такой подход называется tagged pointer.

Реализация в Indexed32MultilayerBlock, код типа - 11.

Из общего объема блоков отбираются подходящие под условие, чтобы в нем было максимум до 32 слоев, хоть под это требование подпадают абсолютно все MultilayerBlock из моей геодаты, оставляем фильтрацию для фолбэка. В конструкторе обсчитываем пришедший исходный массив байт, вытаскивая номера слоев из общего потока и пересобирая данные слоев в свои массивы. Массив индексов собираем по описанный выше логике:

	index[i] = (short) ((nLayers << 11) | ((layersCountBefore) & 0x07FF));
	layersCountBefore += nLayers;
	
	// обратно вытаскиваем
	int startOffset = cellDataOffset & 0x01FF;
	int nLayers = (cellDataOffset >> 11) & 0x01F;

Т.к. повытаскивали из data количества слоев, 64 байта, то можно будет даже рассчитывать на экономию по памяти 64х363_890=23_288_960 байт, 23Мб.

Раз уж залезли в пересборку массива данных, то сделаем еще одну вещь - проверим отсортированы ли данные слоев в столбце по высоте? Статистика хоть и показывает, что да все отсортировано по убыванию, но надо убедиться. А убедиться надо, чтобы поупрощать алгоритмы поиска высот, сделав их мало того, что более читабельными и логичными, так еще теперь можно добавить ранние выходs из циклов и обработку спец кейсов для поиска ближайшего слоя, когда их только один или два.

Замеряем:

Benchmark                                           (blockType)   Mode  Cnt     Score    Error  Units
GeoDriverBenchParams.getNextLowerZ  INDEXED_32_MULTILAYER_BLOCK  thrpt    5  3697,672 ± 74,411  ops/s

К 5к не близко, но стало производительнее (не будем унывать, при переходе на GeoDriverBytes разница еще сократится).

А что же с памятью:

     COUNT       AVG       SUM   DESCRIPTION
   2073703        79 165857392   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
   1693994       180 305802848   [S
    430841        24  10340184   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightComplexBlock
   1531897        24  36765528   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightOneNsweComplexBlock
    625077        16  10001232   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
     85930        24   2062320   ru.mosinnik.l2eve.geodriver.blocks.FewHeightsComplexBlock
      1214        24     29136   ru.mosinnik.l2eve.geodriver.blocks.FewHeightsOneNsweComplexBlock
      1498        16     23968   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    363890        24   8733360   ru.mosinnik.l2eve.geodriver.blocks.Indexed32MultilayerBlock
    253993        24   6095832   ru.mosinnik.l2eve.geodriver.blocks.NoHolesMultilayerBlock
     23821        24    571704   ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
   7086194           589808896   (total)

Отыгрываем назад все ожидаемые 23Мб (3.8% от предыдущего) и хотя бы немного компенсируем потерю от добавленных индексов.

Промежуточный итог: теперь со всеми оптимизациями блоков закончено, а у нас стало 589Мб, а если выключить индексированные мультиблоки - 557Мб. Кажется что это предел и можно отыграть лишь какие-то крохи, упомянутые выше, но цель хотя бы 512Мб. Думаем дальше.

GeoDriverBytes

Посмотрим внимательно на последний вывод:

     COUNT       AVG       SUM   DESCRIPTION
   2073703        79 165857392   [B
       166    262160  43518560   [Lru.mosinnik.l2eve.geodriver.abstraction.IBlock;
         1      4112      4112   [Lru.mosinnik.l2eve.geodriver.abstraction.IRegion;
   1693994       180 305802848   [S
    430841        24  10340184   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightComplexBlock
   1531897        24  36765528   ru.mosinnik.l2eve.geodriver.blocks.BaseHeightOneNsweComplexBlock
    625077        16  10001232   ru.mosinnik.l2eve.geodriver.blocks.ComplexBlock
     85930        24   2062320   ru.mosinnik.l2eve.geodriver.blocks.FewHeightsComplexBlock
      1214        24     29136   ru.mosinnik.l2eve.geodriver.blocks.FewHeightsOneNsweComplexBlock
      1498        16     23968   ru.mosinnik.l2eve.geodriver.blocks.FlatBlock
    363890        24   8733360   ru.mosinnik.l2eve.geodriver.blocks.Indexed32MultilayerBlock
    253993        24   6095832   ru.mosinnik.l2eve.geodriver.blocks.NoHolesMultilayerBlock
     23821        24    571704   ru.mosinnik.l2eve.geodriver.blocks.OneHeightComplexBlock
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoDriver
         1        16        16   ru.mosinnik.l2eve.geodriver.regions.NullRegion
       166        16      2656   ru.mosinnik.l2eve.geodriver.regions.Region
   7086194           589808896   (total)

Вспоминаем, что пару раз мы обжигались на том, что не учитывали разрастание класса из-за выравнивания (alignment), что на обслуживание массива нужны еще служебные структуры и они тоже жрут память. Глянем еще, что у нас есть аж 43Мб в массивах IBlock, хотя там хранятся только ссылки на сами объекты блоков, в которых уже хранятся какие-то данные. Выглядит как большое поле для оптимизации. Сразу оговорюсь, целей разбираться с FFM как замену Unsafe пока нет, а будем использовать более простые вещи.

Итак идея думаю понятна: надо избавиться от абстракций в виде классов и самому менеджерить доступы к полям и массивами с данными, которые были внутри блоков. Звучит страшно конечно, предстоит много работы.

Структуры

Первое, что делаем - это создаем новый класс драйвера GeoDriverBytes, он теперь будет хранить все данные блоков в большом ByteBuffer data (далее буфер) и несколько вспомогательных массивов:

разреженный массив интов regionFirstBlockIndexes - в нем хранится смещение (или позиция) внутри буфера) на начало данных соответствующего региона, фактически он нам будет заменять получение объекта региона. Размер его фиксирован 32х32, но заполнен согласно сетке регионов по номерам. Пустые регионы заполняются -1 для понимания, что данных для такого региона нет.
байтовый массив blockTypes - в нем хранятся типы блока, те самые, что указывал ранее в реализациях блоков, по факту заменяют определение класса, чтобы вызвать нужную реализацию метода
массив интов blockDataOffsets - в нем хранятся смещения в буфере на начало данных каждого блока, блоков 11.5кк и размер массива аналогичный.

Заполнение

Задача двухэтапная - сначала надо подсчитать размеры для будущих структур, потом уже заполнить.

Для начала создадим в пакедже bytes для каждого класса блоков их дублеров с суффиксом *Bytes, где будем реализовывать специфическую для блоков логику.

Для подсчета объемов создается статический метод calcBytesCount, который по переданному блоку считает необходимый размер, чтобы все уместилось.
Например для ComplexBlockBytes возврат константы, т.к. размер всегда известен:

    public static final int SIZE = 2 * IBlock.BLOCK_CELLS;

    public static int calcBytesCount(ComplexBlock block) {
        return SIZE;
    }

А для заполнения необходимо было бы для каждого либо написать реализацию преобразования из формата .l2j либо же просто логику дампа содержимого блока в буфер. Выбран второй вариант: реализуем статический метод appendBytes, который принимает блок, соответствующего типа, и записывает его в переданный буфер.

Например для NoHolesMultilayerBlock создается NoHolesMultilayerBlockBytes с методом:

    public static void appendBytes(NoHolesMultilayerBlock block, ByteBuffer data) {
        data.put(block.getLayersCount());
        for (short datum : block.getData()) {
            data.putShort(datum);
        }
    }

Далее уже без особой магии читаем итеративно регионы, разбираем на блоки, для всех считаем объемы для буфера и массивов. Потом вторым проходом заполняем конвертированными значениями сам буфер, сохраняя постепенно оффсеты и типы в дополнительных массивах.

Сразу же для FlatBlock сделаем оптимизацию: в блоке у нас только одна высота, помещающаяся в short, она так же поместится и в int в массиве blockDataOffsets, поэтому вместо оффсета сразу сохраним высоту. Это позволит нам сэкономить немного места и избежать дополнительного чтения.

Подготовка к выборке

Поиск высоты и nswe по переданным координатам по сути аналогично работе обычного драйвера, но вместо работы с объектами регионов и блоков теперь для всего используются смещения и вызов логики по типу:

Определяем регион для этой координаты - смещение начала данных для региона (regionFirstBlockIndex) из regionFirstBlockIndexes.
Определяем блок для этой координаты - это смещение начала данных блока (blockIndexInRegion) относительно начала данных региона (regionFirstBlockIndex). Считается из координат тривиальной формулой.

Определяем тип блока и смещение начала данных блока:

byte blockType = blockTypes[regionFirstBlockIndex + blockIndexInRegion];
int blockDataOffset = blockDataOffsets[regionFirstBlockIndex + blockIndexInRegion];

Теперь у нас есть все, что требуется для работы:

тип блока для выбора логики - в больших некрасивых switch-ах в зависимости от типа вызывается соответствующий статический метод
начало данных блока в общем буфере

Выборка

Для каждого метода (checkNearestNSWE/getNearestZ/getNextLowerZ/getNextHigherZ) в *Bytes классах реализуются аналоги, но которые используют не локальные данные объектов, а чтение из общего буфера. Для этого помимо обычных параметров передаем подготовленный ранее blockDataOffset и сам буфер data. Внутри методов меняется по сути только чтение из внутренних data массивов на чтение из буфера с добавленным смещением.

Например для ComplexBlock:

// было:
private final short[] data;

private int getCellNSWE(int geoX, int geoY) {
	int cellOffset = ((geoX & 0x07) << 3) + (geoY & 0x07);
	short datum = data[cellOffset];
	return datum & 0x0F;
}


// стало:
private static int getCellNSWE(int geoX, int geoY, int blockDataOffset, ByteBuffer data) {
	int cellOffset = ((geoX & 0x07) << 3) + (geoY & 0x07);
	return data.getShort(blockDataOffset + 2 * cellOffset) & 0x0F;
}

В целом просто механическая работа по переносу логики, но были особенности.

Во-первых, особенность работы с short - ранее они как правило были в массивах short[] и итерирование было с инкрементом на единицу, а теперь смещения у нас в байтах и надо не забывать инкрементировать на два.

Во-вторых, дополнительную боль создают блоки, у которых были другие поля помимо массива data - в таких случаях необходимо высчитывать и сохранять внутренние смещения и например для FewHeightsOneNsweComplexBlockBytes получается нечто монструозное сложночитаемое:

public static final int INNER_DATA_SIZE = IBlock.BLOCK_CELLS / 2;

private static final int NSWE_OFFSET = 0;
private static final int INNER_DATA_OFFSET = 1;
private static final int HEIGHTS_OFFSET = INNER_DATA_OFFSET + INNER_DATA_SIZE;


private static int getCellHeight(int geoX, int geoY, int blockDataOffset, ByteBuffer data) {
	int cellOffset = ((geoX & 0x07) << 3) + (geoY & 0x07);
	int heightIndex;
	if ((cellOffset & 0x01) == 0) {
		heightIndex = data.get(blockDataOffset + INNER_DATA_OFFSET + cellOffset / 2) & 0x0F;
	} else {
		heightIndex = (data.get(blockDataOffset + INNER_DATA_OFFSET + cellOffset / 2) >> 4) & 0x0F;
	}
	return data.getShort(blockDataOffset + HEIGHTS_OFFSET + 2 * heightIndex);
}

if-else boilerplate

Во всех методах GeoDriverBytes есть либо большой switch либо if-else цепочки, казалось бы в java 25 уже давно есть pattern matching, и можно хотя бы код в том же getType сделать с его помощью. Сделал, а для уверенности погонял бенчи для сравнения подходов и выяснил, что в моем случае pattern matching на 7% медленнее, чем просто цепочка if-else. Скорее всего дело в специфике моих данных и распределении, что порядка 70% попадают в первые две ветки if-else, и это оказывается заметно дешевле typeSwitch. Но благодаря подкинутой мысли из тгшного jvm.pro чата написал о проблеме на JDK майлинг листы и вот https://bugs.openjdk.org/browse/JDK-8378724. Буду наблюдать за решением, а пока остается некрасивый if-else. К тому же зная распределение типов блоков в нем можно будет управлять, приоритетом проверки, для более раннего срабатывания самого частовстречаемого типа блока. (Кстати, поделал такие опыты и да это дает результат, самый лучший - на комбинации три ифа, покрывающие 80% блоков, а остальные на switch. Но надо бы собрать частоты не по наличию блоков, а по попаданиям в реальной работе, поэтому пока оставил как есть и позже вернусь.)

Результаты

С включенными всеми типами блоков:

     COUNT       AVG       SUM   DESCRIPTION
         2 213376540 426753080   [B
         2  21760016  43520032   [I
         1        56        56   java.nio.HeapByteBuffer
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        32        32   ru.mosinnik.l2eve.geodriver.driver.GeoDriverBytes
         7           470273224   (total)

Без индексированных мультиблоков:

     COUNT       AVG       SUM   DESCRIPTION
         2 201732060 403464120   [B
         2  21760016  43520032   [I
         1        56        56   java.nio.HeapByteBuffer
         1        24        24   ru.mosinnik.l2eve.geodriver.driver.GeoConfig
         1        32        32   ru.mosinnik.l2eve.geodriver.driver.GeoDriverBytes
         7           446984264   (total)

Было 589Мб и 557Мб, стало 470Мб (минус 119Мб, 20%) и 446Мб (минус 111Мб, 20%) - отличный результат, уже укладываемся в 512Мб самой геодатой.

Пробуем запуститься и, чтобы было интереснее, сразу с -Xmx500m. Результат к сожалению ожидаемый:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Ставим лимит в 3Гб:

Gameserver have started, used memory: 723 / 3000 Mb.

Из 723Мб хипа 446Мб тратится на геодату, оставшиеся 277Мб - это необходимые для работы сервера данные (например скилы, предметы, мобы и т.д., что требует постоянного нахождения в памяти).

Работа проделана большая, дальше мысли только о mmap.

GeoDriverBytesMmap

Итак в буфере 392Мб, остальное в доп структуры. Доп структуры нужны всегда, а вот буфер можно подгрузить частично - игроков планируется штучное, а то и вообще в одиночку побегать, считай один регион и тот не полностью нужен будет.

Для mmap нужны файлы, сделаем сохранение буфера и структур внутри GeoDriverBytes.writeToFiles и сразу обратный к нему readFromFiles, чтобы загружать уже подготовленное без анализа и пересборки .l2j.

total 427M
-rw-r--r-- 1 user 333  42M Feb 25 01:29 blockDataOffsets.bin
-rw-r--r-- 1 user 333  11M Feb 25 01:29 blockTypes.bin
-rw-r--r-- 1 user 333 375M Feb 25 01:29 data.bin
-rw-r--r-- 1 user 333 4.0K Feb 25 01:29 regionFirstBlockIndexes.bin

Итого:

// новые бинари
$ du -sh bin_geo_data
427M    bin_geo_data

// старые.l2j
$ du -sh geodata
535M    geodata

Тестанем время загрузки: на .l2j время 7.5 секунд, из бинарных файлов - 350 мс. Оба время после пары-тройки загрузок с NVMe на прогретых ФС кэшах.

Приступим к GeoDriverBytesMmap. Структуры те же, логика работы с данными та же, отличие от GeoDriverBytes только в том, что файл данных не вычитывается в память, а мапится:

// было
data = ByteBuffer.wrap(Files.readAllBytes(dataDir.resolve(DATA_FILE_NAME)));

// стало
RandomAccessFile file = new RandomAccessFile(dataDir.resolve(DATA_FILE_NAME).toFile(), "r");
FileChannel channel = file.getChannel();
data = channel.map(FileChannel.MapMode.READ_ONLY, 0, channel.size());

Запускаем с -Xmx500m

Gameserver have started, used memory: 343 / 500 Mb.

Ну и напоследок сводная таблица действий и какой выхлоп давало (GeoDriverBytesMmap пропущен, т.к. сложно посчитать):

Что сделано	Всего памяти (Мб)	Дельта (Мб)	Дельта (%)
стартовое	805,76
переиспользование FlatBlock	684,78	120,97	15,01
OneHeightComplexBlock	683,45	1,33	0,19
BaseHeightComplexBlock	598,27	85,17	12,46
BaseHeightOneNsweComplexBlock	573,53	24,74	4,14
FewHeightsComplexBlock	572,05	1,49	0,26
FewHeightsOneNsweComplexBlock	572,01	0,0388	0,0068
NoHolesMultilayerBlock	557,79	14,22	2,49
IndexedMultilayerBlock	613,10	-55,31	-9,92
Indexed32MultilayerBlock	589,81	23,29	3,80
GeoDriverBytes с индексированными	470,27	119,54	20,27
GeoDriverBytes без индексированных	446,98	23,29	4,95

Итого		358,77	44,53

Красота. Цель достигнута...

Заключение

Но как бы не так, это лишь размер хипа, но есть еще сама JVM с либами, JIT, GC, стеки потоков и т.д. (можно почитать например https://habr.com/ru/companies/otus/articles/445312/ и для погружения уже в доклад Паньгина https://www.youtube.com/watch?v=kKigibHrV5I).

Глянем что у нас по покажет NativeMemoryTracking - набегает до 718Мб (смотреть Total comitted)

Вывод VM.native_memory summary

C:\Program Files\Java\jdk-21\bin>jcmd 11388 VM.native_memory summary
11388:
Native Memory Tracking:
(Omitting categories weighting less than 1KB)
Total: reserved=2100916KB, committed=718036KB       malloc: 72360KB #226808, peak=139055KB #197205       mmap:   reserved=2028556KB, committed=645676KB
-                 Java Heap (reserved=512000KB, committed=512000KB)                            (mmap: reserved=512000KB, committed=512000KB, at peak)
-                     Class (reserved=1049415KB, committed=10887KB)                            (classes #10353)                            (  instance classes #9636, array classes #717)                            (malloc=839KB tag=Class #19823) (peak=844KB #19842)                            (mmap: reserved=1048576KB, committed=10048KB, at peak)                            (  Metadata:   )                            (    reserved=65536KB, committed=41344KB)                            (    used=41063KB)                            (    waste=281KB =0.68%)                            (  Class space:)                            (    reserved=1048576KB, committed=10048KB)                            (    used=9784KB)                            (    waste=264KB =2.63%)
-                    Thread (reserved=95534KB, committed=6382KB)                            (threads #93)                            (stack: reserved=95232KB, committed=6080KB, peak=6080KB)                            (malloc=194KB tag=Thread #583) (peak=222KB #640)                            (arena=108KB #183) (peak=1019KB #157)
-                      Code (reserved=255711KB, committed=26287KB)                            (malloc=7967KB tag=Code #35281) (at peak)                            (mmap: reserved=247744KB, committed=18320KB, at peak)                            (arena=1KB #1) (peak=34KB #2)
-                        GC (reserved=56723KB, committed=56675KB)                            (malloc=13715KB tag=GC #9938) (peak=32281KB #8261)                            (mmap: reserved=43008KB, committed=42960KB, at peak)                            (arena=0KB #0) (peak=38KB #6)
-                 GCCardSet (reserved=30KB, committed=30KB)                            (malloc=30KB tag=GCCardSet #54) (peak=131KB #319)
-                  Compiler (reserved=698KB, committed=698KB)                            (malloc=502KB tag=Compiler #279) (peak=533KB #289)                            (arena=196KB #6) (peak=48245KB #23)
-                  Internal (reserved=1660KB, committed=1660KB)                            (malloc=1592KB tag=Internal #11653) (peak=2496KB #19068)                            (mmap: reserved=68KB, committed=68KB, at peak)
-                     Other (reserved=10347KB, committed=10347KB)                            (malloc=10347KB tag=Other #39) (peak=46755KB #45)
-                    Symbol (reserved=9408KB, committed=9408KB)                            (malloc=7226KB tag=Symbol #133605) (at peak)                            (arena=2182KB #1) (at peak)
-    Native Memory Tracking (reserved=4094KB, committed=4094KB)                            (malloc=107KB tag=Native Memory Tracking #1890) (peak=107KB #1900)                            (tracking overhead=3987KB)
-        Shared class space (reserved=16384KB, committed=14848KB, readonly=0KB)                            (mmap: reserved=16384KB, committed=14848KB, peak=15104KB)
-               Arena Chunk (reserved=6643KB, committed=6643KB)                            (malloc=6643KB tag=Arena Chunk #469) (peak=59552KB #1268)
-                   Tracing (reserved=15629KB, committed=15629KB)                            (malloc=15565KB tag=Tracing #446) (peak=15581KB #486)                            (arena=64KB #2) (at peak)
-                   Logging (reserved=0KB, committed=0KB)                            (malloc=0KB tag=Logging #1) (peak=1KB #1)
-                    Module (reserved=207KB, committed=207KB)                            (malloc=207KB tag=Module #2859) (at peak)
-                 Safepoint (reserved=8KB, committed=8KB)                            (mmap: reserved=8KB, committed=8KB, at peak)
-           Synchronization (reserved=606KB, committed=606KB)                            (malloc=606KB tag=Synchronization #9639) (at peak)
-            Serviceability (reserved=33KB, committed=33KB)                            (malloc=33KB tag=Serviceability #41) (peak=129KB #43)
-                 Metaspace (reserved=65749KB, committed=41557KB)                            (malloc=213KB tag=Metaspace #161) (at peak)                            (mmap: reserved=65536KB, committed=41344KB, at peak)
-      String Deduplication (reserved=1KB, committed=1KB)                            (malloc=1KB tag=String Deduplication #8) (at peak)
-           Object Monitors (reserved=35KB, committed=35KB)                            (malloc=35KB tag=Object Monitors #31) (peak=61KB #277)

Дальше из спортивного интереса позажимал объемы метаспейса, кэша, включил другой ГЦ и т.д., ну можно считать влез, Total 515404KB (503Мб):

Вывод VM.native_memory summary

Native Memory Tracking:
(Omitting categories weighting less than 1KB)
Total: reserved=624516KB, committed=515404KB       malloc: 43384KB #192016, peak=110791KB #138199       mmap:   reserved=581132KB, committed=472020KB
-                 Java Heap (reserved=389120KB, committed=389120KB)                            (mmap: reserved=389120KB, committed=389120KB, at peak)
-                     Class (reserved=66279KB, committed=10727KB)                            (classes #10281)                            (  instance classes #9564, array classes #717)                            (malloc=743KB tag=Class #16877) (peak=749KB #16913)                            (mmap: reserved=65536KB, committed=9984KB, at peak)                            (  Metadata:   )                            (    reserved=65536KB, committed=40960KB)                            (    used=40745KB)                            (    waste=215KB =0.53%)                            (  Class space:)                            (    reserved=65536KB, committed=9984KB)                            (    used=9730KB)                            (    waste=254KB =2.54%)
-                    Thread (reserved=18632KB, committed=4476KB)                            (threads #60)                            (stack: reserved=18432KB, committed=4276KB, peak=4276KB)                            (malloc=131KB tag=Thread #385) (peak=208KB #577)                            (arena=69KB #117) (peak=984KB #97)
-                      Code (reserved=28377KB, committed=15093KB)                            (malloc=3608KB tag=Code #18215) (peak=5386KB #22209)                            (mmap: reserved=24768KB, committed=11484KB, at peak)                            (arena=1KB #1) (peak=35KB #3)
-                        GC (reserved=1302KB, committed=1294KB)                            (malloc=22KB tag=GC #58) (peak=3291KB #879)                            (mmap: reserved=1280KB, committed=1272KB, at peak)
-                  Compiler (reserved=562KB, committed=562KB)                            (malloc=366KB tag=Compiler #282) (peak=484KB #322)                            (arena=196KB #6) (peak=41591KB #23)
-                  Internal (reserved=1574KB, committed=1574KB)                            (malloc=1506KB tag=Internal #9993) (at peak)                            (mmap: reserved=68KB, committed=68KB, at peak)
-                     Other (reserved=4204KB, committed=4204KB)                            (malloc=4204KB tag=Other #36) (peak=46755KB #44)
-                    Symbol (reserved=9368KB, committed=9368KB)                            (malloc=7186KB tag=Symbol #132710) (peak=7188KB #132734)                            (arena=2182KB #1) (at peak)
-    Native Memory Tracking (reserved=3434KB, committed=3434KB)                            (malloc=59KB tag=Native Memory Tracking #1039) (peak=60KB #1051)                            (tracking overhead=3375KB)
-        Shared class space (reserved=16384KB, committed=14848KB, readonly=0KB)                            (mmap: reserved=16384KB, committed=14848KB, peak=15104KB)
-               Arena Chunk (reserved=3092KB, committed=3092KB)                            (malloc=3092KB tag=Arena Chunk #293) (peak=45786KB #1175)
-                   Tracing (reserved=15630KB, committed=15630KB)                            (malloc=15567KB tag=Tracing #481) (peak=15578KB #464)                            (arena=64KB #2) (at peak)
-                   Logging (reserved=0KB, committed=0KB)                            (malloc=0KB tag=Logging #1) (peak=1KB #1)
-                    Module (reserved=206KB, committed=206KB)                            (malloc=206KB tag=Module #2857) (at peak)
-                 Safepoint (reserved=8KB, committed=8KB)                            (mmap: reserved=8KB, committed=8KB, at peak)
-           Synchronization (reserved=540KB, committed=540KB)                            (malloc=540KB tag=Synchronization #8582) (at peak)
-            Serviceability (reserved=32KB, committed=32KB)                            (malloc=32KB tag=Serviceability #39) (peak=38KB #152)
-                 Metaspace (reserved=65735KB, committed=41159KB)                            (malloc=199KB tag=Metaspace #119) (at peak)                            (mmap: reserved=65536KB, committed=40960KB, at peak)
-      String Deduplication (reserved=1KB, committed=1KB)                            (malloc=1KB tag=String Deduplication #8) (at peak)
-           Object Monitors (reserved=35KB, committed=35KB)                            (malloc=35KB tag=Object Monitors #33) (peak=65KB #317)

Понятно, что там еще для ОС надо чего-то оставить и тут уже только надеяться, что все лишнее улетит в swap.

Пока все это пилилось, ситуация поменялась - у моего хостера F поменялись тарифы и старая моя впска добровольно-принудительно была заменена, и у новой стало 1Гб памяти. И как вы думаю понимаете, в нее уже влезаем спокойно и челендж фактически отменился.

Но усилия не пропали даром, на впске подняты были еще база, auth сервер, агент portainer-а и еще по мелочи всякого, и все разместилось достаточно свободно в докерах. Да и оптимизация памятью геодаты не ограничилась, погонял бенчи и ускорение до 5 раз на получении высот и nswe. По ходу дела еще пару мест повсплывало и было улучшено или помечено тудушками для будущих улучшений.

Предвижу вопросы про GraalVM, с увеличение лимита до 1Гб практической потребности уже не было, а никаких мыслительных действий для этого особо не требуется и уже не интересно. Да и ранее уже имел дело с граалем, и в целом он на дистанции медленнее работает из-за отсутствия JIT оптимизаций в рантайме, что на 1 ядре впски не особо надо, а время старта меня тут вполне устраивает.

Весь код нового геодрайвера в репе https://github.com/mosinnik/l2-geo. Можно использовать, комментировать, предлагать что еще попробовать. А и да, если у кого будут вопросы или кто захочет себе внедрить на работающем проекте, то прошу дать знать по координатам в профиле, хочется узнать какой реальный профит может оказаться.

Получилась занятная головоломка, которая на работе сейчас редко встречается, и это был саймый кайф в данном процессе, что для меня самое главное и ради чего по факту все это было сделано.

Оптимизация Lineage 2 GeoData драйвера