Только у меня дошли руки до челленжа на 1 миллиард строк в D, как появился новый прикольный челленж подобного плана от Brendt'а, автора PHP Annotated: челленж на парсинг 100 миллиона строк в PHP.

Задумка обманчиво простая. На входе имеем два параметра: путь и дату, одна строка на одну запись, 100 миллионов всего. На выходе получается мапа путей и количества запросов на них в каждую дату. Главное условие -- делать всё это в PHP, без каких-либо внешних инструментов и по сути с базовыми модулями под рукой, которые можно найти на большинстве обычных серверов с PHP.

Оригинальный челленж начался 25 февраля 2026 и закончился 15 марта 2026, с лидербордами и призами от JetBrains для отправивших лучшие решения.

В этот раз я даже успел поучаствовать, залетев на 10-15 место в таблице решений с параллелизмом, но быстро улетел ниже, закончив на 35 месте (1.5сек разница с топ-1 решением) и 14-ом месте в категории однопоточных решений (3.6сек разница). (Даже заметил Данни ван Кутена из прошлого поста в лидербордах, хехе)

Мне этот челленж показался очень любопытным, поэтому я решил записать

что сделал в своём решении и что не очень помогло
что отличается в лучших решениях
как себя в таком челленже покажет D

Так что поехали.

Стартовая точка

Весь мой прогресс (включая тайминги на моей машине, той же, что в посте про D) можно посмотреть в моём форке челленжа.

Стартовое наивное решение было достаточно прямолинейным:

final class Parser
{
    public function parse(string $inputPath, string $outputPath): void
    {
        $out = [];

        $handle = fopen($inputPath, 'r');
        if ($handle === false) {
            throw new Exception("Failed to open input file: {$inputPath}");
        }

        try {
            while (($line = fgets($handle)) !== false) {
                $line = rtrim($line, "\r\n");
                if ($line !== '') {
                    [$path, $date] = $this->parseLine($line);
                    if (!isset($out[$path])) $out[$path] = [];
                    $out[$path][$date] = ($out[$path][$date] ?? 0) + 1;
                }
            }
        } finally {
            fclose($handle);
        }

        foreach ($out as $path => &$dates) {
            ksort($dates);
        }

        file_put_contents($outputPath, json_encode($out, JSON_PRETTY_PRINT));
    }

    private function parseLine(string $line): array
    {
        // skipping https://stitcher.io/, , it's all the same domain anyway
        // also skipping 15ch of datetime
        $line = substr($line, 19, -15);

        return explode(',', $line);
    }
}

Читаем файл построчно, парсим строки и пишем всё через json_encode в файл.

Эта версия в итоге отработала за 93 секунды.

Оптимизации

Раунд 1: Чтение кусками и кастомные парсеры

Первая пачка оптимизаций пришла из опыта с 1brc, а заодно из общего понимания слабых сторон PHP:

Чтение блоками. Вместо одного системного вызова за каждую строку, лучше читать сразу огромными кусками через fread, отслеживать последний переход на новую строку в чанке и идти к началу неоконченной строки в конце.
Кастомный парсер даты. Пре-рассчёт мапы $dateIds и прямой поиск 8-символьной подстроки даты напрямую.
Кастомный json-изатор. Собирать выходную JSON строку вручную и писать через fwrite + буфер записи, а не через json_encode + file_put_contents.
Базовый парсер строк. Пропуск участков фиксированной длинны (префикс URL, суффикс даты) перед поиском разделителя.
Отключение сборщика мусора.

Вставлять тут все сниппеты кода заняло бы слишком много места, но сам код можно увидеть тут.

По итогу все эти изменения дали результат в 73 секунды.

Раунд 2: глобальное пространство имён, сборщик мусора, структура кода

Следующие изменения были относительно небольшие, зато результат от них был на удивление хороший.

Глобальное пространство имён при вызове функций. Добавление префикса \ (например \strpos, \substr...) даёт интерпретатору PHP понять, что это функция не из локального пространства имён. Это сохраняет небольшое количество времени, но на дистанции 100 млн строк даёт ощутимую разницу.
Встраивание логики обработки блоков прямо в основной метод. Это устраняет оверхед вызова функций и позволяет PHP встраивать переменные.

