Pull to refresh
255.16
BotHub
Агрегатор нейросетей: ChatGPT, Claude, Midjourney

Как я обработал один миллиард строк в PHP

Level of difficultyMedium
Reading time12 min
Views20K
Original author: Florian Engelhardt

Вероятно, вы уже слышали о соревновании под названием "The One Billion Row Challenge" (1brc), если же нет, то предлагаю ознакомиться с репозиторием 1brc Гуннара Морлинга.

Моё участие в проекте было мотивировано присутствием в нём двух моих коллег, которые достигли лидирующих позиций.

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

Первый наивный подход 

Я скопировал содержимое репозитория и сформировал датасет с миллиардом записей в текстовом файле measurements.txt. После этого приступил к разработке первоначальной, простейшей версии алгоритма, который мог бы выполнять поставленную передо мной задачу:

<?php

$stations = [];

$fp = fopen('measurements.txt', 'r');

while ($data = fgetcsv($fp, null, ';')) {

   if (!isset($stations[$data[0]])) {

       $stations[$data[0]] = [

            $data[1],

            $data[1],

            $data[1],

            1

        ];

    } else {

        $stations[$data[0]][3] ++;

        $stations[$data[0]][2] += $data[1];

        if ($data[1] < $stations[$data[0]][0]) {

            $stations[$data[0]][0] = $data[1];

        }

        if ($data[1] > $stations[$data[0]][1]) {

            $stations[$data[0]][1] = $data[1]

        }

    }

}

ksort($stations);

echo '{';

foreach($stations as $k=>&$station) {

    $station[2]=$station[2]/$station[3];

    echo $k, '=', $station[0], '/', $station[2], '/', $station[1],

}', ';

echo '}';

В этом скрипте нет ничего выдающегося: мы открываем файл и читаем данные с помощью функции fgetcsv(). Если станция ещё не была обнаружена, мы регистрируем её, если же она уже есть в нашем списке, то увеличиваем счётчик, добавляем значения температуры и обновляем минимальные и максимальные показатели при необходимости.

По завершении, я применяю функцию ksort() для сортировки массива $stations, после чего вывожу список станций, а также вычисляю среднюю температуру, разделив общую сумму на количество записей.

Эксперимент с этим базовым кодом на моём ноутбуке показал, что его выполнение занимает 25 минут ?

Теперь самое время приступить к оптимизации и использовать профайлер:

Визуализация временных интервалов позволила мне определить, что задача ограничена возможностями процессора (CPU bound). Начальный этап компиляции файла не оказывает заметного влияния, также отсутствуют существенные операции сбора мусора.

Просмотр flame-графика также полезен, так как он показывает, что я трачу 46% процессорного времени на fgetcsv().

Переход от fgetcsv() к fgets() 

Моя первая оптимизация включала замену fgetcsv() на fgets(), чтобы самостоятельно извлечь строку и разделить ее на части, используя символ ";". Мотивацией для этого было то, что fgetcsv() выполняет больше операций, чем требуется для моих целей.

// ... while (" class="formula inline">data = fgets(

$pos = strpos($data, ';'); 

$city = substr($data, 0, $pos); 

$temp = substr($data, $pos+1, -1);

 // …

 Дополнительно я переименовал $data[0] в $city и $data[1] в $temp везде.

После повторного запуска скрипта с этим изменением, время выполнения сократилось до 19 минут 49 секунд. Хотя это всё ещё довольно продолжительный период, мы наблюдаем уменьшение на 21% по сравнению с предыдущими показателями.

Flame-график отображает внесенные изменения, и переход к просмотру времени выполнения CPU по отдельным строкам кода также демонстрирует процессы, происходящие в основном блоке кода:

Я трачу ~38% времени CPU на строках 18 и 23, которые выглядят следующим образом:

18 | $stations[$city][3] ++;

   | // ...

23 | if ($temp > $stations[$city][1]) {

Строка 18 отражает первый доступ к массиву

Применение ссылок там, где это возможно

$station = &$stations[$city];

$station[3] ++;

$station[2] += $temp; 

// вместо

$stations[$city][3] ++;

$stations[$city][2] += $data[1];

Таким образом PHP не будет искать ключ в массиве $stations каждый раз при доступе, можно рассматривать это как кэширование для обращения к "текущей" станции в массиве.

И эта мера оказалась эффективной: время выполнения сократилось до 17 минут 48 секунд, что на 10% быстрее предыдущего результата!

Всего одно сравнение

Проходя по коду, я наткнулся на этот фрагмент:

if ($temp < $station[0]) {

    $station[0] = $temp;

}

if ($temp > $station[1])

    $station[1] = $temp;

}

