[mehmetcansahin]

array_diff() currently builds its exclusion set from string representations, causing avoidable conversions for large integer-only inputs. This adds a collision-safe fast path using a bitset for compact integer ranges; mixed or sparse inputs continue through the existing path.

$a = range(0, 200000);
$b = range(100000, 300000);

$start = microtime(true);
for ($i = 0; $i < 10; $i++) {
    array_diff($a, $b);
}
printf("%.3fs\n", microtime(true) - $start);

Result: ~0.12s before, ~0.015s after (approximately 8x faster). Unlike the earlier integer-keyed HashTable approach, this retains linear worst-case behavior.

Tests cover integer limits, duplicates, key and reference preservation, and fallback behavior.

[ArtUkrainskiy]

I measured this on master c65321c (b5a4a7f merges with a conflict in 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 call 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
range(0, 200000) minus range(100000, 300000) (the description's example)	50,869,022	−88%	−88%	−87%	−88%
10 ints minus 10 ints (values 1–30)	1,563	−75%	−74%	−71%	−73%
100 ints minus 100 ints (values 1–300)	19,536	−82%	−82%	−82%	−83%
1,000 ints minus 1,000 ints (values 1–3,000)	239,935	−86%	−85%	−86%	−87%
1,000 ints minus three arrays of 300 ints	225,205	−85%	−85%	−86%	−86%
1,000 ints minus 1,000 ints, values up to 10⁹ (falls back)	243,475	0%	+1%	+1%	+2%
1,000 ints minus 999 dense ints and one far value (falls back after the scan)	240,022	+2%	+3%	+3%	+4%
1,000 ints minus 999 ints and one string (falls back after the scan)	240,918	0%	+4%	+3%	+3%
999 ints and one string minus 1,000 ints (falls back after the scan)	241,631	0%	+2%	+1%	0%
1,000 strings minus 1,000 strings (falls back at once)	75,019	0%	+2%	0%	−2%
10 strings minus 10 strings (falls back at once)	657	+1%	+3%	+7%	+1%

Ints that fit the bitset take 71–88% fewer cycles; the example from the description takes 7.9–8.2× fewer, as reported.

Calls that do not take the bitset path pay for the check first. When the first value is not an int, the call to php_array_diff_long() (zend_never_inline; with GCC 13.3 it saves and restores six registers) and the type check add 41–47 instructions: +1 … +7% cycles on 10 strings. Otherwise the arrays are scanned up to the value that rules the bitset out, about 10 instructions per value of the first array and 22–25 per exclusion value: 0 … +4% cycles and +1 … +5% instructions on 1,000 values. Master against master in the same series gives −1 … +1%.

I tried two changes on top of the PR (diffs): checking the type of the first value of the first array inline in array_diff() before the call, and then also scanning the exclusion arrays before the first array. Extra instructions per call relative to master, lowest and highest over the four compilers (second series, same machine):

call	PR	PR + inline first-value check	PR + inline check + exclusions first
10 strings minus 10 strings	+41 … +48	+14 … +20	+14 … +19
1,000 strings minus 1,000 strings	+69 … +100	−40 … +89	−78 … +28
1,000 ints minus 1,000 ints, values up to 10⁹	+9,900 … +10,100	+9,900 … +11,100	−110 … +1,100
1,000 ints minus 999 dense ints and one far value	+32,000 … +35,100	+32,500 … +35,000	+22,000 … +24,900
1,000 ints minus 999 ints and one string	+31,800 … +35,200	+32,200 … +35,100	+22,100 … +25,300
999 ints and one string minus 1,000 ints	+9,800 … +9,900	+9,600 … +10,900	+32,000 … +35,100

• The inline check cuts the cost for arrays that start with a non-int from 41–48 to 14–20 instructions.
• Scanning the exclusions first makes sparse ints fall back after two values and saves the first-array scan when an exclusion is far or not an int, but an int array with a non-int at the end of the first array then pays for the exclusion scan as well. Which case is more common I can't judge. With GCC 14.2 both variants add about 1,000 more instructions to these fallbacks.
• Neither change affects the bitset path (the int rows stay within 2 points of the PR). In cycles, the 1,000-value fallbacks stay between −3% and +4% for all three; 10 strings on clang 18.1 stay at +5 … +8% for all three, which the instruction count does not explain, and I did not look further.

Correctness: the result with its keys, references and refcounts (debug_zval_dump()) is the same as master on 200,000 random calls, 37% of them on the new path, and on targeted cases: exclusion spans just below and above 8 × count for 2–1,000 values, PHP_INT_MIN/PHP_INT_MAX and spans that would overflow, string keys, references and duplicates, int-like strings, floats, bools, null and objects mixed in; with all four compilers and under ASan/UBSan. The harness catches six deliberate mutations (no out-of-range check, the minimum never updated, no addref, string keys dropped, the first array's types not checked, references not dereferenced). Both variants above give the same output with all four compilers (not run under ASan).

Tests: every case in array_diff_long_values.phpt that reaches the new path uses a range of at most 4 values, so a bitset of more than one 64-bit word is never built there (elsewhere ext/random/tests/03_randomizer/methods/pickArrayKeys.phpt builds one, through array_diff() on random keys). A case such as 100 exclusion ints spread over 0–700 would cover it.

No correctness issues found. Before this is merged, could you look at the cost for calls that fall back, at least the inline first-value check? I can send either change as a PR to your branch.

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

[mehmetcansahin]

Thanks! Rebased and pushed both variants, a multi-word bitset test, ZEND_BITSET_ALLOCA for the bitset, and a NEWS entry.