public function parse(string $inputPath, string $outputPath): void
{
    \gc_disable();

    $handle = \fopen($inputPath, 'rb');
    \stream_set_read_buffer($handle, 0);
    $remaining = \filesize($inputPath);

    while ($remaining > 0) {
        $toRead = $remaining > self::READ_CHUNK ? self::READ_CHUNK : $remaining;
        $chunk = \fread($handle, $toRead);
        $chunkLen = \strlen($chunk);
        $remaining -= $chunkLen;

        $lastNl = \strrpos($chunk, "\n");
        $tail = $chunkLen - $lastNl - 1;
        if ($tail > 0) {
            \fseek($handle, -$tail, SEEK_CUR);
            $remaining += $tail;
        }

        $p = self::PREFIX_LEN;
        while ($p < $lastNl) {
            $sep = \strpos($chunk, ',', $p);
            // ...
            $p = $sep + 52;
        }
    }
}

Итог: 31.45 секунд

Раунд 3: Таблицы поиска и одномерное хранилище

Два самых больших выигрыша при однопоточности пришли от снижения количества лишних рассчётов при выполнении:

Предварительно составленные таблицы путей и дат. После сканирования первых 2 МБ файла можно сразу составить список всех уникальных слагов и назначить каждому числовой ID. И рассчитать заранее все валидные даты. Это сохранит время на лишних манипуляциях со строками.
Предрассчитанные базовые оффсеты. По сути хранить $pathId * $dateCount в таблице напрямую.
Одномерный массив вместо вложенного ассоциативного массива. Наверное самое важное изменение. Один поиск по таблице вместо двух, и int-ключи, с которыми PHP работает быстрее, чем со строковыми.

// as a rough example of what's happening in the actual code
$raw = \fread($handle, self::PATH_SCAN_SIZE);
$pos = 0;
while ($pos < $lastNl) {
    $nlPos = \strpos($raw, "\n", $pos + 52);
    $slug = \substr($raw, $pos + self::PREFIX_LEN, $nlPos - $pos - 51);
    if (!isset($pathIds[$slug])) {
        $pathIds[$slug] = $pathCount;
        $pathBaseMap[$slug] = $pathCount * $dateCount;
        $pathCount++;
    }
    $pos = $nlPos + 1;
}

//...

$sep = \strpos($chunk, ',', $p);
$idx = $pathBaseMap[\substr($chunk, $p, $sep - $p)] + $dateIds[\substr($chunk, $sep + 3, 8)];
$counts[$idx]++;
$p = $sep + 52;

Результат: 15.9 секунд

Бонус: разворачивая цикл

Одна из небольших полезных фишек — это разворачивание цикла в 8-12 идентичных кусков кода. Это снижает количество проверок предусловий и часто может дать небольшой буст производительности.

Результат: 14.3 секунды

Параллелизм

Это была моя первая попытка работы с параллелизмом в PHP, но подход тут очень схож с C. По сути мы просто делаем по pcntl_fork на ядро.

Основная задумка тут — назначить диапазон байт файла одному из воркеров, оставить его обрабатывать данные, а потом записать результат во временный файл. Когда все воркеры закончат, основной поток соберёт все результаты и просуммирует.

// rough outline of the idea

$numProcs = \max(1, (int) \shell_exec('nproc') ?: 4);
$ranges = $this->splitRanges($inputPath, $fileSize, $numProcs);

for ($i = 0; $i < $numProcs; $i++) {
    $tmp = \tempnam(\sys_get_temp_dir(), 'mrc_');
    $pid = \pcntl_fork();
    if ($pid === 0) {
        $output = $this->processRange(...);
        \file_put_contents($tmp, $output);
        exit(0);
    }
    $pidToTmp[$pid] = $tmp;
}

// ...

while ($pending > 0) {
    $finished = \pcntl_waitpid(-1, $status);
    $proc = \array_values(\unpack('C*', \file_get_contents($pidToTmp[$finished])));
    for ($j = 0; $j < $outputSize; $j++) {
        $counts[$j] += $proc[$j];
    }
    $pending--;
}

