Я очень люблю язык программирования D и все его прикольные фичи. А ещё я люблю читать про прикольные фишки в программировании и разные челленжи. Когда я в первый раз услышал про "1brc", было уже несколько поздно в нём поучаствовать, да и узнал я о нём не в контексте оригинальной Java версии, а из поста про реализацию на Rust.
Этот пост подогрел во мне интерес попробовать себя в чём-то подобном, и так уж вышло, что никто ещё не написал реализацию на D (по крайней мере я не нашёл).
К сожалению, время найти на это у меня вышло только года полтора спустя (и спустя два года с начала оригинального челленжа).
Что за челленж
Идея проста: генерируется файл на один миллиард строк с данными по температуре в разных городах, нужно обработать эти данные и вывести объект с названиями городов, средней, минимальной и максимальной температурами в каждом.
Звучит вроде бы просто, но разница между 1 миллионом и 1 миллиардом строк ощутимая, особенно когда речь заходит за размер файла и как много времени нужно на его обработку. Наивной реализации нужно где-то 1.4сек на обработку миллиона строк, но на миллиард нужно уже 12 минут (!).
Проблемы
Четыре основных проблемы, которые приходят на ум и решение которых позволит выжать немного производительности, такие:
- Чтение файла с диска занимает ощутимо времени. Загрузить весь файл в память тоже такое себе решение, но наверняка должен быть подход к проблеме получше.
- Конвертирование десятичных дробей в числа с плавающей точкой – тоже не самая быстрая операция. Как и большое количество операций с числами с плавающей точкой.
- Многопоточность. В D очень приятные в использовании инструменты для параллелизма в коде, за счёт этого можно получить дешёвое ускорение задёшево.
- Хранение данных. Самым простым способом было бы хранение данных в ассоциативном массиве со строковыми ключами. Более эффективным способом хранения была бы хешмапа.
Можно ещё выжать немного производительности за счёт флагов компилятора.
Помимо этого я (бесстыже) подсмотрел в пару интересных блог постов про реализации на C и Go, что дало немного вдохновения, а заодно дало точку сравнения своих результатов с референсными. Моим главным ориентиром, впрочем, была реализация 1brc от Дэнни ван Кутена на C (или Данни? как правильно-то вообще): она отрабатывала за 1.6сек, и это был тот результат, к которому мне хотелось приблизиться настолько близко, насколько возможно, не выходя из реалий D.
Реализация
Все свои попытки я залогал в этом git репозитории, так что можно полистать коммиты и посмотреть изменения. Основной идей было постепенное "обновление" с зафиксированной историей и результатами в README.
Время выполнения было получено замерами запусков time, обычно среднее за 3-5 прогонов.
Все тестовые прогоны были запущены на моём личном ноутбуке, Asus Rog Strix Scar 15 ~2022 года с Intel Core i9-12900H, под Arch Linux.
Ставим ориентир: наивная реализация
Это был базовый подход, с которым бы сравнивались улучшенные версии. Используя ассоциативный массив, перенаправление stdin через unix-пайп и double для показателей.
Реализация действительно простая и понятная, действительно наивная, и выполняется она за 12м20с.
Кастомный парсер строк и рассчёты в int
Формат данных обычно имеет одну и ту же структуру: Город;17.2. Это значит, что для такого формата можно достаточно просто сделать свой парсер строк и выиграть за счёт этого за дёшево немного скорости. Также можно парсить показатели температуры в int, игнорируя точку, что позволит делать все рассчёты также с целыми числами и добавлять точку только при конечном выводе.
value = 0;
bool negative = false;
for (int i = endSt+1; i < buf.length; i++) {
if (buf[i] == '\n') {
endVal = i + 1;
start = i;
break;
}
if (buf[i] == '.') {
continue;
}
if (buf[i] == '-') {
negative = true;
continue;
}
value = value * 10 + (buf[i] - '0');
}
if (negative) {
value = -value;
}Таким изменением мы уже получаем достаточно крупный скачок: 4м45с, в 2.6 раза быстрее оригинала.
Чтение файла
Ещё один хороший способ ускориться идёт от оптимизации чтения файла.
Моей первой идеей было читать файл большими кусками. У такого подхода есть один недостаток: по сути надо будет делать логику работы с "огрызками". Впрочем, этого и так не избежать, для параллелизма всё равно понадобится что-то подобное.
Вынося логику обработки строк в processLine и читая файл кусками по 64МБ можно получить что-то подобное:
enum chunkSize = 64 * 1024 * 1024;
auto file = File(fname, "rb");
ubyte[] buffer = new ubyte[chunkSize];
ubyte[] leftover;
while (true) {
auto bytesRead = file.rawRead(buffer);
if (bytesRead.length == 0) break;
ubyte[] chunk = leftover.length > 0 ? leftover ~ bytesRead : bytesRead;
leftover = null;
int lastNewline = cast(int)(chunk.length - 1);
while (lastNewline >= 0 && chunk[lastNewline] != '\n') lastNewline--;
if (lastNewline < 0) {
leftover = chunk;
continue;
}
if (lastNewline + 1 < chunk.length) {
leftover = chunk[(lastNewline + 1)..$];
}
int pos = 0;
while (pos <= lastNewline) {
int lineEnd = pos;
while (lineEnd <= lastNewline && chunk[lineEnd] != '\n') lineEnd++;
if (lineEnd > lastNewline) break;
processLine(chunk, pos, lineEnd, stations);
pos = lineEnd + 1;
}
}
if (leftover.length > 0) {
processLine(leftover, 0, cast(int)leftover.length, stations);
}
Такое изменение даёт нам 3м17с. Это в 3.8 раз быстрее оригинала, но, впрочем, не такое крупное ускорение, как я ожидал (и в сравнении с предыдущей итерацией). Есть способ подойти к проблеме получше, но перед этим надо сделать кое-что ещё.
Хешмапа
К этому изменению я относился несколько скептично, предполагая, что компилятор D под капотом превращает ассоциативные массивы в что-то вроде такой хешмапы сам. Ох, как же я ошибался!
Своя реализация простой хешмапы для работы с присваиваниями, методами для рехеша/добавления/выделения, конверсией в масссив в конце и простая хеш-функция для строковых имён городов (которую, каюсь, я просто скопировал из интернетов) дали в итоге впечатляющий результат: теперь время выполнения крутилось вокруг 1м44с, ускорение в целых 6.1 раза.
Читаем файл, но иначе
Читая пост про реализацию на C я заметил интересный подход к той же проблеме чтения файла. Решением у Дэнни была функция mmap(), которая мапила файл в оперативную память на уровне ОС. В поисках альтернативы в D (всё же хотелось пока не спускаться на уровень C, это было бы нечестно) я в итоге наткнулся на std.mmfile. По сути это ровно то же самое, но (насколько я понимаю) не привязанное к одной ОС (или вернее эта обёртка, которая всё сделает за тебя).
Переписывание загрузки файла на вариант с использованием MmFile значительно упростило код, и с "огрызками" уже не нужно было особо заморачиваться.
auto mm = new MmFile(fname);
auto data = cast(const(ubyte)[]) mm[];
int pos = 0;
int n = cast(int) data.length;
while (pos < n) {
int lineEnd = pos;
while (lineEnd < n && data[lineEnd] != '\n') {
++lineEnd;
}
if (lineEnd == pos && lineEnd >= n) {
break;
}
processLine(cast(ubyte[]) data, pos, lineEnd, stations);
pos = (lineEnd < n) ? lineEnd + 1 : n;
}И результат был... 9 секунд? Ну не может же всё быть так просто.
Ну, да. Как выяснилось, использование int для отслеживания позиции в файле было не самой моей благословенной идеей, так как в этот тип не помещался полный размер файла. Потребовалось время (и до стыдного много), чтобы это осознать (учитывая, что на первый взгляд результаты вроде выглядели нормально).
После исправления проблемы получился уже более честный результат: около 24.1 секунды, в 30 раз быстрее оригинала.
И, ох, это конечно впечатляет. И повторные запуски отрабатывают чуть быстрее из-за mm кэша. Но разница в скорости обычно была не слишком большая, около 0.5-1с, что определённо стоит учитывать, но пока что это не такой важный фактор.
Самое интересное: насколько лучше будет с параллелизмом?
Параллелизм
С параллелизмом в D очень весело и приятно работать. Не самая весёлая часть этого – необходимость данные поделить между тредами.
Я пошёл простым путём: данные разделены поровну между тредами (или поровну на количество заданных кусков), после чего границы блоков данных подправляются до ближайшего конца строки. В результате получаем скорректированные границы для каждого треда, с чем мы уже можем работать для независимой обработки блоков и записи данных в локальные хешмапы.
В дополнение, я наткнулся на совет отключить сборщик мусора во время горячего параллельного цикла, самой тяжёлой части, что также выиграло дополнительно секунду-другую.
immutable minChunks = cast(int)((data.length + int.max - 1) / int.max);
immutable actualThreads = max(minChunks, numThreads);
size_t[] boundaries = new size_t[actualThreads + 1];
boundaries[0] = 0;
boundaries[actualThreads] = data.length;
foreach (i; 1 .. actualThreads) {
size_t pos = (data.length * i) / actualThreads;
while (pos < data.length && data[pos] != '\n') pos++;
boundaries[i] = (pos < data.length) ? pos + 1 : data.length;
}
StationMap[] localMaps = new StationMap[actualThreads];
GC.disable();
foreach (tid; parallel(iota(0, actualThreads))) {
auto chunk = data[boundaries[tid] .. boundaries[tid + 1]];
int pos = 0;
int n = cast(int) chunk.length;
while (pos < n) {
int lineEnd = pos;
while (lineEnd < n && chunk[lineEnd] != '\n') {
++lineEnd;
}
if (lineEnd == pos && lineEnd >= n) {
break;
}
processLine(cast(ubyte[]) chunk, pos, lineEnd, localMaps[tid]);
pos = (lineEnd < n) ? lineEnd + 1 : n;
}
}
GC.enable();После этого остаётся только соединить все локальные хешмапы в одну – по сути просто сделать их обход и объединить данные.
Это дало мне результат между 8.1 и 9.5 секунд.
Но это ещё не всё. До этого момента я использовал простой dub build для сборки, но наверняка же можно поиграться с флагами компиляторов, используя gdc или ldc?
И таки да! С ldc2 -O3 -release -mcpu=native получилось спуститься ещё ниже: в диапазон от 4.5 до 7.0 секунд. (ремарка из будущего: с производительным профилем энергопотребления результат опустился до 3.4-4.6сек)
На этом всё?
Ну, не совсем, но это были мои лучшие попытки. Но пока как-то далековато от 1.6 секунд, не правда ли?
Справедливости ради, это всё ещё достаточно шустро, но всё же можно и быстрее. Моей первой мыслью было поиграться с флагами компилятора (-ffast-math -flto=full), с размером преаллокации хешмапы, мин/макс фунциями без ветвления или inline функциями. Но всё это как-то не очень дало ощутимый результат.
Два больших изменения, которые сами напрашивались – убрать всё, что может притащить сборщик мусора, и избавиться от рантайма D. Если вторая идея мне не очень нравится, это всё же не в духе D, использование по всему коду @nogc должно улучшить реализацию. И я действительно начал писать что-то подобное, но ума мне не хватило сделать достаточно хороший и стабильный код самому, так что пришлось призвать помощь. А ещё в рамках этих изменений я изменил свою хешмапу на что-то похожее на вариант у Дэнни.
Результаты такого подхода я поместил в файл app_alt.d. В ходе моих тестов этот код отрабатывал за 2.4-2.6 секунд, но спуститься ниже было уже тяжело. И я подозреваю, что эта 1 секунда частично идёт из std.parallel, а частично от оверхеда самого D.
Пользуясь своим небольшим помощником, я "конвертировал" код реализации Дэнни ван Кутена под D, чтобы посмотреть, как она будет отрабатывать после компиляции. Этот вариант кода я оставил в analyze_c.d в том же репозитории, и это конечно не идеальная реплика, но она намеренно держится как можно ближе к первоисточнику. После сборки через ldc2 -O3 -release -mcpu=native -boundscheck=off -ffast-math -flto=full (с и без -betterC результаты были почти такие же), я получил результат в 2.2-2.4 сек.
Учитывая, что основной разницей между app_alt и analyze_c было использование std.parallel, я бы предположил, что это дало лишние 150мс, но спуститься ниже было бы чрезвычайно сложно. Оставшиеся 0.6 секунды разницы скорее всего идут от оверхеда D.
В качестве заключения
Мой честный результат – 4.5-7.0 сек (или 3.4-4.6 сек), что примерно в 128 раз быстрее решения "в лоб".
Дополнительные эксперименты показали, что в целом возможно спуститься и до 2.2 секунд, и заодно прощупать оверхед D в рамках этой задачи.
Это, как мне кажется, всё ещё отличные результаты, учитывая, что самые быстрые реализации на Rust, что я видел, были в районе 6-8 секунд, хотя я уверен, что где-то существуют решения в диапазоне 1.7-2.5 сек. Самое быстрое решение на Java, что я видел, справилось за 1.5-1.7 секунд. И самые шустрые решения, что я видел на Go, справились за 2.0-3.5 секунд. И при этом я не могу утверждать, что гарантированно видел вообще все решения.
Так что даже с этим оверхедом, и даже с моей относительно простой реализацией, мне кажется D оказался в очень хорошей компании.
P.S. И только у меня руки дошли до 1brc в D, как появился другой челленж похожего плана: 100 миллионов строк на PHP от Брендта. Будет интересно попробовать написать своё решение на PHP и на D, чтобы увидеть, сколько производительности получится выжать из них.