Сравнение производительности перебора массивов в цикле через 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(n²), если бы при поиске значения по индексу перебиралась бы вся хэш таблица. На самом деле, перебираются не все значения, а только часть их, поэтому сложность будет варьироваться от O(n) до O(n²). И для больших массивов, она будет ближе к, O(n). Но даже в этом случае, перебор массива с доступом по ключу — более ресурсоемкая операция.

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