Сравнение производительности перебора массивов в цикле через 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) раз больше чем к целочисленному

Автор: rotor

Источник