[php-src] master: [intl] Size sortWithSortKeys buffers based on array size (#23504)

Author: Ilia Alshanetsky (iliaal)
Committer: GitHub (web-flow)
Pusher: iliaal
Date: 2026-08-30T11:14:46-04:00

Commit: https://github.com/php/php-src/commit/091cb333619644379ac606c38d373c45e7c2c0de
Raw diff: https://github.com/php/php-src/commit/091cb333619644379ac606c38d373c45e7c2c0de.diff

[intl] Size sortWithSortKeys buffers based on array size (#23504)

collator_sort_with_sort_keys() ecalloc'd sortKeyBuf and sortKeyIndxBuf
at DEF_SORT_KEYS_BUF_SIZE (1MiB) each on every call regardless of array
size. sortKeyBuf now starts from zend_hash_num_elements() * 32 bytes,
clamped to a 4KiB minimum and the previous 1MiB cap, and grows
geometrically up to DEF_SORT_KEYS_BUF_INCREMENT. sortKeyIndxBuf is
allocated exactly for the element count, dropping the index-buffer
growth path. Sibling audit: DEF_SORT_KEYS* constants have no other
users and collator_sort()/asort()/get_sort_key() already scale
allocations.

Changed paths:
  A  ext/intl/tests/collator_sort_with_sort_keys_buffer_size.phpt
  M  NEWS
  M  ext/intl/collator/collator_sort.cpp


Diff:

diff --git a/NEWS b/NEWS
index bd17cf9bf8e6..ae8edaf97c9f 100644
--- a/NEWS
+++ b/NEWS
@@ -7,6 +7,8 @@ PHP                                                                        NEWS
     100-continue flow control). (Sjoerd Langkemper)
 
 - Intl:
+  . Fixed Collator::sortWithSortKeys() allocating fixed 2MiB buffers
+    regardless of array size. (Ilia Alshanetsky)
   . Fixed a memory leak when iterating IntlBreakIterator::getPartsIterator()
     results. (iliaal)
   . Fixed a leak in Locale::getKeywords() when a keyword value cannot be
diff --git a/ext/intl/collator/collator_sort.cpp b/ext/intl/collator/collator_sort.cpp
index cb1f2aefc358..f2674b9c8ff8 100644
--- a/ext/intl/collator/collator_sort.cpp
+++ b/ext/intl/collator/collator_sort.cpp
@@ -44,9 +44,8 @@ ZEND_EXTERN_MODULE_GLOBALS( intl )
 
 static const size_t DEF_SORT_KEYS_BUF_SIZE = 1048576;
 static const size_t DEF_SORT_KEYS_BUF_INCREMENT = 1048576;
-
-static const size_t DEF_SORT_KEYS_INDX_BUF_SIZE = 1048576;
-static const size_t DEF_SORT_KEYS_INDX_BUF_INCREMENT = 1048576;
+static const size_t MIN_SORT_KEYS_BUF_SIZE = 4096;
+static const size_t SORT_KEY_LENGTH_ESTIMATE = 32;
 
 static const size_t DEF_UTF16_BUF_SIZE = 1024;
 
@@ -427,17 +426,17 @@ U_CFUNC PHP_FUNCTION( collator_sort_with_sort_keys )
 	zval*       hashData             = nullptr;                     /* currently processed item of input hash */
 
 	char*       sortKeyBuf           = nullptr;                     /* buffer to store sort keys */
-	uint32_t    sortKeyBufSize       = DEF_SORT_KEYS_BUF_SIZE;   /* buffer size */
+	uint32_t    sortKeyBufSize       = 0;                        /* buffer size */
 	ptrdiff_t   sortKeyBufOffset     = 0;                        /* pos in buffer to store sort key */
 	uint32_t    sortKeyLen           = 0;                        /* the length of currently processing key */
 	uint32_t    bufLeft              = 0;
 	uint32_t    bufIncrement         = 0;
 
 	collator_sort_key_index_t* sortKeyIndxBuf = nullptr;            /* buffer to store 'indexes' which will be passed to 'qsort' */
-	uint32_t    sortKeyIndxBufSize   = DEF_SORT_KEYS_INDX_BUF_SIZE;
 	uint32_t    sortKeyIndxSize      = sizeof( collator_sort_key_index_t );
 
 	uint32_t    sortKeyCount         = 0;
+	uint32_t    numElements          = 0;
 	uint32_t    j                    = 0;
 
 	UChar*      utf16_buf            = nullptr;                     /* tmp buffer to hold current processing string in utf-16 */
@@ -472,9 +471,20 @@ U_CFUNC PHP_FUNCTION( collator_sort_with_sort_keys )
 	if( !hash || zend_hash_num_elements( hash ) == 0 )
 		RETURN_TRUE;
 
+	numElements = zend_hash_num_elements( hash );
+
+	if( numElements > DEF_SORT_KEYS_BUF_SIZE / SORT_KEY_LENGTH_ESTIMATE ) {
+		sortKeyBufSize = DEF_SORT_KEYS_BUF_SIZE;
+	} else {
+		sortKeyBufSize = numElements * SORT_KEY_LENGTH_ESTIMATE;
+	}
+	if( sortKeyBufSize < MIN_SORT_KEYS_BUF_SIZE ) {
+		sortKeyBufSize = MIN_SORT_KEYS_BUF_SIZE;
+	}
+
 	/* Create buffers */
-	sortKeyBuf     = reinterpret_cast<char *>(ecalloc( sortKeyBufSize,     sizeof( char    ) ));
-	sortKeyIndxBuf = reinterpret_cast<collator_sort_key_index_t *>(ecalloc( sortKeyIndxBufSize, sizeof( uint8_t ) ));
+	sortKeyBuf     = reinterpret_cast<char *>(ecalloc( sortKeyBufSize, sizeof( char ) ));
+	sortKeyIndxBuf = reinterpret_cast<collator_sort_key_index_t *>(ecalloc( numElements, sortKeyIndxSize ));
 	utf16_buf      = eumalloc( utf16_buf_size );
 
 	/* Iterate through input hash and create a sort key for each value. */
@@ -524,7 +534,15 @@ U_CFUNC PHP_FUNCTION( collator_sort_with_sort_keys )
 		/* check for sortKeyBuf overflow, increasing its size of the buffer if needed */
 		if( sortKeyLen > bufLeft )
 		{
-			bufIncrement = ( sortKeyLen > DEF_SORT_KEYS_BUF_INCREMENT ) ? sortKeyLen : DEF_SORT_KEYS_BUF_INCREMENT;
+			bufIncrement = sortKeyBufSize;
+
+			if( bufIncrement > DEF_SORT_KEYS_BUF_INCREMENT ) {
+				bufIncrement = DEF_SORT_KEYS_BUF_INCREMENT;
+			}
+
+			if( bufIncrement < sortKeyLen ) {
+				bufIncrement = sortKeyLen;
+			}
 
 			sortKeyBufSize += bufIncrement;
 			bufLeft += bufIncrement;
@@ -534,16 +552,6 @@ U_CFUNC PHP_FUNCTION( collator_sort_with_sort_keys )
 			sortKeyLen = ucol_getSortKey( co->ucoll, utf16_buf, utf16_len, (uint8_t*)sortKeyBuf + sortKeyBufOffset, bufLeft );
 		}
 
-		/*  check sortKeyIndxBuf overflow, increasing its size of the buffer if needed */
-		if( ( sortKeyCount + 1 ) * sortKeyIndxSize > sortKeyIndxBufSize )
-		{
-			bufIncrement = ( sortKeyIndxSize > DEF_SORT_KEYS_INDX_BUF_INCREMENT ) ? sortKeyIndxSize : DEF_SORT_KEYS_INDX_BUF_INCREMENT;
-
-			sortKeyIndxBufSize += bufIncrement;
-
-			sortKeyIndxBuf = reinterpret_cast<collator_sort_key_index_t *>(erealloc( sortKeyIndxBuf, sortKeyIndxBufSize ));
-		}
-
 		sortKeyIndxBuf[sortKeyCount].key = (char*)sortKeyBufOffset;    /* remember just offset, cause address */
 		                                                               /* of 'sortKeyBuf' may be changed due to realloc. */
 		sortKeyIndxBuf[sortKeyCount].zstr = hashData;
diff --git a/ext/intl/tests/collator_sort_with_sort_keys_buffer_size.phpt b/ext/intl/tests/collator_sort_with_sort_keys_buffer_size.phpt
new file mode 100644
index 000000000000..ef1d68851e37
--- /dev/null
+++ b/ext/intl/tests/collator_sort_with_sort_keys_buffer_size.phpt
@@ -0,0 +1,57 @@
+--TEST--
+Collator::sortWithSortKeys() buffer allocation scales with array size
+--EXTENSIONS--
+intl
+--FILE--
+<?php
+$c = new Collator('en_US');
+$a = ['bb', 'aa', 'dd', 'cc'];
+$c->sort($a);
+
+$before = memory_get_peak_usage();
+$b = ['bb', 'aa', 'cc', 'ab', 'ca', 'bc', 'ac', 'ba'];
+$c->sortWithSortKeys($b);
+$peakDelta = memory_get_peak_usage() - $before;
+
+var_dump($a);
+var_dump($b);
+var_dump($peakDelta < 100000);
+
+$long = str_repeat('a', 10000);
+$d = [$long . 'b', $long . 'a'];
+$c->sortWithSortKeys($d);
+echo $d[0] === $long . 'a' ? "long-a\n" : "fail-a\n";
+echo $d[1] === $long . 'b' ? "long-b\n" : "fail-b\n";
+?>
+--EXPECT--
+array(4) {
+  [0]=>
+  string(2) "aa"
+  [1]=>
+  string(2) "bb"
+  [2]=>
+  string(2) "cc"
+  [3]=>
+  string(2) "dd"
+}
+array(8) {
+  [0]=>
+  string(2) "aa"
+  [1]=>
+  string(2) "ab"
+  [2]=>
+  string(2) "ac"
+  [3]=>
+  string(2) "ba"
+  [4]=>
+  string(2) "bb"
+  [5]=>
+  string(2) "bc"
+  [6]=>
+  string(2) "ca"
+  [7]=>
+  string(2) "cc"
+}
+bool(true)
+long-a
+long-b