Вероятно, вы уже слышали о соревновании под названием "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) мы смогли существенно ускорить работу.
Заключение
Я надеюсь, вам было так же интересно читать эту статью, как и мне было интересно её писать. Если вам захочется углубиться в оптимизацию кода, не стесняйтесь принять участие и делиться своими комментариями о ваших результатах.
