tony2001: Строки в PHP

$tony2001 (

tony2001) wrote,
@ 2006-06-19 23:23:00

Entry tags:

php, sara, строки

Строки в PHP
Строки в PHP by Sara

(Post a new comment)

	md_x 2006-06-20 06:07 am UTC (link)
	Спасиб. будет куда тыкать носом народ. :-) (Reply to this)

	scoon_the_crazy 2006-06-20 10:39 am UTC (link)
	Господи... Что ж они такое курили, прежде чем писать код работы со строками... (Reply to this) (Thread)

	tony2001 2006-06-20 10:45 am UTC (link)
	мм? по-моему, там понятно разжевано как и почему работает. (Reply to this) (Parent)(Thread)

scoon_the_crazy
2006-06-20 10:52 am UTC (link)

Я вот про код, который на выходе порождает:

INIT STRING  ~0
ADD_STRING   ~0 ~0 'This'
ADD_STRING   ~0 ~0 ' '
ADD_STRING   ~0 ~0 'is'

Может я торможу, но почему не один ADD_STRING?

(Reply to this) (Parent)(Thread)

	tony2001 2006-06-20 11:29 am UTC (link)
	Why does this happen? Because there are about a dozen ways that a variable can be hidden inside an interpolated string. (Reply to this) (Parent)(Thread)

	scoon_the_crazy 2006-06-20 11:53 am UTC (link)
	Продолжаю тормозить. Разве в плане обработки переменных приведенный выше код отличается от приведенного ниже? ADD_STRING ~0 ~0 'This is' Если да, то чем? (Reply to this) (Parent)(Thread)

	tony2001 2006-06-20 12:02 pm UTC (link)
	лучше этот вопрос задать Саре. (Reply to this) (Parent)

	levgem 2006-06-20 04:06 pm UTC (link)
	Хорошо, но почему не ARRAY_ADD_STRING 'This' ARRAY_ADD_STRING 'This' ARRAY_JOIN Это ведь было бы быстрее. (Reply to this) (Parent)(Thread)

	tony2001 2006-06-20 04:17 pm UTC (link)
	а массив причем здесь вообще? (Reply to this) (Parent)(Thread)

	levgem 2006-06-20 04:20 pm UTC (link)
	Да в том, что если заранее известно, что операция будет представлять из себя множественную конкатенацию не оптимизированных для этого строк, то засунуть их в массив и сджойнить существенно быстрее. (Reply to this) (Parent)(Thread)

	tony2001 2006-06-20 04:30 pm UTC (link)
	даа? копирование данных в массив и конкатенация массива - это проще, чем конкатенация строки? (Reply to this) (Parent)(Thread)

	sply 2006-06-20 07:27 pm UTC (link)
	да, проще. без шуток. (Reply to this) (Parent)(Thread)

	tony2001 2006-06-20 07:46 pm UTC (link)
	обоснуйте. (Reply to this) (Parent)(Thread)

sply
2006-06-20 08:10 pm UTC (link)

/me ворчит: почему нельзя сразу поверить или самому смоделировать.

Потому что в 10 последовательных конкатенациях к одной строке мы имеем в худшем случае 10 выделений/освобождений памяти и копирований из старой результирующей строки в новую.

В лучшем случае, когда используется специальный менеджмент памяти, заточенный под строки и выделяющий на каждуй строку память с замасом для конкатенаций, оверхед в сумме будет меньше, т.е. если на каждую строку в 10 байт мы держим буфер 1024 байта, то мы конкатенацию засунем быстро, но имеем дикий оверхед по памяти (это ж на каждый "\n" выделять 1K) и по промахам кэша CPU, что на самом деле очень как заметно.

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

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

В PHP, скорее всего первый вариант, т.к. второй, все-таки, извращение, а третий - экзотика. Но в любом из вариантов - с массивом будет быстрее.

(Reply to this) (Parent)(Thread)

tony2001
2006-06-20 08:23 pm UTC (link)

>Потому что в 10 последовательных конкатенациях к одной строке мы имеем в
> худшем случае 10 выделений/освобождений памяти и копирований из старой
> результирующей строки в новую.

realloc() + memcpy() - где тут освобождения и новые выделения?

>А в массив мы закидываем только указатели на строки, затем при конкатенации
>всего макссива сразу один раз выделяем память под размер всех строк и
>почередно их копируем в результат.

