[php-src] PR #23585: ext/standard: Optimize sort() and rsort() for large packed integer arrays

Pull Request: https://github.com/php/php-src/pull/23585 Author: LamentXU123 After the last trivial one-element optimization I get to familiar with how sort works in Zend. So, now, except the array is empty or only has one element, we convert arrays to mixed storage before sorting, and convert them back after we sort them. The reason we are doing this is because the internal sorting functions is using Buckets, so we can preserve the keys when sorting the values. Packed arrays (most cases we are sorting them instead of unpacked and mixed arrays), are sequence zvals, and don't have customized keys. This let me thinking. Can we just implement a sort internally which completely works with zvals and not Buckets? So we don't need to convert them to Bucket and convert them back again when sorting packed arrays that don't have external keys at all? I have a idea to implement a sort works with integer arrays entirely depending on zvals. There it is. I set a threshold to use this new internal function instead of the original one when the array to be sorted is large (>= 64 elements), packed and contains fully int. This is because sort functions with fully int arrays is easy to implement (I don't need to consider user's fallback function etc.) and since we are now not doing creating new Buckets and destroying them the benefits mainly comes from larger arrays, both in the aspect of time and memory spaces. Tho the idea is not completed yet (we only imeplement the case for fully int arrays) but this there are already impressive improvements on the case. And sorting an int array with >= 64 elements is quite common in the real world. I ran benchmarks on a 64-elements, fully int array. Also, somehow this is also way more faster when we are sorting on a already sorted array, which is like a bonus. Benchmark: | Case | Baseline batch | Candidate batch | Time change | Candidate faster pairs | |---|---:|---:|---:|---:| | Random integers, sort() | 178.99 ms | 149.92 ms | -16.24% | 11/21 | | Random integers, rsort() | 235.23 ms | 127.49 ms | -45.80% | 21/21 | | Already sorted integers, sort() | 66.86 ms | 30.15 ms | -54.91% | 21/21 | And this is the results with a 1,000,000 element array FYI. | Case | Baseline | Candidate | Time change | |---|---:|---:|---:| | Random integers, sort() | 355.47 ms | 226.61 ms | -36.25% | | Random integers, rsort() | 542.42 ms | 187.24 ms | -65.48% | | Already sorted integers, sort() | 162.24 ms | 58.58 ms | -63.89% | | Random integers with COW, sort() | 355.48 ms | 287.87 ms | -19.02% |