Insert Array Insertion Time

Question

During an in-depth study of the structure of hashes and zval and how arrays are based on it, they encountered strange insertion times.

Here is an example:

$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>";
}

So, I found that each element 1024, 2024, 4048... will be inserted using a much longer time (> ~ x10).

It does not depend on use array_push, array_unshiftor simply $array[] = someValueToInsert.

I think about this in the Hash framework:

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

nNumOfElements has a maximum value by default, but this is not the answer why it took more time to insert into special counters (1024, 2048 ...).

Any thoughts?

Answer 1

PHP, , zend_hash_do_resize(). - , , - . 1024, , . :

} else if (ht->nTableSize < HT_MAX_SIZE) {  /* Let 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.

, Thread Safe -. , , ZTS.

Answer 2

, . . " " 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.imtqy.com/2011/12/12/How-big-are-PHP-arrays-really-Hint-BIG.html

. . ++,

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