т.е. надо будет два раза обходить весь массив - первый раз чтобы посчитать длину всех строк, второй раз чтобы их поочередно скопировать.
плюс ПЕРЕД этим надо будет создать сам массив, что уже предполагает malloc() и memcpy().

(Reply to this) (Parent)(Thread)

sply
2006-06-20 08:46 pm UTC (link)

освобождение, новое выделение и копирование из старой области в новую прячутся в realloc(). realloc увеличит размер выделенной памяти без копирования только в том случае, если размер заранее выделенной области меньше, чем запрашиваемый сейчас. В freebsd 5 один чанк для маллока - 16 байт. В этом случае для примера из статьи была бы как-минимум одна реаллокация с копированием старых данных. Плюс внутри каждого реаллока без переноса - просто сложение, сравнение, сохранение.

Ладно, давай я на остальные вопросы отвечать сейчас не буду. Если, скажем, до завтра вопросы так и остануться непонятыми, напомни, пожалуйста, я распишу детально.

(Reply to this) (Parent)(Thread)

tony2001
2006-06-20 09:01 pm UTC (link)

>realloc увеличит размер выделенной памяти без копирования только в том
> случае, если размер заранее выделенной области меньше, чем запрашиваемый сейчас.
не факт.
realloc() не означает, что вся память выделяется заново и всё содержимое заново копируется в неё.

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

(Reply to this) (Parent)(Thread)

sply
2006-06-21 09:11 am UTC (link)

Это уже религиозный догматизм - вы принимаете за аксиому утверждение, ошибочность которого можно проверить и теорией, и практикой. Если, не смотря на то, что я сообщил уже достаточно много и вы имели достаточно времени, чтобы делать самостоятельный вывод, вы предпочитаете стоять на аксиоме домысла, дальнейшее объяснение вряд-ли способно изменить вашу позицию и ваше понимание.

Кроме того, меня удивляет, что вы никак не прокомментировали пример с тестами просто конкатенации и output buffer. А он уже на практике вполне заметно демонстрирует неэффективность конкатенации.

(Reply to this) (Parent)

spacoom
2006-06-29 08:16 pm UTC (link)

На самом деле память действительно выделяется заново в большинстве случаев как минимум в фрибсд, подозреваю в линуксе дело обстоит также. Вот реализация malloc/realloc в freebsd:

http://www.freebsd.org/cgi/cvsweb.cgi/~checkout~/src/lib/libc/stdlib/malloc.c?rev=1.127&content-type=text/plain

(Reply to this) (Parent)(Thread)

tony2001
2006-06-29 08:34 pm UTC (link)

хм. забавно..
т.е. фря даже не пытается что-либо оптимизировать, а тупо делает malloc()/memcpy()/free().
не могу сказать, что я сильно удивлён - этого следовало ожидать от фри.

вот как это сделано в glibc:

  realloc(Void_t* p, size_t n)
  Returns a pointer to a chunk of size n that contains the same data
  as does chunk p up to the minimum of (n, p's size) bytes, or null
  if no space is available.

  The returned pointer may or may not be the same as p. The algorithm
  prefers extending p when possible, otherwise it employs the
  equivalent of a malloc-copy-free sequence.

  If p is null, realloc is equivalent to malloc.

исходники тут: http://sourceware.org/cgi-bin/cvsweb.cgi/libc/malloc/malloc.c?rev=1.158&content-type=text/x-cvsweb-markup&cvsroot=glibc

(Reply to this) (Parent)(Thread)

	quappa 2006-07-02 10:40 pm UTC (link)
	У нас разный интернет :) По указанному урлю (исходники FreeBSD) на моём компьютере открывается шикарный аллокатор с сильно оптимизированным реаллоком. (Reply to this) (Parent)

	9000 2006-06-21 01:48 pm UTC (link)
	Разве №3 -- экзотика? Мне он кажется единственно здравым :) Особенно в случае, когда строки не null-terminated, а со счётчиком в начале (как сделал бы я). (Reply to this) (Parent)(Thread)

	sply 2006-06-21 02:15 pm UTC (link)
	Но в реальности встречается почему-то редко. Возможно, из-за того, что сложнее отлаживать. Да и не очень он известен. (Reply to this) (Parent)

sply
2006-06-20 08:16 pm UTC (link)

при поиске в гугле по zend string concatenation optimization четвертой выдает ссылку на такую статью:
http://phplens.com/lens/php-book/optimizing-debugging-php.php

