Препарируем PHP. Как устроены while, foreach, array_walk и некоторые другие страшные слова

в 7:54, , рубрики: funcorp, php, Блог компании FunCorp, ненормальное программирование

Препарируем PHP. Как устроены while, foreach, array_walk и некоторые другие страшные слова - 1
Дело было вечером, делать было нечего. Самое время устроить небольшой разбор того, чем изнутри отличаются некоторые способы перебора массивов в PHP.

Исходники от master ветки (это сейчас 7.4 с вкраплениями 8)
Генератор опкодов от php 7.3.0.
Замеры производились на 7.3.6.

Дисклеймер для зануд: упоминание пары наносекунд и тактов процессора – это такой полемический приём под названием «гипербола».
Может быть, на самом деле, там десятки или сотни наносекунд и тысячи тактов, но это всё равно настолько малые величины, что необходимость экономить на них говорит о том, что что-то в вашем коде не так.

Этап компиляции

for, foreach, do и while являются ключевыми словами языка, тогда как функции array_* – это функции стандартной библиотеки. Следовательно, при прочих равных, по первым парсер отработает на пару наносекунд быстрее.

Парсер

До токена statement путь будет одинаков для всех

start -> top_statement_list -> top_statement -> statement

Циклы определены на уровне statement:

->T_FOR '(' for_exprs ';' for_exprs ';' for_exprs ')' for_statement
->T_FOREACH '(' expr T_AS foreach_variable ')' foreach_statement
->T_FOREACH '(' expr T_AS foreach_variable T_DOUBLE_ARROW foreach_variable ')' foreach_statement
->T_DO statement T_WHILE '(' expr ')' ';'
->T_WHILE '(' expr ')' while_statement

Отличие for_exprs от просто expr только в том, что для первого допустима запись нескольких expr через запятую.
foreach_variable – это конструкция, которая помимо просто variable, также отслеживает распаковку с помощью list или [].
for_statement, foreach_statement, while_statement отличаются от стандартного statement тем, что в них добавлена возможность разбора альтернативного синтаксиса:

foreach($array as $element): 
  #do something 
endforeach; 

Вызов функций закопан гораздо глубже:

-> expr -> variable -> callable_variable -> function_call -> name argument_list

callable_variable, хм… Забавно, не правда ли? :)

Перейдём к опкодам

Для примера давайте возьмём простой перебор индексированного массива с печатью каждого ключа и значения. Понятно, что использование for, while и do для такой задачи не оправдано, но у нас цель просто показать внутреннее устройство.

foreach

$arr = ['a', 'b', 'c'];   // в дальнейших примерах будем использовать его же
foreach($arr as $key => $value) echo $key.$value;
line     #* E I O op                 fetch          ext  return  operands
---------------------------------------------------------------------------
   2     0  E >   ASSIGN                                         !0, <array>
   4     1      > FE_RESET_R                             $4      !0, ->7
         2    > > FE_FETCH_R                             ~5      $4, !1, ->7
         3    >   ASSIGN                                         !2, ~5
         4        CONCAT                                 ~7      !2, !1
         5        ECHO                                           ~7
         6      > JMP                                            ->2
         7    >   FE_FREE                                        $4
   5     8      > RETURN                                         1

Что тут происходит:


FE_RESET_R: создаёт итератор $4 для массива !0. Либо, если массив пуст, сразу переходит к инструкции 7.
FE_FETCH_R: совершает шаг итерации, извлекает текущий ключ в ~5, а значение в !1. Либо, если достигнут конец массива, переходит к инструкции 7.
Инструкции 3-6 не особо интересны. Тут происходит вывод и возврат к FE_FETCH_R.
FE_FREE: уничтожает итератор.

for, while, ...

$length = count($arr);
for($i = 0; $i < $length; $i++) echo $i.$arr[$i];

На самом деле это частный случай while

$i = 0;
while($i < $length) {
    echo $i.$arr[$i];
    $i++;
}

На самом деле это частный случай if+goto

$i = 0;
goto check;
body:
    echo $i.$arr[$i];
    $i++;
check:
if($i < $length) goto body;

Опкоды для всех трёх случаев будут практически идентичны. Разве что в случае с if, JMPNZ поменяется на пару JMPZ+JMP из-за входа в тело if'а.
Для цикла do опкоды будут незначительно отличаться из-за его постпроверочной природы.

line     #* E I O op                 fetch          ext  return  operands
---------------------------------------------------------------------------
   3     0  E >   ASSIGN                                         !0, <array>
   5     1        COUNT                                  ~4      !0
         2        ASSIGN                                         !1, ~4
   6     3        ASSIGN                                         !2, 0
         4      > JMP                                            ->10
         5    >   FETCH_DIM_R                            ~7      !0, !2
         6        CONCAT                                 ~8      !2, ~7
         7        ECHO                                           ~8
         8        POST_INC                               ~9      !2
         9        FREE                                           ~9
        10    >   IS_SMALLER                             ~10     !2, !1
        11      > JMPNZ                                           ~10, ->5
        12    > > RETURN                                         1

