Исследование операции конкатенации строк в PHP

7 комментариев
Исследование операции конкатенации строк в PHP

Исследование операции конкатенации строк в PHPКогда выполняешь работу, полезно знать возможности и особенности инструмента, который держишь в руках. Давным-давно я решал задачу на 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);
}

 

Читайте также

Состоялся релиз PHP 7.4
Состоялся релиз PHP 7.4

Состоялся релиз PHP 7.4

Уязвимость PHP7 подвергает сайты риску удалённого взлома
Уязвимость PHP7 подвергает сайты риску удалённого взлома

Уязвимость PHP7 подвергает сайты риску удалённого взлома

3 комментария
На осуждённых в Минске протестируют электронные браслеты
На осуждённых в Минске протестируют электронные браслеты

На осуждённых в Минске протестируют электронные браслеты

1 комментарий
Эксперимент: четырёхдневка сделала работников на 20% продуктивнее
Эксперимент: четырёхдневка сделала работников на 20% продуктивнее

Эксперимент: четырёхдневка сделала работников на 20% продуктивнее

Обсуждение

Алексей Данченко
Алексей Данченко Инженер-программист в ЛюксСофт
0

Здесь, во-первых, не хватает исходного кода, чтобы можно было хоть как-то оценить, какой конкретно код сравнивается, и как замеряется время. А, во-вторых, нет никаких объяснений и выводов. "По-видимому, он объясняется тем, что по достижении 16-кбайтного размера строки..." - нужны факты, а не догадки.

1

Спасибо за отзыв!

Я добавил к сообщению исходный текст программы 1-го эксперимента. В остальных экспериментах использовался тот же "костяк", менялась только тестовая функция и значение переменной $m, чтобы привести время опыта в разумные рамки в пределах 2-50 секунд. В эксперименте № 2 было установлено $m = 500000, что привело к росту постоянной составляющей времени на организацию цикла по переменной $j. Чтобы исключить влияние этой постоянной на результаты, я провёл опыт с пустым телом функции test () (получилось 2,43 секунды) и вычел полученное значение из результатов измерений.
Ваше замечание относительно строгости результатов принимается. Но точный ответ на вопрос сложно получить косвенными методами, нужно как минимум анализировать исходный код транслятора, а возможно и смотреть механизмы операционной системы. На данном этапе меня устроил полученный результат: в PHP исследованные операции реализованы достаточно эффективно, чтобы их можно было использовать на практике для разумных размеров данных -- до 5 Мб.

Алексей Данченко
Алексей Данченко Инженер-программист в ЛюксСофт
1

Есть предложение выложить исходный код как-нибудь так: http://ideone.com/e8rhl1, можно запустить или сделать fork и поиграться с параметрами, да и читабельнее будет.

0

ЗдОрово! Я не знал о существовании такого ресурса. Спасибо!

0

>> в PHP исследованные операции реализованы достаточно эффективно
За 20 лет можно было научиться эффективно складывать строки :)
В отличие от всех других проблем языка...

0

>> В отличие от всех других проблем языка...
Слышал много негативных высказываний о PHP. А мне он почему-то нравится. Даже его альтернативный синтаксис -- можно поностальгировать по FoxPro ;-)
Объектная модель у него, конечно, "в-ногу-стреляющая"... И отсутствие нормальной поддержки UNICODE пока что огорчает... Но ничего, с этим можно жить ;-)

0

Переделал программу тестирования производительности в PHP-класс: https://github.com/R0bur/PHP-performance-test

Теперь проводить тестирование гораздо проще. Достаточно создать свой класс на основе тестирующего класса IAPerformanceTest и описать в нём функции, содержащие тестируемый код. Тестируемые функции должны называться Test1, Test2, ..., TestN и принимать один параметр. Если требуется инициализация, то нужно ещё создать инициализирующие функции Prep1, Prep2, ..., PrepN (тоже с одним параметром). Все описанные функции будут тестироваться в одинаковых условиях, поэтому полученные результаты можно сравнивать.

После этого создаётся экземпляр класса и запускается тестирование путём вызова метода Go (vmin, vmax, vstep), где vmin - начальное значение параметра, который передаётся в тестирующуюся функцию, vmax - его максимальное значение, а vstep - шаг изменения параметра. Всё остальное тестирующий класс делает автоматически и по окончании работы выводит результаты тестирования в текстовый файл.