цитата:
The fastest way to concatenate multiple small strings into one large string is to create an output buffer (ob_start) and to echo into the buffer. At the end get the contents using ob_get_contents. This works because memory allocation is normally the killer in string concatenation, and output buffering allocates a large 40K initial buffer that grows in 10K chunks. Added 22 June 2004.

видимо, автор статьи на своем опыте убедился про то, что строки на php реализованы первым, в лоб, способом.

(Reply to this) (Parent)(Thread)

	tony2001 2006-06-20 08:25 pm UTC (link)
	я бы скорее предположил, что автор - это очередной оптимизатор двойных кавычек, поскольку output buffering включает в себя явно значительно больше телодвижений, чем "." (Reply to this) (Parent)(Thread)

sply
2006-06-20 08:51 pm UTC (link)

можно сделать простой эксперимент и убедиться, что автор цитаты прав:

$a = '';
$b = 'abcd';

for ($i = 1000000; $i > 0; $i--) {
        $a .= $b;


real    0m10.732s
user    0m7.351s
sys     0m2.407s


$a = '';
$b = 'abcd';

ob_start();
for ($i = 1000000; $i > 0; $i--) {
        echo $b;
}
$b = ob_get_clean();

real    0m4.243s
user    0m3.117s
sys     0m0.982s

Кстати, большая разница в sys как раз и может быть вызвана тем, что в первом варианте число системных вызовов в ядро для аллокации дополнительной памяти намного больше, чем во втором. Все-таки каждый раз запрашивать у ядра кусочки по 16 байт намного дороже, чем куски по 10 K

(Reply to this) (Parent)(Thread)

spacoom
2006-06-29 09:54 pm UTC (link)

А какая ось? У меня нет под рукой современного линукса - надо проверить на нем, судя по линку товарища выше, realloc в нем хорошо оптимизирован, поэтому разработчики пхп просто могут не подозревать о других реализациях либс.

Сам столкнулся с крайне медленным реаллоком во фре. Разработчик фришного malloc советует только реаллокить как можно реже )))

(Reply to this) (Parent)(Thread)

tony2001
2006-06-29 10:00 pm UTC (link)

>поэтому разработчики пхп просто могут не подозревать о других реализациях либс.
ну да, они же живут в сферическом вакууме.

>Разработчик фришного malloc советует только реаллокить как можно реже
отличное решение.

(Reply to this) (Parent)

levgem
2006-06-20 09:00 pm UTC (link)

Вот тут то серьезная ошибка. Странно, что вы так думаете. Объект строка уже создан, надо лишь его адрес поместить в массив.
А конкатенация массива — на порядок более быстрая вещь, чем склеивание неоптимизированных для этого строк. На порядок.

(Reply to this) (Parent)(Thread)

	tony2001 2006-06-20 09:05 pm UTC (link)
	еще один.. объясните мне чем отличается некий набор из N указателей char * от того, что вы называете "массив" и в чем на порядок быстрее конкатенация char** от конкатенции N char *? (Reply to this) (Parent)(Thread)

levgem
2006-06-20 09:11 pm UTC (link)

При конкатенации N строк несколько раз будет происходить realloc.

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

Странно, что вы, вроде как занимаясь разработкой языка, этого не понимаете.

(Reply to this) (Parent)(Thread)

tony2001
2006-06-20 09:30 pm UTC (link)

>При конкатенации N строк несколько раз будет происходить realloc.
да.
см. в другом треде почему это не так критично, как вы считаете.

>При джойне массива память будет выделена один раз (наверное, если в PHP это
> сделано с умом, как в других языках, если нет, то разницы не будет) и никаких
>копирований не будет.
начнём с того, что я всё еще не понимаю что именно вы называете массивом.
то ли это char **, то ли это PHP array. вероятно, первое (или всё же нет?).

ок, возьмём первое.
почему-то вы оба не учитываете, что в случае с char ** нам придётся проходить массив ДВАЖДЫ, чтобы сначала посчитать суммарную длину всех строк, а потом уже выделить память и опять пройти массив, копируя все строки в одну.
и рост массива будет замедлять весь процесс.

мне вообще достаточно странно всё это слышать.
опкод "добавить строку к строке" будет использовать массивы? вам самим не кажется странным этот факт? если бы engine знал наперед какие опкоды к ниму придут (чтобы знать, что впереди N-ное кол-во ADD_STRING и как-то оптимизировать этот процесс) - наверное, это был бы уже не engine, а artificial intelligence.

