Сравнение производительности перебора массивов в цикле через for() и foreach()

    Я хотел бы обратить внимание на одну не очевидную особенность php.
    Допустим у нас есть массив с целочисленными индексами
    $arr = array( $val1, $val2, ..., $valn );
    
    Этот массив можно перебрать в цикле двумя способами
    foreach($arr as $k => $v ) {...}
    
    и
    $n = count( $arr );
    for($k = 0; $k < $n; $k++ ) {...}
    

    Кажется вполне очевидным, что второй способ должен быть, если и не быстрее, то уж точно не медленнее.
    Давайте разберемся.
    — Нет. Никаких бенчмарков. Только код!

    На самом деле, второй способ работает медленнее! Особенно это кажется не очевидным для тех, кто имеет опыт программирования на C и C++, где индекс массива — это простое смещение указателя.
    Я обнаружил эту особенность довольно давно, но все ни как не доходили руки посмотреть с чем это связано

    Итак, почему так происходит


    Давайте посмотрим на внутренне устройство массива в php.
    Внутренне, в ядре Zend, массив представлен несколькими взаимосвязанными структурами:

    Структура Bucket описывает «указатель» на текущую позицию массива
    typedef struct bucket {
    	ulong h;                   // целочисленное значение индекса
                                   // (если индекс целочисленный)
    	uint nKeyLength;           // длина строки (строкового ключа)
    	void *pData;               // значение элемента массива 
                                   // [ извлечь можно так: (zval **)pos->pData ]
    	void *pDataPtr;
    	struct bucket *pListNext;  // Указатель на следующий элемент массива
    	struct bucket *pListLast;  // Указатель на предыдущий элемент массива
    	struct bucket *pNext;      // используется для внутренних операций с arBuckets
    	struct bucket *pLast;      // используется для внутренних операций с arBuckets
    	const char *arKey;         // строковое представление ключа, если ключ строковой
    } Bucket;
    typedef Bucket* HashPosition;
    

    Структура HashTable — это и есть сам массив во внутреннем представлении:
    typedef struct _hashtable {
    	uint nTableSize;
    	uint nTableMask;
    	uint nNumOfElements;       // количество элементов в массиве
    	ulong nNextFreeElement;
    	Bucket *pInternalPointer;
    	Bucket *pListHead;         // Указатель на первый элемент массива
    	Bucket *pListTail;         // Указатель на последний элемент массива
    	Bucket **arBuckets;        // собственно, сама ХэшТаблица.
                                   // Используется для индексации как строковых
                                   // так и целочисленных ключей
    	dtor_func_t pDestructor;
    	zend_bool persistent;
    	unsigned char nApplyCount;
    	zend_bool bApplyProtection;
    } HashTable;
    

    Даже представленной уже информации достаточно, что бы понять причину. Массивы реализованы в виде двусвязных списков.
    Двусвязные списки позволяют осуществлять быструю вставку, достаточно быстрый перебор, но произвольный доступ в них — медленная операция.

    Давайте посмотрим как, все-таки, Zend осуществляет итерацию элементов массива

    // Переход к следующему элементу массива.
    int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos)
    {
    	HashPosition *current = pos ? pos : &ht->pInternalPointer;
    	if (*current) {
    		*current = (*current)->pListNext;
    		return SUCCESS;
    	} else
    		return FAILURE;
    }
    
    // Переход к предыдущему элементу массива. 
    // В php нет обратной итерации, но она поддерживается Zend
    // и может быть использована при написании расширений.
    int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)
    {
    	HashPosition *current = pos ? pos : &ht->pInternalPointer;
    	if (*current) {
    		*current = (*current)->pListLast;
    		return SUCCESS;
    	} else
    		return FAILURE;
    }
    

    Здесь, я думаю, все понятно без дополнительных объяснений — указатель на текущий элемент заменяется указателем на следующий элемент, ссылка на который хранится в текущем.

    Теперь посмотрим как осуществляется доступ по индексу.
    int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
    {
    	uint nIndex;
    	Bucket *p;
    	nIndex = h & ht->nTableMask;
    	p = ht->arBuckets[nIndex];
    	while (p != NULL) {
    		if ((p->h == h) && (p->nKeyLength == 0)) {
    			*pData = p->pData;
    			return SUCCESS;
    		}
    		p = p->pNext;
    	}
    	return FAILURE;
    }
    

    Здесь нужны некоторые пояснения.
    Я не хотел бы утомлять читателей излишне подробным описанием того, как устроен массив arBuckets (C массив из HashPosition — указателей на Bucket).
    Скажу только, что здесь осуществляется последовательный перебор части внутренней хэш таблицы arBuckets до поиска нужного значения.

    Выводы


    foreach($arr as $i => $v ){...}
    
    Достаточно быстро перебирает все элементы массива, получая их один за другим. Сложность этой операции O(n).

    for($i = 0; $i < $n; $i++ ){...}
    
    На каждой итерации ищет индекс во внутренней хэш таблице.

    Оценочно, сложность последней операции выражалась бы суммой арифметической прогрессии n*(n+1)/2 т.е. и имела бы порядок O(n2), если бы при поиске значения по индексу перебиралась бы вся хэш таблица. На самом деле, перебираются не все значения, а только часть их, поэтому сложность будет варьироваться от O(n) до O(n2). И для больших массивов, она будет ближе к, O(n). Но даже в этом случае, перебор массива с доступом по ключу — более ресурсоемкая операция.

    Что касается массивов со строковыми ключами (или смешанными — целочисленными и строковыми).
    Все вышесказанное справедливо и для них с той разницей, что скорость доступа к строковому ключу в среднем в 8 (максимум в 16) раз больше чем к целочисленному
    Share post

    Comments 49

        +11
        На самом деле, второй способ работает медленнее! Особенно это кажется не очевидным для тех, кто имеет опыт программирования на C и C++, где индекс массива — это простое смещение указателя.
        Даже на C и C++ эксперименты с видами цикла (даже не окружающим контекстом и не содержимым!) — это последнее что придёт в голову делать в плане оптимизации по скорости, а на php это вообще смешно.
          0
          Экономия на спичках.
          0
          Хорошее исследование, но не даёт никакой практической пользы, т.к. время доступа к элементам массива составляет пренебрежимо малый процент от общего времени работы скриптов. Даже если всё переписать в соответствии с вашими наблюдениями, в результате никто ничего не заметит.
            +20
            Я не предлагаю ничего переписывать. Конечно же, оно того не стоит!
            Мне просто показалось любопытной такая особенность php и ей я поделился с сообществом.
            Такие вещи лежат в основе хороших практик.
            Например выбор двойных или одинарных кавычек для строк в php — еще менее существенная вещь в плане производительности, чем то, о чем я пишу. Однако, использование одинарных кавычек — хорошая практика. Код с foreach часто выглядит элегантнее чем код с for, а если знать что он еще и быстрее, то это ли не повод взять за правило использование foreach как основного способа итерации.
              0
              Если оно несущественно, в чем смысл заострять на нём внимание? :)
              Вы правы, выбор кавычек и for vs foreach в PHP после версии 3, если не ошибаюсь, не оказывают никакого влияния на производительность и темы исчерпали себя многократно много лет назад.

              Полезнее темы в исходниках можно найти от обратного — от проблемы, а уже видя проблему, смотреть в исходники. Я так например в soap баги находил.
                +3
                > Код с foreach часто выглядит элегантнее чем код с for, а если знать что он еще и быстрее, то это ли не повод взять за правило использование foreach как основного способа итерации.

                Выше описал, что «быстрее» оно только в специально подготовленной пробирке, да и то на громадных массивах и всё равно несущественное.
                Так что рекомендовать что-то из for или foreach из соображений скорости — как-то не совсем оправдано.
                Рекомендовать эти конструкции с современным движком PHP можно только из соображений удобства использования.
                foreach — краткий синтаксис для перебора всех ключей со значениями; for — более длинный синтаксис, но можно использовать его не только для перебора. Смотря какую операцию хотите сделать. Перебрать — foreach. Сделать более хитрый цикл, нежели перебор — тогда for для вас. Вот всё, что сейчас можно порекомендовать.
                  0
                  Извините, что-то не уловил, какие средства может предоставить for для «большей хитрости», которые не может предоставить foreach?
                    +3
                    Да хотя бы просто пройти только по четным индексам, или по каждому десятому, или по числам Фибоначчи.
                    Или сделать бесконечный цикл.
                    Или выйти из цикла при нарушении инварианта более хитрого, чем «не конец контейнера».
                    И т.д. и т.п.
                +1
                Это тот самый случай, когда различие важно. Сложность алгоритмов — это такой интересный зверь, который любит выплывать на повторении операций. И если мы гипотетически решим перебрать трёхмерный массив, то тут он и вылезет в полной красе. В случае O(n) это будет O(n3), а в случае O(n2) — O(n6). В случае перебора элементов куба 20х20х20 — это соответственно 8к операций против 64кк операций. И это при том, что пхп ещё и сам по себе — весьма медленный язык.
                  0
                  Оба способа дают O(n), где вы квадрат нашли? Ниже в комментариях уже объяснили, почему никакого квадрата тут нет.
                +1
                Можно ещё ускорить и сократить потребление памяти перебирая так: foreach($arr as $k => &$v ) {...} И лучше заметна разница на больших массивах…
                  +2
                  Какие ваши доказательства? PHP при присваивании создает ссылку на значение и только клонирует данные, если значение меняется. Т.е. так, например, можно передавать в фунцию хоть сколько угодно большие массивы и не думать о памяти (но только до тех пор пока мы в функции не начнем менять данные внутри этого массива).

                  Подозреваю, что ($arr as $k => &$v ) только добавит оверхеада.
                    +1
                    Вы правы, синтаксис foreach со ссылкой — это ещё одно наследие версий PHP, передававшееся от деда к внуку, и оно давно неактуально. Zend Engine постоянно оптимизируется и синтаксис без ссылки на сколько я помню где-то в четвертых версиях PHP не даёт скорости.
                      0
                      А вы попробуйте потестить… И статейку почитайте habrahabr.ru/post/134784/
                        0
                        Потестил и оказалось, что для массивов так и есть (изза создания копии массива). Может когда-нибудь пригодится
                    +3
                    int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
                    {
                        uint nIndex;
                        Bucket *p;
                        nIndex = h & ht->nTableMask;
                        p = ht->arBuckets[nIndex];
                        while (p != NULL) {
                            if ((p->h == h) && (p->nKeyLength == 0)) {
                                *pData = p->pData;
                                return SUCCESS;
                            }
                            p = p->pNext;
                        }
                        return FAILURE;
                    }
                    


                    Вот это вообще похоже на выборку из самой обычной-преобычной хэш-таблицы. Если это так, то в arBuckets хранится в среднем 1 элемент, и итоговая сложность выборки одного элемента по индексу — константная — O(1).
                      +1
                      Мне всегда казалось, что for() медленней foreach() просто потому, что при for() делается больше операций на стороне PHP — для foreach делается лишь привязка переменных (будем считать это одной базовой операцией для PHP), а при for, как правило, 3 операции — это $i++, сравнение $i с N, и присвоение значения массива какой-нибудь переменной:

                      <?php
                      $arr = range(0, 500000);
                      
                      foreach ($arr as $i => $v);
                      
                      $cnt = count($arr);
                      for ($i = 0; $i < $cnt; $i++) $v = $arr[$i];
                      


                      Если всё же запустить бенчмарк, то получим следующие цифры на цикле без тела:

                      $ php --version
                      PHP 5.4.24 (cli) (built: Jan 19 2014 21:32:15) 
                      Copyright (c) 1997-2013 The PHP Group
                      Zend Engine v2.4.0, Copyright (c) 1998-2013 Zend Technologies
                      
                      $ php test.php
                      Foreach: 0.021 sec
                      For:     0.026 sec
                      


                      Добавив какую-нибудь полезную нагрузку (например, подсчёт $sum += $arr[$i] или $sum += $v в случае foreach), for вообще иногда выигрывает :)

                      $ php test2.php
                      Foreach: 0.029 sec (sum=125000250000)
                      For:     0.027 sec (sum=125000250000)
                      


                      Что лишь доказывает, что пользы от авторского топика никакой :))
                        0
                        Продолжая идиотские изыскания, выходит, что я всё же немного был не прав по поводу того, что привязка переменной в foreach дается абсолютно бесплатно:

                        <?php
                        $arr = range(0, 500000);
                        $max = count($arr);
                        $sum = 0;
                        
                        $start = microtime(true);
                        for($i = 0; $i < $max; $i++) $sum += $arr[$i];
                        echo "For        took " . round(microtime(true) - $start, 3) . " sec\n";
                        
                        $start = microtime(true);
                        foreach($arr as $i => $v) $sum += $v;
                        echo "Foreach_iv took " . round(microtime(true) - $start, 3) . " sec\n";
                        
                        $start = microtime(true);
                        foreach($arr as $v) $sum += $v;
                        echo "Foreach_v  took " . round(microtime(true) - $start, 3) . " sec\n";
                        
                        $start = microtime(true);
                        $sum = array_sum($arr);
                        echo "Arrsum     took " . round(microtime(true) - $start, 3) . " sec\n";
                        


                        Вот какие результаты получаются:

                        $ php test.php 
                        For        took 0.028 sec
                        Foreach_iv took 0.026 sec
                        Foreach_v  took 0.023 sec
                        Arrsum     took 0.008 sec
                        


                        Какой-то колоссальной разницы нет между этими вариантами, кроме array_sum, пожалуй :). Кажется, array_sum выигрывает за счёт того, что оббегает весь массив, но при этом не делает привязку переменных и прочей ерунды, и различия в способе хранения тут особо не при чём — основное время очевидно тратится на исполнение простейших PHP опкодов, а не на саму итерацию по массиву.
                        0
                        Тут вопрос не в обвязке этих операций, а в алгоритмической сложности. Автор топика утверждает что сложность выборки из хэш-таблицы — O(n) что есть неправда.
                          0
                          Так. Давайте мою цитату, где я такое сказал.
                          Сложность перебора N элементов не может быть меньше O(N), а больше может. Про сложность выборки из хеш-таблицы я конкретно не говорил. Сказал про сложность выборки строковых ключей (последний абзац). целочисленный ключ может быть извлечен как за одну операцию, так и за несколько.
                            0
                            Я конкретно вот про эту цитату:
                            for($i = 0; $i < $n; $i++ ){...}
                            

                            На каждой итерации ищет индекс во внутренней хэш таблице.

                            Оценочно, сложность последней операции выражалась бы суммой арифметической прогрессии n*(n+1)/2 т.е. и имела бы порядок O(n2), если бы при поиске значения по индексу перебиралась бы вся хэш таблица. На самом деле, перебираются не все значения, а только часть их, поэтому сложность будет варьироваться от O(n) до O(n2). И для больших массивов, она будет ближе к, O(n). Но даже в этом случае, перебор массива с доступом по ключу — более ресурсоемкая операция.

                            На самом деле сложность тут будет O(n), а не O(n2) во всех случаях, потому что вряд ли разработчики PHP забили на качество хэширования и обычные числовые индексы имеют весьма слабую вероятность попасть в один bucket.
                            Ну т.е. не будет перебора даже части значений, потому что в bucket-е будет ровно один элемент. В этом и смысл хэш-таблицы.
                    +1
                    Ну так такие исследования надо начинать с того, что в php ЛЮБОЙ массив — хеш-таблица. А значит код с for и $i каждый раз означает получение элемента по этому самому $i, то есть дополнительное вычисление хеша, в то время как foreach это как раз перебор по всей хеш-таблице.
                      0
                      Это никакое не исследование :) вы преувеличиваете статус моей заметки.
                      в php ЛЮБОЙ массив — хеш-таблица
                      Совершенно верно. Об этом и речь. Еще и двусвязный список. Я например не знал, что там внутри двусвязный список. И мне кажется это совсем не очевидно.
                        0
                        оО. Вы хотите сказать, что хеш-таблица двусвязный список? Может вы имеете ввиду разрешение коллизий?
                        Если второе — то это метод цепочек, второй вариант того же метода цепочек — бинарные деревья, но я не думаю что это дало бы прирост производительности большой
                          +1
                          Нет, он хочет сказать, что используется специальная модификация хеш-таблицы — прошитая хеш-таблица.

                          В Java она называется LinkedHashMap
                            0
                            Я ничего такого не говорил. Где вы такое увидели?
                            К вашему замечанию о том что php-массив является хэш таблицей, что действительно очевидно, я добавил уточнение, что помимо хэш таблицы там есть еще и двусвязный список.
                            Хранение массивов могло быть реализовано разными способами. Сама хеш таблица могла быть реализована разными способами.
                            Смысл поста не в том какие бывают хеш таблицы и как в них разрешаются коллизии, а в том как конкретно в php реализован массив.
                            Я думаю людям, практикующим программирование на php эта информация уж точно не повредит.
                              0
                              Я не пытался на вас наехать.
                              Просто я не знал о том, что хеш-таблицы реализуются через связные списки. Для меня смысл хеш-таблицы представляется в O(1) для вставки и получении элемента, за счет смещения по обычному массиву, а связные списки никак в это понятние не вписываются.
                              Помимо понимания что внутри массивов — хеш-таблица хорошо бы также понимать что за хеш таблица
                                0
                                Она, по-видимому, и не реализовывается через них. Это обычная хеш таблица, в которой вместе со значением еще хранится указатель на предыдущий положенный элемент, и на следующий. Специально для того, чтобы итерироваться, ибо в обычной хеш-таблице это невозможно.
                            0
                            Это одна из базовых структур данных, используемая в подавляющем большинстве языков программирования. О ней правда стоит почитать хотя бы вики и знать ее сложность.
                          +3
                          Для более глубокого понимания внутреннего устройства массивов в php советую статью Никиты Попова: Understanding PHP's internal array implementation.
                          • UFO just landed and posted this here
                              +2
                              Нет, это более крутой Попов.
                              • UFO just landed and posted this here
                              0
                              Вот спасибо вам за ссылочку. Там просто кладесь всякого интнреснрго.
                              +2
                              И для больших массивов, она будет ближе к, O(n)

                              Дело не в величине массива, а в том сколько будет совпадающих хэшей в хэштаблице: Supercolliding a PHP array
                                0
                                Требую честные замеры RPS, сделанные на реальном приложении.
                                Производительность будет одинаковая.

                                А еще нельзя использовать for, там где нужен foreach, а foreach там, где нужен for — это портит код.
                                  0
                                  Да кто этим for-ом вообще пользуется?
                                    0
                                    А чего бы им не пользоваться-то?
                                      0
                                      Заглянул в свой последний немаленький проект и не нашел сходу ни одного for-а. Удел for-а — повторить некоторую операцию некоторое ограниченное число раз, т.е. те случаи, когда итерируемая переменная слабо связана с содержимым цикла. Такое редко надо. Использовать for для прохода по массиву странно.
                                        0
                                        Редко и странно, ага.

                                        for ($i = 0; $i<$len; $i+=2) {
                                            for ($j = $len - 1; $j >=0; $j--) {
                                                for ($k = $j; $k >=0; $k--) {
                                                     // это всё вы тоже форичем делаете?
                                               }
                                            }
                                        }
                                        
                                          0
                                          Насколько я понял вашего собеседника, ваш пример не о том.
                                          Blumfontein как будто бы говорит о том, что for используется в основном в отрыве от перебираемого массива, т.е. когда не важны ключи, а foreach — наоборот, когда это важно.

                                          Т.е. обратите внимание, что в вашем примере все индексы числовые — таким образом, ими можно манипулировать, не учитывая их смысл/значение.
                                            0
                                            /*
                                            * это всё вы тоже форичем делаете?
                                            */

                                            Нет. Я это всё ничем не делаю. У меня таких случаев не бывает.
                                      0
                                      Вариант с for можно использовать только в том случае, если действительно все ключи массива $arr расположены в порядке возрастания без пропусков. И об этом не стоит забывать…
                                      $arr = [0 => 'a', 1 => 'b', 3 => 'c'];
                                      $n = count( $arr );
                                      for($k = 0; $k < $n; $k++ ) {...}
                                      
                                        0
                                        Цикл for можно использовать гораздо шире. Даже относительно массивов. И в вашем примере тоже его тоже можно применить, если потребуется.
                                          0
                                          Конечно можно — допустим определить «есть ли дырки». Но в данном случае речь идет о банальном переборе всех элементов массива, а не каких-либо других экзотических обработках массивов.
                                        +5
                                        Надеюсь все тут понимают, что for и foreach совсем разные вещи? for перебирает в порядке следования индексов, foreach — в порядке следования значений. Массив [ 1=>1, 0=>0 ] эти циклы переберут по-разному.

                                        Only users with full accounts can post comments. Log in, please.