[php-src] PR #24475: array_unshift(): Shift packed arrays in place
| From: | mehmetcansahin | Date: | Wed, 21 Oct 2026 10:26:50 +0000 |
| Subject: | [php-src] PR #24475: array_unshift(): Shift packed arrays in place | ||
| Groups: | php.git-pulls | ||
| Request: | Send a blank email to git-pulls+get-39653@lists.php.net to get a copy of this message | ||
Pull Request: https://github.com/php/php-src/pull/24475
Author: mehmetcansahin
This PR speeds up
array_unshift() on packed arrays by shifting values in place with
memmove() instead of allocating and rebuilding the table. The fast path applies when
there are no holes or active iterators and rebuilding would use the same table size. Other paths,
including table growth and shrinking, are unchanged.
### Benchmarks
Prepending one value on Apple M1, release/NTS build (php -n), using the median of seven
runs per build, alternating base and PR:
| input | base ns/op | this PR ns/op | change |
|---|---:|---:|---:|
| packed, n=7 | 45.4 | 35.1 | -22.8% |
| packed, n=1,000 | 496.9 | 245.1 | -50.7% |
| packed, n=100,000 | 158,820.8 | 29,289.2 | -81.6% |
| copy of packed, n=1,000 | 1,640.6 | 1,377.7 | -16.0% |
| string keys, n=1,000 (old path) | 10,220.4 | 10,274.7 | +0.5% |
Tested with the array suite on release and debug ASan/UBSan builds.
<details>
<summary>Benchmark script and methodology</summary>
Base 1c9242e7fec, this PR a667208a4da; Apple clang 21, -O2
-DNDEBUG, OPcache off. Each process calibrates to at least 60 ms and reports the lowest
average time over five batches. Packed cases include the array_pop() calls that keep
the size constant; copy cases include copy-on-write separation. Negative change means faster.
Run as php -n bench.php '<case>' 60000000.
```php
<?php
function steady(int $n, int $k): Closure {
return function (int $reps) use ($n, $k): int {
$a = range(1, $n);
$vals = range(-$k, -1);
for ($r = 0; $r < $reps; $r++) {
array_unshift($a, ...$vals);
for ($j = 0; $j < $k; $j++) array_pop($a);
}
return count($a);
};
}
function copyThen(array $src): Closure {
return function (int $reps) use ($src): int {
for ($r = 0; $r < $reps; $r++) {
$b = $src;
array_unshift($b, 0);
}
return count($b);
};
}
$hash = [];
for ($i = 0; $i < 1000; $i++) $hash["k$i"] = $i;
$cases = [
'packed, 7 elements, 1 value' => steady(7, 1),
'packed, 1,000 elements, 1 value' => steady(1000, 1),
'packed, 100,000 elements, 1 value' => steady(100000, 1),
'copy of packed, 1,000 elements, 1 value' => copyThen(range(1, 1000)),
'copy of string keys, 1,000 elements, 1 value' => copyThen($hash),
];
$run = $cases[$argv[1]];
$target = (int) $argv[2];
$reps = 1;
do {
$t = hrtime(true);
$run($reps);
$d = hrtime(true) - $t;
if ($d >= $target) break;
$reps *= 2;
} while (true);
$best = PHP_FLOAT_MAX;
for ($i = 0; $i < 5; $i++) {
$t = hrtime(true);
$run($reps);
$best = min($best, (hrtime(true) - $t) / $reps);
}
echo json_encode(['ns' => $best]), "\n";
```
</details>