[PHP-CVS] [php-src] master: Optimize array_intersect() using hash-based matching (#23019)
[email protected] (mehmetcan via GitHub)
| Newsgroups | php.cvs |
|---|---|
| Message-ID | <[email protected]> |
Author: mehmetcan (mehmetcansahin)
Committer: GitHub (web-flow)
Pusher: arnaud-lb
Date: 2026-08-06T13:12:21+02:00
Commit: https://github.com/php/php-src/commit/e9deb0af19c33bf458009c51d0750c981cff3eab
Raw diff: https://github.com/php/php-src/commit/e9deb0af19c33bf458009c51d0750c981cff3eab.diff
Optimize array_intersect() using hash-based matching (#23019)
Changed paths:
A ext/standard/tests/array/array_intersect_empty.phpt
A ext/standard/tests/array/array_intersect_reentrant_holes.phpt
A ext/standard/tests/array/array_intersect_side_effects.phpt
A ext/standard/tests/array/array_intersect_values.phpt
M NEWS
M UPGRADING
M Zend/tests/bug74093.phpt
M Zend/tests/named_params/internal_variadics.phpt
M ext/standard/array.c
M ext/standard/tests/array/array_intersect_variation9.phpt
Diff:
diff --git a/NEWS b/NEWS
index fd4d58dd3c20..a70b2d52d8b0 100644
--- a/NEWS
+++ b/NEWS
@@ -52,6 +52,7 @@ PHP NEWS
. Added the "filter.max_filter_count" stream context option for php://filter
URLs. Using more than 16 filters without configuring this option is now
deprecated. (Sjoerd Langkemper)
+ . Improved performance of array_intersect(). (mehmetcansahin)
. Fixed bug GH-23006 (phpcredits() full-page HTML title says phpinfo()).
(Weilin Du)
. The following functions now raise a ValueError when the $filename argument
diff --git a/UPGRADING b/UPGRADING
index 453bae75701b..d6ed37ef49b6 100644
--- a/UPGRADING
+++ b/UPGRADING
@@ -201,6 +201,14 @@ PHP 8.6 UPGRADE NOTES
SplTempFileObject; the two previously returned different values.
- Standard:
+ . array_intersect() with at least two arrays now converts values to strings
+ while scanning its inputs instead of during sort comparisons. This can
+ change the number and order of conversion warnings and __toString() calls,
+ which conversion exception is reached, and the result for stateful
+ __toString() implementations. Argument types are validated before checking
+ for empty arrays or converting values, so an invalid later argument can
+ suppress conversion side effects from earlier arrays. Values are not
+ converted if any input array is empty.
. Form feed (\f) is now added in the default trimmed characters of trim(),
rtrim() and ltrim().
RFC: https://wiki.php.net/rfc/trim_form_feed
@@ -715,6 +723,7 @@ PHP 8.6 UPGRADE NOTES
- Standard:
. Improved performance of array_fill_keys().
+ . Improved performance of array_intersect().
. Improved performance of array_map() with multiple arrays passed.
. Improved performance of array_sum() and array_product() for
integer-only arrays.
diff --git a/Zend/tests/bug74093.phpt b/Zend/tests/bug74093.phpt
index d38d6e5109c4..fea0d5ea9d03 100644
--- a/Zend/tests/bug74093.phpt
+++ b/Zend/tests/bug74093.phpt
@@ -14,9 +14,10 @@ max_execution_time=1
hard_timeout=1
--FILE--
<?php
-$a1 = range(1, 3000000);
-$a2 = range(100000, 3999999);
-array_intersect($a1, $a2);
+$values = range(1, 6000000);
+/* array_intersect() now uses a linear-time hash implementation. Use a large
+ * internal string sort to retain the hard-timeout workload. */
+sort($values, SORT_STRING);
?>
--EXPECTF--
Fatal error: Maximum execution time of 1+1 seconds exceeded %s
diff --git a/Zend/tests/named_params/internal_variadics.phpt b/Zend/tests/named_params/internal_variadics.phpt
index 8312bde406d2..8ec11ac2c34a 100644
--- a/Zend/tests/named_params/internal_variadics.phpt
+++ b/Zend/tests/named_params/internal_variadics.phpt
@@ -15,6 +15,14 @@ try {
echo $e->getMessage(), "\n";
}
+var_dump(array_intersect(array: [1, 2]) === [1, 2]);
+
+try {
+ array_intersect([1, 2], arrays: [2]);
+} catch (ArgumentCountError $e) {
+ echo $e->getMessage(), "\n";
+}
+
try {
$array = [1, 2];
array_push($array, ...['values' => 3]);
@@ -25,4 +33,6 @@ try {
--EXPECT--
Internal function array_merge() does not accept named variadic arguments
Internal function array_diff_key() does not accept named variadic arguments
+bool(true)
+Internal function array_intersect() does not accept named variadic arguments
Internal function array_push() does not accept named variadic arguments
diff --git a/ext/standard/array.c b/ext/standard/array.c
index fe74e1e7881d..584afada2089 100644
--- a/ext/standard/array.c
+++ b/ext/standard/array.c
@@ -5369,9 +5369,218 @@ PHP_FUNCTION(array_intersect_ukey)
}
/* }}} */
+static zend_always_inline bool php_array_intersect_get_key(
+ zval *value, zend_ulong *num_key, zend_string **str_key, zend_string **tmp_key)
+{
+ ZVAL_DEREF(value);
+ *tmp_key = NULL;
+
+ if (Z_TYPE_P(value) == IS_LONG) {
+ *num_key = (zend_ulong) Z_LVAL_P(value);
+ *str_key = NULL;
+ return true;
+ }
+
+ if (Z_TYPE_P(value) == IS_STRING) {
+ *str_key = Z_STR_P(value);
+ return true;
+ }
+
+ *str_key = zval_try_get_tmp_string(value, tmp_key);
+ return *str_key != NULL;
+}
+
+static zend_always_inline void php_array_intersect_empty_result(zval *first, zval *return_value)
+{
+ HashTable *result;
+ bool in_place = zend_may_modify_arg_in_place(first);
+
+ if (in_place) {
+ result = Z_ARRVAL_P(first);
+ ZVAL_ARR(return_value, result);
+ } else {
+ result = zend_array_dup(Z_ARRVAL_P(first));
+ ZVAL_ARR(return_value, result);
+ }
+
+ ZEND_HASH_FOREACH_KEY(result, zend_ulong num_key, zend_string *key) {
+ if (key) {
+ zend_hash_del(result, key);
+ } else {
+ zend_hash_index_del(result, num_key);
+ }
+ } ZEND_HASH_FOREACH_END();
+
+ if (in_place) {
+ Z_ADDREF_P(return_value);
+ }
+}
+
+/* {{{ Hash-based implementation of array_intersect(). Values are compared
+ * using their string representation. On the long|string domain, this is
+ * exactly key equality under symtable normalization: a long and a string
+ * compare equal iff the string is the canonical decimal representation of the
+ * long, which is precisely when ZEND_HANDLE_NUMERIC converts it to that long
+ * key. Other values are converted to string before the same normalization. */
+static zend_never_inline void php_array_intersect_hash(zval *args, uint32_t argc, zval *return_value)
+{
+ for (uint32_t i = 0; i < argc; i++) {
+ if (Z_TYPE(args[i]) != IS_ARRAY) {
+ zend_argument_type_error(i + 1, "must be of type array, %s given", zend_zval_value_name(&args[i]));
+ return;
+ }
+ }
+
+ /* An empty argument makes the intersection empty, so no values need to be
+ * converted to string. */
+ for (uint32_t i = 0; i < argc; i++) {
+ if (zend_hash_num_elements(Z_ARRVAL(args[i])) == 0) {
+ php_array_intersect_empty_result(&args[0], return_value);
+ return;
+ }
+ }
+
+ /* Map each value of args[1] to the number of consecutive arguments,
+ * starting from args[1], the value has been seen in. */
+ zval one;
+ ZVAL_LONG(&one, 1);
+ HashTable set;
+ zend_hash_init(&set, zend_hash_num_elements(Z_ARRVAL(args[1])), NULL, NULL, 0);
+ zend_bitset delete_bitset = NULL;
+ ALLOCA_FLAG(use_heap);
+ bool in_place = false;
+
+ ZEND_HASH_FOREACH_VAL(Z_ARRVAL(args[1]), zval *value) {
+ zend_ulong value_num_key = 0;
+ zend_string *value_str_key, *tmp_key;
+ if (!php_array_intersect_get_key(value, &value_num_key, &value_str_key, &tmp_key)) {
+ goto cleanup;
+ }
+ if (value_str_key) {
+ zend_symtable_update(&set, value_str_key, &one);
+ } else {
+ zend_hash_index_update(&set, value_num_key, &one);
+ }
+ zend_tmp_string_release(tmp_key);
+ } ZEND_HASH_FOREACH_END();
+
+ for (uint32_t i = 2; i < argc; i++) {
+ ZEND_HASH_FOREACH_VAL(Z_ARRVAL(args[i]), zval *value) {
+ zend_ulong value_num_key = 0;
+ zend_string *value_str_key, *tmp_key;
+ if (!php_array_intersect_get_key(value, &value_num_key, &value_str_key, &tmp_key)) {
+ goto cleanup;
+ }
+ zval *count;
+ if (value_str_key) {
+ count = zend_symtable_find(&set, value_str_key);
+ } else {
+ count = zend_hash_index_find(&set, value_num_key);
+ }
+ zend_tmp_string_release(tmp_key);
+ if (count && Z_LVAL_P(count) == (zend_long) i - 1) {
+ ZVAL_LONG(count, i);
+ }
+ } ZEND_HASH_FOREACH_END();
+ }
+
+ /* Match the generic path by filtering the first argument in place if
+ * possible and duplicating it otherwise. In particular, duplication keeps
+ * bucket holes whose positions are observable through array_rand(). */
+ HashTable *result;
+ in_place = zend_may_modify_arg_in_place(&args[0]);
+ if (in_place) {
+ result = Z_ARRVAL(args[0]);
+ ZVAL_ARR(return_value, result);
+ } else {
+ result = zend_array_dup(Z_ARRVAL(args[0]));
+ ZVAL_ARR(return_value, result);
+ }
+
+ /* Determine all entries to remove before deleting any. Deleting an entry may
+ * invoke a user destructor that changes subsequent string conversions. */
+ HashTable *scanned_result = result;
+ uint32_t scanned_num_used = result->nNumUsed;
+ uint32_t delete_bitset_len = zend_bitset_len(scanned_num_used);
+ delete_bitset = ZEND_BITSET_ALLOCA(delete_bitset_len, use_heap);
+ zend_bitset_clear(delete_bitset, delete_bitset_len);
+
+ size_t scanned_element_size = ZEND_HASH_ELEMENT_SIZE(scanned_result);
+ for (uint32_t result_idx = 0; result_idx < scanned_num_used; result_idx++) {
+ zval *entry = ZEND_HASH_ELEMENT_EX(scanned_result, result_idx, scanned_element_size);
+ if (UNEXPECTED(Z_TYPE_P(entry) == IS_UNDEF)) {
+ continue;
+ }
+ zend_ulong value_num_key = 0;
+ zend_string *value_str_key, *tmp_key;
+ if (!php_array_intersect_get_key(entry, &value_num_key, &value_str_key, &tmp_key)) {
+ goto cleanup;
+ }
+ zval *count;
+ if (value_str_key) {
+ count = zend_symtable_find(&set, value_str_key);
+ } else {
+ count = zend_hash_index_find(&set, value_num_key);
+ }
+ zend_tmp_string_release(tmp_key);
+ if (!count || Z_LVAL_P(count) != (zend_long) argc - 1) {
+ zend_bitset_incl(delete_bitset, result_idx);
+ }
+ }
+
+ /* A conversion may retain the first argument through reentrant user code,
+ * so it may no longer be safe to modify the original array in place. */
+ if (in_place && !zend_may_modify_arg_in_place(&args[0])) {
+ result = zend_array_dup(Z_ARRVAL(args[0]));
+ ZVAL_ARR(return_value, result);
+ in_place = false;
+ }
+
+ /* The late duplication may compact holes, so read keys from the table whose
+ * bucket indexes are stored in the bitset. */
+ uint32_t result_idx;
+ ZEND_BITSET_FOREACH(delete_bitset, delete_bitset_len, result_idx) {
+ if (HT_IS_PACKED(scanned_result)) {
+ zend_hash_index_del(result, result_idx);
+ } else {
+ zval *entry = ZEND_HASH_ELEMENT_EX(scanned_result, result_idx, scanned_element_size);
+ Bucket *bucket = (Bucket *) entry;
+ if (bucket->key) {
+ zend_hash_del(result, bucket->key);
+ } else {
+ zend_hash_index_del(result, bucket->h);
+ }
+ }
+ } ZEND_BITSET_FOREACH_END();
+
+cleanup:
+ if (delete_bitset) {
+ free_alloca(delete_bitset, use_heap);
+ }
+ zend_hash_destroy(&set);
+ if (in_place) {
+ Z_ADDREF_P(return_value);
+ }
+}
+/* }}} */
+
/* {{{ Returns the entries of arr1 that have values which are present in all the other arguments */
PHP_FUNCTION(array_intersect)
{
+ zval *args;
+ uint32_t argc;
+
+ if (zend_parse_parameters(ZEND_NUM_ARGS(), "+", &args, &argc) == FAILURE) {
+ RETURN_THROWS();
+ }
+
+ if (argc >= 2) {
+ php_array_intersect_hash(args, argc, return_value);
+ return;
+ }
+
+ /* Preserve the generic path and its conversion side effects for calls with
+ * a single array. */
php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_NORMAL, INTERSECT_COMP_DATA_INTERNAL, INTERSECT_COMP_KEY_INTERNAL);
}
/* }}} */
diff --git a/ext/standard/tests/array/array_intersect_empty.phpt b/ext/standard/tests/array/array_intersect_empty.phpt
new file mode 100644
index 000000000000..1bf527a42694
--- /dev/null
+++ b/ext/standard/tests/array/array_intersect_empty.phpt
@@ -0,0 +1,55 @@
+--TEST--
+array_intersect() does not convert values when an argument is empty
+--FILE--
+<?php
+class ThrowingStringableValue {
+ public function __toString(): string {
+ throw new RuntimeException('conversion failed');
+ }
+}
+
+set_error_handler(static function (int $code, string $message): never {
+ throw new ErrorException($message, $code);
+});
+
+$cases = [
+ static fn() => array_intersect([], [[1]]),
+ static fn() => array_intersect([[1]], []),
+ static fn() => array_intersect([new ThrowingStringableValue()], ['value'], []),
+ static fn() => array_intersect([], [new stdClass()]),
+];
+
+foreach ($cases as $case) {
+ try {
+ var_dump($case());
+ } catch (Throwable $e) {
+ echo $e::class, ': ', $e->getMessage(), "\n";
+ }
+}
+
+restore_error_handler();
+
+$result = array_intersect([9 => 'value'], []);
+$result[] = 'appended';
+var_dump(array_keys($result));
+
+try {
+ array_intersect([], [], new stdClass());
+} catch (TypeError $e) {
+ echo $e->getMessage(), "\n";
+}
+?>
+--EXPECT--
+array(0) {
+}
+array(0) {
+}
+array(0) {
+}
+array(0) {
+}
+array(1) {
+ [0]=>
+ int(10)
+}
+array_intersect(): Argument #3 must be of type array, stdClass given
diff --git a/ext/standard/tests/array/array_intersect_reentrant_holes.phpt b/ext/standard/tests/array/array_intersect_reentrant_holes.phpt
new file mode 100644
index 000000000000..8a1d0968dda3
--- /dev/null
+++ b/ext/standard/tests/array/array_intersect_reentrant_holes.phpt
@@ -0,0 +1,37 @@
+--TEST--
+array_intersect() preserves element selection when conversion retains a hash table with holes
+--FILE--
+<?php
+class CapturingStringableWithHole {
+ public static array $argument;
+
+ public function __toString(): string {
+ self::$argument = debug_backtrace()[1]['args'][0];
+ return 'drop';
+ }
+}
+
+function temporary_argument_with_hole(): array {
+ $array = [
+ 'hole' => null,
+ 'drop' => new CapturingStringableWithHole(),
+ 'keep' => 'keep',
+ ];
+ unset($array['hole']);
+ return $array;
+}
+
+$result = array_intersect(temporary_argument_with_hole(), ['keep']);
+var_dump(array_keys($result), array_keys(CapturingStringableWithHole::$argument));
+?>
+--EXPECT--
+array(1) {
+ [0]=>
+ string(4) "keep"
+}
+array(2) {
+ [0]=>
+ string(4) "drop"
+ [1]=>
+ string(4) "keep"
+}
diff --git a/ext/standard/tests/array/array_intersect_side_effects.phpt b/ext/standard/tests/array/array_intersect_side_effects.phpt
new file mode 100644
index 000000000000..00cacb9b4a39
--- /dev/null
+++ b/ext/standard/tests/array/array_intersect_side_effects.phpt
@@ -0,0 +1,70 @@
+--TEST--
+array_intersect() conversion side effects and argument validation
+--FILE--
+<?php
+ini_set('precision', '14');
+
+class StringableWithStatefulDestructor {
+ public function __toString(): string {
+ return 'unmatched';
+ }
+
+ public function __destruct() {
+ ini_set('precision', '3');
+ }
+}
+
+function temporary_values(): array {
+ return [new StringableWithStatefulDestructor(), 1.234567];
+}
+
+var_dump(array_intersect(temporary_values(), ['1.234567']));
+
+class CapturingStringableValue {
+ public static array $argument;
+
+ public function __toString(): string {
+ self::$argument = debug_backtrace()[1]['args'][0];
+ return 'drop';
+ }
+}
+
+function temporary_argument(): array {
+ return [
+ 'drop' => new CapturingStringableValue(),
+ 'keep' => 'keep',
+ ];
+}
+
+$result = array_intersect(temporary_argument(), ['keep']);
+var_dump(array_keys($result), array_keys(CapturingStringableValue::$argument));
+
+set_error_handler(static function (int $code, string $message): bool {
+ echo $message, "\n";
+ return true;
+});
+
+try {
+ array_intersect([[1], [2]], ['Array'], new stdClass());
+} catch (TypeError $e) {
+ echo $e->getMessage(), "\n";
+}
+
+restore_error_handler();
+?>
+--EXPECT--
+array(1) {
+ [1]=>
+ float(1.234567)
+}
+array(1) {
+ [0]=>
+ string(4) "keep"
+}
+array(2) {
+ [0]=>
+ string(4) "drop"
+ [1]=>
+ string(4) "keep"
+}
+array_intersect(): Argument #3 must be of type array, stdClass given
diff --git a/ext/standard/tests/array/array_intersect_values.phpt b/ext/standard/tests/array/array_intersect_values.phpt
new file mode 100644
index 000000000000..caac782346b0
--- /dev/null
+++ b/ext/standard/tests/array/array_intersect_values.phpt
@@ -0,0 +1,103 @@
+--TEST--
+array_intersect() with all value types
+--FILE--
+<?php
+function dump_array(array $value): void {
+ echo json_encode($value), "\n";
+}
+
+dump_array(array_intersect(
+ ['first' => 1, 'duplicate' => 1, 'leading' => '01', 'plus' => '+1', 'exponent' => '1e0', 'zero' => 0, 'negative-zero' => '-0'],
+ ['1', '0'],
+));
+
+dump_array(array_intersect([1, 2, '2', 3], [1, 2, 2, '2', 3], [2, '2', 3]));
+
+$aboveMax = PHP_INT_SIZE === 8 ? "9223372036854775808" : "2147483648";
+$belowMin = PHP_INT_SIZE === 8 ? "-9223372036854775809" : "-2147483649";
+var_dump(
+ array_intersect([PHP_INT_MAX, PHP_INT_MIN], [(string) PHP_INT_MAX, (string) PHP_INT_MIN]) === [PHP_INT_MAX, PHP_INT_MIN],
+ array_intersect([PHP_INT_MAX, PHP_INT_MIN], [$aboveMax, $belowMin]) === [],
+ array_intersect([$aboveMax, $belowMin], [$aboveMax, $belowMin]) === [$aboveMax, $belowMin],
+);
+
+$integer = 2;
+$string = '2';
+$result = array_intersect([&$integer, 3], [&$string, 3]);
+$integer = 9;
+var_dump($result[0]);
+
+$array = [0 => 'drop', 100 => 'x', 200 => 'y'];
+$result = array_intersect($array, ['x', 'y']);
+$expected = $array;
+unset($expected[0]);
+mt_srand(0);
+$resultRandom = [array_rand($result), mt_rand()];
+mt_srand(0);
+$expectedRandom = [array_rand($expected), mt_rand()];
+var_dump($result === $expected, $resultRandom === $expectedRandom);
+
+class StringableValue {
+ public function __construct(private string $value) {}
+ public function __toString(): string { return $this->value; }
+}
+
+$resource = fopen('php://memory', 'r');
+$result = array_intersect(
+ [
+ 'null' => null,
+ 'false' => false,
+ 'true' => true,
+ 'zero-float' => 0.0,
+ 'float' => 1.5,
+ 'resource' => $resource,
+ 'object' => new StringableValue('object'),
+ ],
+ ['', '1', '0', '1.5', (string) $resource, 'object'],
+ [false, true, 0, '1.5', $resource, new StringableValue('object')],
+);
+echo implode(',', array_keys($result)), "\n";
+
+var_dump(@array_intersect([[1]], [[2]]) === [[1]]);
+
+class ThrowingStringableValue {
+ public function __toString(): string { throw new RuntimeException('conversion failed'); }
+}
+
+try {
+ array_intersect(['value'], [new ThrowingStringableValue(), 'value']);
+} catch (RuntimeException $e) {
+ echo $e->getMessage(), "\n";
+}
+
+try {
+ array_intersect([''], [new stdClass()]);
+} catch (Error $e) {
+ echo $e->getMessage(), "\n";
+}
+
+set_error_handler(static function (int $code, string $message): never {
+ throw new ErrorException($message, $code);
+});
+try {
+ array_intersect([[1]], [[2]]);
+} catch (ErrorException $e) {
+ echo $e->getMessage(), "\n";
+} finally {
+ restore_error_handler();
+}
+?>
+--EXPECT--
+{"first":1,"duplicate":1,"zero":0}
+{"1":2,"2":"2","3":3}
+bool(true)
+bool(true)
+bool(true)
+int(9)
+bool(true)
+bool(true)
+null,false,true,zero-float,float,resource,object
+bool(true)
+conversion failed
+Object of class stdClass could not be converted to string
+Array to string conversion
diff --git a/ext/standard/tests/array/array_intersect_variation9.phpt b/ext/standard/tests/array/array_intersect_variation9.phpt
index c73b0f3dc925..05588e85e595 100644
--- a/ext/standard/tests/array/array_intersect_variation9.phpt
+++ b/ext/standard/tests/array/array_intersect_variation9.phpt
@@ -66,26 +66,6 @@ Warning: Array to string conversion in %s on line %d
Warning: Array to string conversion in %s on line %d
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
Warning: Array to string conversion in %s on line %d
array(4) {
[0]=>
@@ -149,34 +129,6 @@ Warning: Array to string conversion in %s on line %d
Warning: Array to string conversion in %s on line %d
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
-Warning: Array to string conversion in %s on line %d
-
Warning: Array to string conversion in %s on line %d
array(4) {
[0]=>