Результат: 3.6 секунд

И последняя попытка

Последним изменением я добавил небольшой кусок логики с картой nextchar (бесстыже позаимствовал идею из решения xHeaven). Счётчик записывается как чистые байты в строку

$next = [];
for ($i = 0; $i < 255; $i++) {
    $next[\chr($i)] = \chr($i + 1);
}

$output = \str_repeat("\0", $outputSize);

$output[$idx] = $next[$output[$idx]];

Это дало мне 2.79 секунд без системного кэширования файла и 1.6 секунд с ним. На референсном железе челленжа мой результат был 3.7 секунд.

Учимся у лучших

У меня конечно оставалось ещё время что-то попробовать усовершенствовать своё решение, но мне показалось, что это уже будет не честно, так как к этому моменту всё, что я делал — подглядывал за решениями топ-3 участников. Так что вместо этого я решил отметить для себя, что они сделали иначе и что привело к такой разнице в производительности.

Я смотрел на решения топ-3 участников: xHeaven, AcidBurn86 и l0gicnz, все трое примерно на одном уровне с результатом около 2.028 секунд.

Главные отличия, которые дали самые крупные улучшения производительности:

Больше воркеров: повышение с 10 до 12 даёт ощутимый прирост
Использование sodium_add для объединения SIMD: немного ощущается как читерство, по сути отдаёт эту задачу на растерзание C
UNIX сокеты вместо временных файлов для синхронизации: позволяет избежать ненужных операций ввода/вывода на диске, что даёт большой прирост производительности
Избавление от strpos: он знаменит тем, насколько он порой замедляет производительности, особенно при большом количестве вызовов, так что замена strpos на специализированную альтернативу тут даёт чудесные результаты
Обратный обход с суффикс ключом: идём по строкам в обратном направлении, с известной датой и длинной строки в начале URL, что сохраняет время на большом количестве ненужных лукапов
Объединение stride+index в одно значение для мапы: использование байтовых смещений для получения всего в одном значении, что позволяет сэкономить время на поиске

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

Бонус: что скажет решение на D

Ну и для сравнения я решил написать тот же код, но на D, который выполняется за 0.4-0.7 секунд: примерно в 2-4 раза быстрее лучшего PHP решения на той же машине.

Функционально версия на D практически такая же, но есть пара ключевых отличий:

тут используется std.parallelism, так что с потоками работать значительно проще
вместо встроенных ассоциативных массивов, я использовал реализацию хешмапы (ту же, что и в d1brc)
MmFile для загрузки и чтения файла

auto mm   = new MmFile(argv[1]);
auto data = cast(const(char)[]) mm[];

foreach (tid; parallel(iota(0, numThreads))) {
    processChunk(data, bounds[tid], bounds[tid + 1], &pathMap, localCounts[tid], next);
}

foreach (lc; localCounts)
    foreach (i, v; lc)
        counts[i] += v;

И, конечно же, MmFile дала самый ощутимый прирост. Следом была хешмапа. Ну и конечно же от компиляции и оптимизаций на стороне компилятора тоже были большие выигрыши.

В качестве заключения

Это определённо было увлекательно, интересно опыт и познавательно.

Увидеть, как время выполнения сократилось с 93 секунд до 2-3 секунд уже само по себе круто, но ещё интереснее разбираться, как этого достичь. К моменту, когда я закончу эту запись в блоге, эти фишки нашли свой путь в общий пайплайн LRG2.

Версия на D тоже добавила веселья и стала своего рода реалити чеком: да, она быстрее, чем PHP, возможно и версия Go была бы примерно на том же уровне, если не чуть медленнее, но важно помнить, что на данный момент разница в скорости была не такой уж большой. Что вообще удивительно: я не ожидал, что PHP сможет справиться с этой задачей настолько хорошо.

А на этом всё. Весёлые программистские челленжи — круто.

Lea's Log

Челленж на 100 миллионов строк в PHP. С 93 до 2.8 секунд (и ниже)