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