Время вставки массива

Question

Время вставки массива

Во время глубокого изучения структуры hash и zval и того, как на ней основаны массивы, возникло странное время вставки.

Вот пример:

$array = array();
$someValueToInsert = 100;
for ($i = 0; $i < 10000; ++$i) {
$time = microtime(true);
array_push($array, $someValueToInsert);
echo $i . " : " . (int)((microtime(true) - $time) * 100000000) . "</br>";
}

Итак, я обнаружил, что каждый 1024, 2024, 4048… элемент будет вставлен, используя гораздо больше времени (> ~ x10).

Это не зависит, буду ли я использовать array_push, array_unshiftили просто $array[] = someValueToInsert,

Я думаю об этом в структуре Hash:

typedef struct _hashtable {
...
uint nNumOfElements;
...
} HashTable;

nNumOfElements имеет значение по умолчанию max, но это не ответ, почему для вставки в специальные счетчики потребовалось больше времени (1024, 2048 …).

Какие-нибудь мысли ?

4

arrays hashtable php

Решение

Другие решения

Я думаю, что это связано с реализацией динамических массивов.
Смотрите здесь «Геометрическое расширение и амортизированная стоимость» http://en.wikipedia.org/wiki/Dynamic_array

To avoid incurring the cost of resizing many times, dynamic arrays resize by a large amount, **such as doubling in size**, and use the reserved space for future expansion

Вы также можете прочитать о массивах в PHP здесь https://nikic.github.io/2011/12/12/How-big-are-PHP-arrays-really-Hint-BIG.html

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

capacity = capacity * 2; // doubles the capacity of the array

3

Источник

Accepted Answer

Хотя я бы посоветовал дважды проверить свой ответ в списке внутренних элементов PHP, я считаю, что ответ лежит в zend_hash_do_resize (). Когда в хеш-таблице требуется больше элементов, вызывается эта функция, а существующая хеш-таблица увеличивается в два раза. Поскольку таблица начинает жизнь в 1024, это удвоение объясняет результаты, которые вы наблюдали. Код:

} else if (ht->nTableSize < HT_MAX_SIZE) {  /* Let's double the table size */
void *old_data = HT_GET_DATA_ADDR(ht);
Bucket *old_buckets = ht->arData;

HANDLE_BLOCK_INTERRUPTIONS();
ht->nTableSize += ht->nTableSize;
ht->nTableMask = -ht->nTableSize;
HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), ht->u.flags & HASH_FLAG_PERSISTENT));
memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
pefree(old_data, ht->u.flags & HASH_FLAG_PERSISTENT);
zend_hash_rehash(ht);
HANDLE_UNBLOCK_INTERRUPTIONS();

Я не уверен, является ли remalloc ударом по производительности, или перефразировка является ударом, или тот факт, что весь блок является непрерывным. Было бы интересно поставить на него профилировщик. Я думаю, что некоторые, возможно, уже сделали это для PHP 7.

Примечание, Поток Сейф версия делает вещи по-другому. Я не слишком знаком с этим кодом, поэтому может возникнуть другая проблема, если вы используете ZTS.

3