Опкодов, ожидаемо, стало больше.
0-2: вычисление $length.
3: $i = 0
4, 10, 11: первичная проверка условия выхода и, собственно, либо выход, либо переход к телу цикла.
5(FETCH_DIM_R): $arr[$i]
6-7: вывод
8-9: $i++ (обратите внимание, что опкод инкремента в любом случае возвращает значение, даже если оно не нужно. Поэтому требуется дополнительная инструкция FREE, для его очистки).
10-11: проверка условия выхода после инкремента.

А можно ещё и так поитерировать

$value = reset($arr);
$key = key($arr);
while($key !== null) {
    echo $key.$value;
    $value = next($arr);
    $key = key($arr);
}

Простыня, так что под спойлер

line     #* E I O op                 fetch          ext  return  operands
---------------------------------------------------------------------------
   3     0  E >   ASSIGN                                         !0, <array>
   5     1        INIT_FCALL                                     'reset'
         2        SEND_REF                                       !0
         3        DO_ICALL                               $4      
         4        ASSIGN                                         !1, $4
   6     5        INIT_FCALL                                     'key'
         6        SEND_VAR                                       !0
         7        DO_ICALL                               $6      
         8        ASSIGN                                         !2, $6
   7     9      > JMP                                            ->20
   8    10    >   CONCAT                                 ~8      !2, !1
        11        ECHO                                           ~8
   9    12        INIT_FCALL                                     'next'
        13        SEND_REF                                       !0
        14        DO_ICALL                               $9      
        15        ASSIGN                                         !1, $9
  10    16        INIT_FCALL                                     'key'
        17        SEND_VAR                                       !0
        18        DO_ICALL                               $11     
        19        ASSIGN                                         !2, $11
   7    20    >   IS_NOT_IDENTICAL                       ~13     !2, null
        21      > JMPNZ                                          ~13, ->10
  11    22    > > RETURN                                         1

Этот вариант хорош тем, что подходит для итерации по массиву с любыми ключами, а не только с монотонно возрастающими целыми числами.
Функции reset, next и key довольно легковесные, но накладные расходы на их вызов всё же есть. И, как мы увидим дальше, расходы эти велики.

Хотя такой подход очень сильно напоминает принцип работы foreach, между ними есть два принципиальных отличия.
1) Тогда как reset, next и keycurrent тоже) работают напрямую с внутренним указателем массива, foreach использует собственный итератор и не меняет состояние внутреннего указателя.
Т.е.

foreach($arr as $v) echo $v.' - '.current($arr).PHP_EOL;

//----------------

a - a
b - a
c - a

2) При использовании foreach для итерации по значению, что бы вы не делали с массивом внутри цикла, проитерирован будет именно первоначальный набор данных

foreach($arr as $v) {
    $arr = ['X','Y','Z'];
    echo $v.PHP_EOL;
}
var_dump($arr);

//----------------

a
b
c
array(3) {
  [0]=>
  string(1) "X"
  [1]=>
  string(1) "Y"
  [2]=>
  string(1) "Z"
}

Что будет при итерации по ссылке, можно почитать в этом RFC. Там всё не очень просто.

array_walk с анонимной функцией

array_walk($arr, function($value, $key){ echo $key.$value;});

Так как используется пользовательская функция, то будет дополнительный набор опкодов.

Функция

line     #* E I O op                 fetch          ext  return  operands
---------------------------------------------------------------------------
         0  E >   RECV                                   !0      
         1        RECV                                   !1      
         2        CONCAT                                 ~2      !1, !0
         3        ECHO                                           ~2
         4      > RETURN                                         null

Основной код

line     #* E I O op                 fetch          ext  return  operands
---------------------------------------------------------------------------
   2     0  E >   ASSIGN                                         !0, <array>
   4     1        INIT_FCALL                                     'array_walk'
         2        SEND_REF                                       !0
         3        DECLARE_LAMBDA_FUNCTION                        '%00%7Bclosure%7D%2Fin%2FHuNEK0x7f9fa62d105a'
         4        SEND_VAL                                       ~2
         5        DO_ICALL                                       
         6      > RETURN                                         1

Поскольку array_walk, как и остальные функции стандартной библиотеки, является интринсиком, то в скомпилированных опкодах механизм итерации отсутствует.

INIT_FCALL: инициализируем вызов array_walk
SEND_REF: кладём ссылку на массив на стек вызова
DECLARE_LAMBDA_FUNCTION: объявляем анонимную функцию
SEND_VAL: кладём анонимную функцию на стек вызова
DO_ICALL: запускаем array_walk на выполнение