Учитывая, что если температура ниже установленного минимума, она не может одновременно быть выше максимума, я преобразовал условный оператор в 'elseif', что потенциально экономит процессорное время.

К слову, мне неизвестен порядок следования температур в файле measurements.txt, но в зависимости от него может иметь значение, какое сравнение проводить в первую очередь.

С учётом этой оптимизации, новая версия сценария работает за 17 минут 30 секунд, что на 2% быстрее предыдущего времени. Это небольшое улучшение, но оно превосходит обычные колебания производительности.

Встраивание явного указания типов данных

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

$temp = (float)substr($data, $pos+1, -1);

И знаете что? Это незначительное изменение сократило время выполнения скрипта до всего 13 минут 32 секунд, дав улучшение производительности на целых 21%!

18 | $station = &$stations[$city];

   | // ...

23 | } elseif ($temp >$station[1]) { 

На строке 18 все еще приходится 11% времени CPU из-за доступа к массиву (поиск ключа в хеш-таблице, что является основой для ассоциативных массивов в PHP).

Затраты процессорного времени на выполнение строки 23 уменьшились примерно с 32% до 15%. Это связано с тем, что теперь PHP не нужно проводить операции преобразования типов. До введения явного приведения типов переменные $temp, $station[0] и $station[1] интерпретировались как строки, и PHP вынужден был преобразовывать их в вещественные числа для каждого сравнения.

Давайте рассмотрим JIT

В PHP OPCache по умолчанию не активен при использовании командной строки и для его включения требуется задать параметр opcache.enable_cli как on. В состав OPCache входит JIT, который, хоть и активирован по умолчанию, фактически не функционирует из-за нулевого размера буфера. Я задал для opcache.jit-buffer-size размер в 10М. После внесения этих изменений, я повторно запустил скрипт с включенным JIT и время выполнения сократилось до:

7 минут 19 секунд ?

Что обеспечило снижение длительности выполнения на 45.9%!

Что ещё можно улучшить?

Я уже сократил время выполнения с исходных 25 минут до примерно 7 минут. Одним из удивительных моментов для меня стал тот факт, что функция fgets() использует около 56 Гб/м памяти для обработки файла объемом 13 ГБ. Это выглядит подозрительно, поэтому я решил исследовать реализацию функции fgets() и обнаружил, что могу уменьшить количество выделений памяти, убрав аргумент len из вызова fgets():

while ($data = fgets($fp)){

// вместо

while ($data = fgets($fp, 999)){

Сравнение профиля до и после изменений:

Вы можете предположить, что это изменение приведёт к заметному повышению производительности, однако прирост составил всего около 1%. Это объясняется тем, что речь идёт о мелких выделениях памяти, с которыми менеджер памяти ZendMM справляется очень эффективно за счёт их размещения в специальных контейнерах (bins), обеспечивая при этом высокую скорость работы.

Можно ли ускорить процесс ещё сильнее?

Конечно, можно! До сих пор я использовал однопоточный подход, который является традиционным для большинства PHP-скриптов, однако PHP обладает возможностью многопоточной обработки на уровне пользователя с использованием расширения parallel.

Анализ профайлера указывает на то, что чтение данных является слабым местом. Замена fgetcsv() на fgets() с последующим разделением строк вручную оказалась полезной, но процесс всё ещё забирает много времени. Поэтому я предлагаю применить многопоточность для одновременного чтения данных и их обработки, после чего мы можем собрать результаты из всех потоков воедино.

$file = 'measurements.txt';

$threads_cnt = 16;

/**

 * Get the chunks that each thread needs to process with start and end position.

 * These positions are aligned to \n chars because we use `fgets()` to read

 * which itself reads till a \n character.

 *

 * @return array<int, array{0: int, 1: int}>

 */

function get_file_chunks(string $file, int $cpu_count): array {

    $size = filesize($file);

    if ($cpu_count == 1) {

        $chunk_size = $size;

    } else {

        $chunk_size = (int) ($size / $cpu_count); 

    }

    $fp = fopen($file, 'rb');

    $chunks = [];

    $chunk_start = 0;

    while ($chunk_start < $size) {

        $chunk_end = min($size, $chunk_start + $chunk_size); 

        if ($chunk_end < $size) { 

            fseek($fp, $chunk_end); 

            fgets($fp); // moves fp to next \n char

            $chunk_end = ftell($fp)

        }

        $chunks[] = [

            $chunk_start,

            $chunk_end

        ];

        $chunk_start = $chunk_end+1;

    }

    fclose($fp);

    return $chunks; 

}

/**

 * This function will open the file passed in `$file` and read and process the

 * data from `$chunk_start` to `$chunk_end`.

 *

 * The returned array has the name of the city as the key and an array as the

 * value, containing the min temp in key 0, the max temp in key 1, the sum of

 * all temperatures in key 2 and count of temperatures in key 3.

 *

 * @return array<string, array{0: float, 1: float, 2: float, 3: int}>

 */ 

$process_chunk = function (string $file, int $chunk_start, int $chunk_end): array{

    $stations = [];

    $fp = fopen($file, 'rb');

    fseek($fp, $chunk_start);

    while ($data = fgets($fp)){

        $chunk_start += strlen($data);

        if ($chunk_start > $chunk_end) {

            break;

        }

        $pos2 = strpos($data, ';');

        $city = substr($data, 0, $pos2);

        $temp = (float)substr($data, $pos2+1, -1);

        if (isset($stations[$city])){

            $station = &$stations[&city];

            $station[3] ++;

            $station[2] += $temp;

            if ($temp < $station[0]) {

                $station[0] = $temp;

            } elseif ($temp > $station[1]) {

                $station[1] = $temp;

            }

        } else {

            $stations[$city] = [

                $temp,

                $temp,

                $temp,

                1

            ];

        }

    }

    return $stations;

};

$chunks = get_file_chunks($file, $threads_cnt);

$futures = [];

for ($i = 0; $i < $threads_cnt; $i++) {

    $runtime = new \parallel\Runtime();

    $futures[$i] = $runtime->run(

        $process_chunk,

        [

            $file,

            $chunks[$i][0],

            $chunks[$i][1],

        ]

    );

}

$results = [];

for ($i = 0; $i < $threads_cnt; $i++) {

    // `value()` blocks until a result is available, so the main thread waits

    // for the thread to finish

    $chunk_result = $futures[$i]->value();

    foreach ($chunk_result as $city => $measurement) {

        if (isset($results[$city])) {

            $result = &$results[$city];

            $result[2] += $measurement[2];

            $result[3] += $measurement[3];

            if ($measurement[0] < $result[0]) {

                $result[0] = $measurement[0];

            }

            if ($measurement[1] < $result[1]) {

                $result[1] = $measurement[1];

            }

        } else {

            $results[$city] = $measurement;

        }

    }

}

ksort($results);

echo '{', PHP_EOL;

foreach($results as $k=>&$station) {

    echo "\t", $k, '=', $station[0], '/', ($station[2]/$station[3]), '/', $station[1], ',', PHP_EOL; 

}

echo '}', PHP_EOL;

Этот скрипт выполняет несколько операций: во-первых, я провожу разбиение файла на части с учетом границ строк (\n), чтобы позже использовать функцию fgets(). После того как части файла определены, я инициирую $threads_cnt рабочих потоков. Каждый из потоков открывает тот же файл и перемещается к начальной точке своего сегмента данных, затем совершает чтение и обработку данных до завершения сегмента, возвращая промежуточные результаты. В заключение, основной поток объединяет эти результаты, выполняет сортировку и осуществляет их вывод.

Этот многопоточный подход завершается всего за:

1 минуту 35 секунд ?

Это конец?

Ни в коем случае. По поводу этого решения я хочу отметить хотя бы два аспекта:

Этот код был запущен на MacОS с использованием процессора Apple Silicon, где есть проблемы с использованием JIT в версии PHP, скомпилированной с поддержкой ZTS, в следствие чего время выполнения составило 1 минуту 35 секунд без JIT. Возможно, результаты могли бы быть лучше с активированным JIT.

Я осознал, что использовал версию PHP, скомпилированную с флагами CFLAGS="-g -O0 ...", соответствующими моим ежедневным потребностям в отладке ?.

Я должен был проверить и это с самого начала, поэтому я пересобрал PHP 8.3 с флагами CLFAGS="-Os ...", и в результате получил окончательное время выполнения со 16 потоками:

? 27.7 секунд ?

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

Вот временной график при использовании 10 потоков:

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

Чему я научился? 

Каждый уровень абстракции это компромисс между удобством и затратами на циклы центрального процессора или память. fgetcsv() проста в обращении и маскирует множество деталей, однако это имеет свою стоимость. Даже fgets(), хотя и скрывает некоторые моменты, делает процесс чтения данных значительно проще.

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

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

Это может быть несвойственно для большинства PHP-программ, но благодаря параллелизму (используя ext-parallel) мы смогли существенно ускорить работу.

Заключение 

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

Tags:
Hubs:
Total votes 66: ↑64 and ↓2+72
Comments33

Articles

Information

Website
bothub.chat
Registered
Founded
Employees
2–10 employees
Location
Россия