Skip to content

PHP array_shift(): Optimize tail move on hole-free packed arrays - #23517

Open
mehmetcansahin wants to merge 1 commit into
php:masterfrom
mehmetcansahin:array-shift-loop
Open

PHP array_shift(): Optimize tail move on hole-free packed arrays#23517
mehmetcansahin wants to merge 1 commit into
php:masterfrom
mehmetcansahin:array-shift-loop

Conversation

@mehmetcansahin

@mehmetcansahin mehmetcansahin commented Aug 30, 2026 •
edited
Loading

Copy link
Copy Markdown
Contributor

For a packed array without holes, removing the first element leaves a contiguous tail. When no iterator is active, array_shift() now moves that tail with a single memmove() instead of testing every slot for IS_UNDEF; a one element tail is moved directly to avoid the call overhead. Packed arrays with holes, arrays with active iterators, and hash arrays keep the existing paths.

Benchmarks

Draining a packed int array ($a = $base; while ($a) array_shift($a);):

n repetitions base this PR speedup
100 20,000 160.5 ms 58.7 ms 2.7×
1,000 2,000 1,075.6 ms 249.9 ms 4.3×
10,000 200 10,726.5 ms 2,602.4 ms 4.1×

Two-element regression check ($a = [0, 1]; array_shift($a); x 100M, exercises the direct-copy specialization): 3.528s → 3.438 s, no tiny-array slowdown observed.

Benchmark scripts

Draining benchmark:

<?php
foreach ([100, 1000, 10000] as $n) {
    $reps = intdiv(2000000, $n);
    $base = range(0, $n - 1);
    $best = PHP_FLOAT_MAX;
    for ($run = 0; $run < 3; $run++) {
        $t = hrtime(true);
        for ($r = 0; $r < $reps; $r++) {
            $a = $base;
            while ($a) array_shift($a);
        }
        $best = min($best, (hrtime(true) - $t) / 1e6);
    }
    printf("n=%-6d drain x%-5d best: %8.1f ms\n", $n, $reps, $best);
}

Two-element regression check:

<?php
$best = PHP_FLOAT_MAX;
for ($run = 0; $run < 3; $run++) {
    $t = hrtime(true);
    for ($i = 0; $i < 100000000; $i++) {
        $a = [0, 1];
        array_shift($a);
    }
    $best = min($best, (hrtime(true) - $t) / 1e9);
}
printf("fresh [0,1] x100M best: %.3f s\n", $best);

@mehmetcansahin

mehmetcansahin commented Aug 31, 2026

Copy link
Copy Markdown
Contributor Author

The FreeBSD failure appears to be an unrelated test flake. Could it be rerun?

@mehmetcansahin
mehmetcansahin marked this pull request as ready for review August 31, 2026 07:20
@mehmetcansahin
mehmetcansahin requested a review from bukka as a code owner August 31, 2026 07:20
@ArtUkrainskiy

ArtUkrainskiy commented Oct 14, 2026

Copy link
Copy Markdown
Contributor

I measured this on master c65321c (7268e32 merges with conflicts in NEWS and UPGRADING only) with GCC 13.3, GCC 14.2, clang 18.1 and clang 20.1 on an i7-13700H, built with the flags of the official Docker image.

Change in CPU cycles per operation with the PR, relative to master (negative = fewer cycles, faster); median of five alternating runs:

call master, CPU cycles per call (GCC 13.3) GCC 13.3 GCC 14.2 clang 18.1 clang 20.1
array_shift() of a fresh copy of [0, 1] 121 −1% −4% −3% −3%
queue of 10: shift one, append one 103 −15% −21% −8% −15%
queue of 100: shift one, append one 467 −70% −69% −66% −70%
queue of 1,000: shift one, append one 3,557 −82% −83% −82% −84%
queue of 10,000: shift one, append one 35,702 −73% −73% −72% −75%
drain a copy of 100 ints with while ($a) array_shift($a) 27,458 −62% −63% −57% −62%
drain a copy of 1,000 ints 1,832,745 −81% −81% −81% −83%
drain a copy of 10,000 ints 181,201,571 −74% −74% −74% −76%
one shift of a fresh copy of 1,000 ints 6,073 −48% −49% −45% −46%
one shift of a fresh copy of 1,000 ints with a hole (old path) 6,646 +2% +1% −1% −6%
one shift of a fresh copy of 100 string keys (hash, old path) 1,394 0% 0% −1% 0%

Draining 100–10,000 ints gets 2.3–6.0× faster here (2.3–2.7× at 100, 5.2–6.0× at 1,000, 3.8–4.1× at 10,000); the description reports 2.7×, 4.3× and 4.1×. A queue of 10,000 gains less than one of 1,000 (−75 … −72% against −84 … −82%) while executing 92–93% fewer instructions (1,000: 90–91%), which is consistent with copy and cache bandwidth becoming the limit when 160 KB move per shift. The paths the PR does not touch (an array with a hole, a hash array) stay at −6 … +2% with instructions within 0.1%, next to −3 … +2% for master against master.

Correctness: every return value and the final array (with references) are the same as master on 500,000 random sequences of shifts, unsets, appends, appended references, shifts of copies, string keys and array_unshift(); on targeted cases the state after every step is compared too (holes at every position before and after compaction), along with the lifetime and destructor order of objects in the tail with a copy-on-write copy, foreach by value and by reference, and a self-referencing array; all with the four compilers and under ASan/UBSan. The harness catches four of five deliberate mutations; the fifth, not clearing the vacated last slot, changes nothing observable: that slot is beyond nNumUsed, and I found nothing that reads slots there before writing them.

No correctness issues found. LGTM.

Full tables, scripts and data: https://github.com/ArtUkrainskiy/php-src-bench/tree/main/reports/pr-23517-array-shift

@mehmetcansahin
PHP array_shift(): Optimize tail move on hole-free packed arrays
79c0bfc 
When a packed array has no holes and no active iterators, the slot
vacated by the shifted element is the only hole, so the tail can be
moved down with a single memmove instead of testing every slot for
IS_UNDEF and comparing source and destination indexes. A tail of a
single element is moved directly instead, avoiding the memmove call
overhead on tiny arrays.
@mehmetcansahin

mehmetcansahin commented Oct 14, 2026 •
edited
Loading

Copy link
Copy Markdown
Contributor Author

Thanks @ArtUkrainskiy for the detailed review!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@bukka bukka Awaiting requested review from bukka bukka is a code owner

Assignees

No one assigned

Labels

Extension: standard

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@mehmetcansahin @ArtUkrainskiy