Когда выполняешь работу, полезно знать возможности и особенности инструмента, который держишь в руках. Давным-давно я решал задачу на Visual Basic и столкнулся с неприятным эффектом при формировании длинной строки путём последовательного добавления отдельных символов.
С каждым символом операция выполнялась всё медленнее, ощутимо снижая отзывчивость пользовательского интерфейса. В ходе изучения проблемы было выяснено, что она возникла из-за особенностей механизма распределения памяти в используемом средстве программирования.
Эффект удалось устранить путём изменения способа формирования строки: для неё резервировалась заранее вся необходимая память, после чего символы просто устанавливались на нужные позиции (рис. 1).
Рис. 1. Два способа формирования строки: путём добавления символов (сверху) и путём вставки символов (снизу).
Приступив к работе с языком программирования PHP, я вспомнил о своём предыдущем опыте и решил проверить, как тут обстоят дела с формированием строк. Для этого написал тестовую программу и провёл несколько экспериментов.
Сразу хочу отметить, что значения времени в этой статье приводятся в относительных величинах, поскольку реальные данные будут зависеть от среды выполнения (как аппаратного, так и программного обеспечения). В каждом эксперименте использована своя шкала времени, поэтому результаты нельзя соотносить друг с другом.
Эксперимент № 1. Исследование скорости формирования строки путём добавления отдельных символов (способ 1) и путём замены символов в шаблоне строки (способ 2)
В результате эксперимента было установлено, что в языке программирования PHP операция конкатенации лишь незначительно уступает по скорости выполнения операции прямого доступа к элементу строки по его номеру (см. рис. 2). Поэтому программист может выбирать тот способ работы со строками, который обеспечивает лучшую наглядность или больше соответствует его личным предпочтениям.
Рис. 2. График зависимости времени формирования строки от её длины.
Дальнейшие эксперименты проводились для более глубокого изучения свойств операции конкатенации строк.
Эксперимент № 2. Исследование времени конкатенации строк различной длины
В этом эксперименте в цикле выполнялась операция конкатенации вида:
$string .= $part;
где $string в начале цикла — пустая строка, а строка $part имеет фиксированную длину 1, 32 или 512 символов (рис. 3).
Рис. 3. Формирование строки с помощью конкатенаций.
На графике, соответствующем 512-символьной прикрепляемой строке, хорошо заметен излом, который соответствует длине результирующей строки примерно равной 16 кбайт. По-видимому, он объясняется тем, что по достижении 16-кбайтного размера строки при необходимости её дальнейшего увеличения происходит перераспределение памяти для её хранения.
Из графиков, соответствующих малому размеру добавляемой строки $part (1, 32 символа), видно, что время выполнения конкатенаций растёт медленнее, чем количество итераций. Это объясняется значительным вкладом в общее время вспомогательных действий (затраты на организацию цикла, работа внутренних механизмов транслятора) по сравнению с собственно тестируемой операцией.
Эксперимент № 3. Исследование времени формирования строки большого размера путём многократного присоединения подстроки фиксированной длины
Этот эксперимент похож на предыдущий, только формируемая строка получается более длинной за счёт увеличения количества конкатенаций: для 512-символьной прикрепляемой строки на 10000-ной итерации формируется строка длиной около 5 Мбайт (рис. 3). Выраженная нелинейность графика для 512-символьной строки обусловлена необходимостью перераспределения памяти для хранения результата.
Рис. 4. Формирование длинной строки с помощью конкатенаций
Условия проведения экспериментов
Тестовая программа выполнялась транслятором PHP 5.5.8 под управлением Windows 7.
Для каждого эксперимента устанавливались его параметры (длина присоединяемой строки и количество итераций конкатенации), после чего проводилось 12 опытов, в результате которых получались 12 значений времени выполнения. Наибольшее и наименьшее значения отбрасывались, остальные 10 проверялись на соответствие критерию Шовене. Если при этом обнаруживался грубый промах, эксперимент повторялся. Таким образом было устранено влияние побочных факторов (работа фоновых процессов, спонтанный своппинг памяти на диск и т. п.).
Относительная погрешность измерений составила от 10% для минимальных значений измерений до 0,2% для максимальных значений при принятой точности таймера ("инструментальной погрешности") 20 мс. Надёжность оценки времени выполнения — 98%.
Исходный текст программы, использовавшейся для хронометража в эксперименте № 1:
/*===================*/
/* Тестовая функция. */
/*===================*/
function test ($a)
{
global $testval1, $testval2;
$l = $testval1 * $a;
for ($i = 0; $i < $l; ++$i)
$testval2 .= 'X';
}
/*==================================*/
/* Хронометраж выполнения операций. */
/* Автор: Игорь Орещенков, 2015. */
/*==================================*/
$testval1 = 32;
$testval2 = '';
$n = 10; // количество опытов
$m = 1000; // количество итераций в одном опыте
$di = 0.02; // инструментальная погрешность измерений
$tan = 2.9; // коэффициент доверия (98%;10)
$tu = array ();
$pu = array ();
for ($u = 1000; $u < 10001; $u += 1000):
do {
$caption = "Testing string building $u x $testval1 chars length (concatenating).";
echo $caption . "
";
/*-----------------------------*/
/* Основной цикл эксперимента. */
/*-----------------------------*/
$t = array ();
for ($i = 0; $i < $n + 2; ++$i):
$tm1 = microtime_float (); // отметка времени старта
for ($j = 0; $j < $m; ++$j):
$testval2 = '';
test ($u);
endfor;
$tm2 = microtime_float (); // отметка времени финиша
/* Результат хронометража. */
$dt = round ($tm2 - $tm1, 3);
$t[] = $dt;
echo "Experiment N $i
";
echo "Start: $tm1
";
echo "Finish: $tm2
";
echo "Elapsed: $dt
";
endfor;
/*-------------------------------------------------*/
/* Статистическая обработка результатов измерений. */
/*-------------------------------------------------*/
sort ($t);
for ($i = 0; $i < $n - 1; ++$i)
$t[$i] = $t[$i + 1];
unset ($t[$n + 1]);
unset ($t[$n]);
$tavg = avg ($t); // выборочное среднее
$tsd = stddev ($t, $tavg); // выборочное среднее квадратическое отклонение
/*------------------------------------------------------------------------------*/
/* Оценка минимального и максимального значения с точки зрения критерия Шовене. */
/*------------------------------------------------------------------------------*/
$t1 = $t[0];
$shovz1 = abs ($t1 - $tavg) / $tsd;
$t2 = $t[$n - 1];
$shovz2 = abs ($t2 - $tavg) / $tsd;
$shovm1 = shovene ($shovz1); // значение M для минимального значения
$shovm2 = shovene ($shovz2); // значение M для максимального значения
if ($shovm1 <= $n and $shovm2 <= $n):
/*------------------------------------------------*/
/* Вычисление случайной составляющей погрешности. */
/*------------------------------------------------*/
$tsdavg = $tsd / sqrt ($n); // среднее квадратическое отклонение среднего
$dtrnd = $tan * $tsdavg;
/*---------------------------------*/
/* Вычисление полных погрешностей. */
/*---------------------------------*/
$dtabs = sqrt ($di * $di + $dtrnd * $dtrnd); // абсолютная погрешность
$dtrel = round (($dtabs / $tavg) * 100, 2); // относительная погрешность в процентах
/*-----------------------------------------*/
/* Запись в файл результатов эксперимента. */
/*-----------------------------------------*/
$res = "Количество опытов: $n
";
$res .= "Продолжительность опытов: ";
for ($i = 0; $i < $n - 1; ++$i):
$res .= $t[$i] . ', ';
endfor;
$res .= $t[$n - 1] . "
";
$res .= "Средняя продолжительность: $tavg
";
$res .= "Относительная погрешность: $dtrel%
";
$fname = substr (time (), -7) .'.txt';
$f = fopen ($fname, "w");
if ($f):
fputs ($f, "$caption
");
fputs ($f, "$res
");
fclose ($f);
endif;
$tu[] = $tavg;
$pu[] = $dtrel;
echo "See file $fname for results of the experiment
";
$crit = true;
else:
echo "Shovene criteria!
";
$crit = false;
endif;
} while (!$crit);
endfor;
/*----------------------------------------------*/
/* Запись в файл общего протокола эксперимента. */
/*----------------------------------------------*/
$fname = "s" . substr (time (), -7) . '.txt';
$f = fopen ($fname, "w");
if ($f):
fputs ($f, "$caption
");
for ($i = 0; $i < count ($tu); ++$i):
$tu0 = $tu[$i];
$pu0 = $pu[$i];
fputs ($f, "$tu0 ($pu0%)
");
endfor;
fclose ($f);
endif;
/*===========================================*/
/* Вычисление выборочного среднего значения. */
/*===========================================*/
function avg ($a)
{
$n = count ($a);
echo "Debug AVG: n = $n
";
$sa = 0;
for ($i = 0; $i < $n; ++$i):
$sa += $a[$i];
endfor;
return $sa / $n;
}
/*=================================================*/
/* Вычисление среднего квадратического отклонения. */
/*=================================================*/
function stddev ($a, $aavg)
{
$n = count ($a);
$sa = 0;
for ($i = 0; $i < $n; ++$i):
$d = $a[$i] - $aavg;
$sa += $d * $d;
endfor;
return sqrt ($sa / ($n - 1));
}
/*======================================*/
/* Критерий Шовене для отбора промахов. */
/*======================================*/
function shovene ($z)
{
if ($z < 1):
$m = 1;
elseif ($z <= 1.28):
$m = 2;
elseif ($z <= 1.46):
$m = 3;
elseif ($z <= 1.58):
$m = 4;
elseif ($z <= 1.68):
$m = 5;
elseif ($z <= 1.76):
$m = 6;
elseif ($z <= 1.78):
$m = 7;
elseif ($z <= 1.82):
$m = 8;
elseif ($z <= 1.92):
$m = 9;
elseif ($z <= 1.98):
$m = 10;
elseif ($z <= 2.00):
$m = 11;
elseif ($z <= 2.04):
$m = 12;
elseif ($z <= 2.08):
$m = 13;
elseif ($z <= 2.10):
$m = 14;
elseif ($z <= 2.12):
$m = 15;
elseif ($z <= 2.16):
$m = 16;
elseif ($z <= 2.18):
$m = 17;
elseif ($z <= 2.20):
$m = 18;
elseif ($z <= 2.22):
$m = 19;
elseif ($z <= 2.24):
$m = 20;
elseif ($z <= 2.26):
$m = 21;
elseif ($z <= 2.28):
$m = 22;
elseif ($z <= 2.30):
$m = 23;
elseif ($z <= 2.32):
$m = 25;
elseif ($z <= 2.34):
$m = 26;
elseif ($z <= 2.36):
$m = 27;
elseif ($z <= 2.38):
$m = 29;
elseif ($z <= 2.40):
$m = 30;
else:
$m = 999;
endif;
return $m;
}
/*========================================================*/
/* Получение текущего времени с точностью до микросекунд. */
/*========================================================*/
function microtime_float ()
{
list ($usec, $sec) = explode (' ', microtime ());
return round ((float)$usec + (float)$sec, 3);
}
Релоцировались? Теперь вы можете комментировать без верификации аккаунта.