(Reply to this) (Parent)(Thread)

	levgem 2006-06-20 09:32 pm UTC (link)
	вы можете упираться сколько угодно. Тем временем, факт остается фактом. Даже из PHP быстрее засунуть в массив строчки и сджойнить, чем склеивать через точку. (Reply to this) (Parent)(Thread)

tony2001
2006-06-20 09:39 pm UTC (link)

простите, но я не упираюсь, я аргументирую.
а вот у вас что-то одни голословные утверждения.
не продемонстрируете код, в котором "даже из PHP быстрее засунуть в массив строчки и сджойнить, чем склеивать через точку" ?
или вам продемонстрировать мои результаты сразу?

(Reply to this) (Parent)

	esycat 2006-06-20 05:44 pm UTC (link)
	А зачем вообще использовать переменные внутри строки? Это такая специфика скриптового языка для веба? (Reply to this) (Parent)(Thread)

	tony2001 2006-06-20 05:49 pm UTC (link)
	шелл явно не скриптовый язык для веба, тем не менее там это тоже есть. для пользователя удобно. (Reply to this) (Parent)(Thread)

esycat
2006-06-20 06:17 pm UTC (link)

В шелле всё иначе совсем. Там это конкатенация и только, а кроме строк ничего не существует.
Собственно, вопрос не конкретно о PHP. Просто переменные внутри строк мне всегда казались, напротив, крайне неудобным излишеством. Именно потому, что существуют a dozen ways, и не всегда можно вставить переменную в тексте так, чтобы она правильно интерпретировалась. С подсветкой синтаксиса проблемы тоже.
То, что обработка строки, в которой могут встречаться переменные, сложнее обработки статической строки, довольно очевидно, мне кажется.

(Reply to this) (Parent)(Thread)

	tony2001 2006-06-20 06:24 pm UTC (link)
	как там внутри - сложно или нет, это никак не влияет на желание пользователей иметь возможность так делать. (Reply to this) (Parent)

	karrbon 2006-06-21 11:13 am UTC (link)
	причина в том, что "This" и пробел разные токены. (Reply to this) (Parent)

Вот интересно

fantaseour
2006-06-20 05:09 pm UTC (link)

На какой длине строк или просто в каком случае эта потеря производительности будет заметна?

Хорошая статья, и по существу. Напонила вот эту:
http://www.joelonsoftware.com/articles/LeakyAbstractions.html

Просто теперь толпа леммингов будет радостно кричать, что "как же этот код может быстро работать? Там классы и строки в двойных кавычках!" Ссылаться будут на эту статью :)

(Reply to this) (Thread)

	Re: Вот интересно tony2001 2006-06-20 05:25 pm UTC (link)
	думаю, на мегабайтах вы сможете найти хоть какую-то разницу. (Reply to this) (Parent)

	Ну вот например alll 2006-06-21 11:14 am UTC (link)
	Сервер хостинг-провайдера обычно перемолачивает гигабайты. Так что в этом случае будет заметно точно. :) Конечно, если речь идёт о pretty home page - там да, всё пофигу. (Reply to this) (Parent)(Thread)

Re: Ну вот например

fantaseour
2006-06-21 11:58 am UTC (link)

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

Данная проблема производительности появляется тогда, когда мы парсим очень длинную строку да еще с переменными внутри.

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

(Reply to this) (Parent)(Thread)

	Re: Ну вот например alll 2006-06-21 12:11 pm UTC (link)
	Да, действительно, настоящий программист должен быть выше таких мелочей. (Reply to this) (Parent)(Thread)

Re: Ну вот например

fantaseour
2006-06-21 02:24 pm UTC (link)

Я все же поясню почему я так написал. хм.

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

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

Ну да. Можно сказать, что убыстрение скрипта на микросекунды в масштабе хостинг провайдера это ого-го, но это никак не связано с гигабайтами трафика.

И да -- я не любитель гоняться за такими микросекундами, что не отменяет того, что бывют случаи (например с длинной строкой), когда именно в этом месте и есть бутылочное горлышко, и хорошо бы знать как работают строки на самом деле, и почему так сделано.

(Reply to this) (Parent)

	fantaseour 2006-06-20 05:10 pm UTC (link)
	сорри, я имел в виду вот эту статью, та предыдущая на нее ссылается: http://www.joelonsoftware.com/articles/fog0000000319.html (Reply to this)

Username:		Create an Account Forgot your login? Login w/ OpenID
Password:
	Remember Me
	English • Español • Deutsch • Русский…

About

Help

Get Involved

Legal

Store

LJ Labs