Далее там происходит магия с вызовом нашей лямбды для каждого элемента массива.

array_walk с использованием предопределённой функции

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

line     #* E I O op                 fetch          ext  return  operands
---------------------------------------------------------------------------
   3     0  E >   ASSIGN                                         !0, <array>
   9     2        INIT_FCALL                                     'array_walk'
         3        SEND_REF                                       !0
         4        SEND_VAL                                       'my_echo'
         5        DO_ICALL                                       
         6      > RETURN                                         1

Выводы банальны. foreach заточен под итерирование массивов, тогда как остальные циклы – просто обёртка над if+goto.
Функции же стандартной библиотеки работают по принципу чёрного ящика.

Погружаемся чуть глубже

Для начала рассмотрим случай с for и его опкодом FETCH_DIM_R, использующимся для извлечения значения по ключу. Извлечение элемента идёт через поиск в хеш-таблице (ZEND_HASH_INDEX_FIND). В нашем случае извлечение идёт из упакованного массива (ключи – непрерывная числовая последовательность) – это довольно лёгкая и быстрая операция. Для неупакованных массивов она будет чуть подороже.

Теперь foreach (FE_FETCH_R). Тут все банально:
1) Проверяем, не вышел ли указатель итератора за пределы массива
2) Извлекаем текущие ключ и значение
3) Инкрементируем указатель

Ну а что происходит с функциями типа array_walk? Хоть все они делают разные вещи, но в основе у них у лежит один и тот же принцип.
Если совсем упрощённо, то (псевдокод):

reset_pointer()
do {
  value = get_current_value()
  if (value == NULL) break         // Именно NULL, а не zval типа NULL
  key = get_current_key()
  call_function(myFunction, key, value)
  increment_pointer()
} while(true)

На самом деле внутри всё сложнее, но суть одна – идёт довольно быстрый перебор хеш-таблицы без участия виртуальной машины PHP (не учитывая вызова пользовательской функции).

Ну и немного замеров

А то ведь какая же статья без замеров (по памяти получилось настолько одинаково, что убрал её измерение).
В качестве массива, по традиции, возьмём zend_vm_execute.h на 70.108 строк.

Скрипт замера под спойлером

<?php
$array = explode("n", file_get_contents('/Users/rjhdby/CLionProjects/php-src/Zend/zend_vm_execute.h'));

function myEcho($key, $value){
    echo $key . $value;
}

ob_start();
$startTime = microtime(true);
for ($i = 0; $i < 10; $i++) {

//    foreach ($array as $key => $value) {
//        echo $key . $value;
//    }

//    foreach ($array as $key => &$value) {
//        echo $key . $value;
//    }

//    $length = count($array);
//    for ($j = 0; $j < $length; $j++) {
//        echo $j . $array[$j];
//    }

//    array_walk($array, function($value, $key) {
//        echo $key . $value;
//    });

//    array_walk($array, 'myEcho');

//    $value = reset($array);
//    $key = key($array);
//    while($key !== null) {
//        echo $key.$value;
//        $value = next($array);
//        $key = key($array);
//    }

}
$endTime = microtime(true);
ob_clean();

echo "time: " . ($endTime - $startTime);

Каждое измерение запускал раз по 10, выбирая наиболее часто встречающееся по первым 4-м цифрам.

foreach            time: 0.12159085273743
foreach(reference) time: 0.11191201210022
for, while         time: 0.13130807876587
array_walk(lambda) time: 0.87953400611877
array_walk(name)   time: 0.50753092765808
next,key           time: 1.06258893013

Подведём итоги

Анализируя результаты, не забываем учитывать, что они получены на 10 проходах по массиву из 70 тысяч элементов.

Абсолютным антигероем оказалась «эмуляция» foreach с помощью next/key. Не делайте так без крайней на то необходимости.
array_walk с лямбдой дышит ему в спину, но тут есть нюанс. Грядущий JIT может кардинально изменить ситуацию. А может и не изменить. Интересно будет посмотреть.
array_walk с использованием готовой функции – крепкий середнячок.
Так как при итерации по ссылке foreach работает несколько иначе (использует опкод FE_FETCH_RW вместо FE_FETCH_R), то сделал для него отдельный замер. Он действительно чуть-чуть быстрее получился.

Как оказалось, создание лямбды на лету – не самая дешёвая операция. Казалось бы, создаётся она всего 10 раз. Надо будет поизучать.
Все остальные способы показали примерно одинаковые результаты, с очень незначительным разрывом.

Спасибо за внимание!
Если есть предложения, что ещё можно «поковырять» – пишите в комментариях. Я пока подумываю о лямбдах – уж очень странна такая просадка производительности.

Автор: Громов Андрей

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js