Faster zend sorting implementation

Hey:

 I was working on zend_qsort improvement. but I got a problem need

to be disscussed with you fist..
first

 as we know,  previously zend_qsort is not a stable sorting algo.

 my draft patch (which already get 0.1% IRs reduce in wordpress)

is kindof a stable sorting algo, you can find it here
(https://github.com/laruence/php-src/compare/zend_sort)

 so, there is a bc break, like for :

 $array = array("o",  "O");
 sort($array, SORT_STRING|SORT_FLAG_CASE);

 var_dump($array);

 previously implementation does the swap:

array(2) {
[0]=>
string(1) "O"
[1]=>
string(1) "o"
}

 but new implementation doesn't not:

does not

array(2) {
[0]=>
string(1) "o"
[1]=>
string(1) "O"
}

do you think such BC break is acceptable? or I still need a RFC? :<

thanks

Xinchen Hui
@Laruence
http://www.laruence.com/

--
Xinchen Hui
@Laruence
http://www.laruence.com/

This sounds reasonable, because given how the sort is not stable, there will be other cases (totally made up, but let's say ["a", "o", "O"]) where the swap does not happen. Consistency, and thus a stable sort, is better.

But you're saying your patch is "kind of a" stable sorting algo, so is it stable only sometimes, or did you mean to say "a kind of"?

David

Hey:

I was working on zend_qsort improvement. but I got a problem need

to be disscussed with you fist..

as we know,  previously zend_qsort is not a stable sorting algo.

my draft patch (which already get 0.1% IRs reduce in wordpress)

is kindof a stable sorting algo, you can find it here
(https://github.com/laruence/php-src/compare/zend_sort)

so, there is a bc break, like for :

$array = array("o",  "O");
sort($array, SORT_STRING|SORT_FLAG_CASE);

var_dump($array);

previously implementation does the swap:

array(2) {
[0]=>
string(1) "O"
[1]=>
string(1) "o"
}

but new implementation doesn't not:

array(2) {
[0]=>
string(1) "o"
[1]=>
string(1) "O"
}

do you think such BC break is acceptable? or I still need a RFC? :<

thanks

Xinchen Hui
@Laruence
http://www.laruence.com/

hi :)

Hey:

 I was working on zend_qsort improvement. but I got a problem need

to be disscussed with you fist..

 as we know,  previously zend_qsort is not a stable sorting algo.

 my draft patch (which already get 0.1% IRs reduce in wordpress)

is kindof a stable sorting algo, you can find it here
(https://github.com/laruence/php-src/compare/zend_sort)

 so, there is a bc break, like for :

 $array = array("o",  "O");
 sort($array, SORT_STRING|SORT_FLAG_CASE);

 var_dump($array);

 previously implementation does the swap:

array(2) {
[0]=>
string(1) "O"
[1]=>
string(1) "o"
}

 but new implementation doesn't not:

array(2) {
[0]=>
string(1) "o"
[1]=>
string(1) "O"
}

do you think such BC break is acceptable? or I still need a RFC? :<

I am not sure about that. Introducing a not easy to catch BC break for
0.1% gain on function (or even for the whole app) is not very
appealing.

However, there is nothing in the documentation actually describing how
it works and there are clear warnings about the unpredictable results.
That means we won't actually break it,per definition. I only wonder if
it is worth the effort for such little gain (yes, the ocean is made of
drops ;).

Cheers,

Pierre

@pierrejoye | http://www.libgd.org

I think this break is acceptable
Of course, if the new sort implementation significantly improves
performance on some cases and doesn't show degradation on the others.

Thanks. Dmitry.

Hey:

 I was working on zend_qsort improvement. but I got a problem need

to be disscussed with you fist..

 as we know,  previously zend_qsort is not a stable sorting algo.

 my draft patch (which already get 0.1% IRs reduce in wordpress)

is kindof a stable sorting algo, you can find it here
(https://github.com/laruence/php-src/compare/zend_sort)

 so, there is a bc break, like for :

 $array = array("o",  "O");
 sort($array, SORT_STRING|SORT_FLAG_CASE);

 var_dump($array);

 previously implementation does the swap:

array(2) {
[0]=>
string(1) "O"
[1]=>
string(1) "o"
}

 but new implementation doesn't not:

array(2) {
[0]=>
string(1) "o"
[1]=>
string(1) "O"
}

do you think such BC break is acceptable? or I still need a RFC? :<

thanks

Xinchen Hui
@Laruence
http://www.laruence.com/

Hey:

I made a PR here: https://github.com/php/php-src/pull/999 for reviewing

in benchmark this can brings more than 30% performance gain in

array_sort etc functions.

tests fails are related to non-stable vs stable sorting difference.

anyway, I feel it's better to ask you to do a final review, what

do you think?

is there any objections to merge this?

thanks

Hey:

 I was working on zend_qsort improvement. but I got a problem need

to be disscussed with you fist..

 as we know,  previously zend_qsort is not a stable sorting algo.

 my draft patch (which already get 0.1% IRs reduce in wordpress)

is kindof a stable sorting algo, you can find it here
(https://github.com/laruence/php-src/compare/zend_sort)

 so, there is a bc break, like for :

 $array = array("o",  "O");
 sort($array, SORT_STRING|SORT_FLAG_CASE);

 var_dump($array);

 previously implementation does the swap:

array(2) {
[0]=>
string(1) "O"
[1]=>
string(1) "o"
}

 but new implementation doesn't not:

array(2) {
[0]=>
string(1) "o"
[1]=>
string(1) "O"
}

do you think such BC break is acceptable? or I still need a RFC? :<

thanks

Xinchen Hui
@Laruence
http://www.laruence.com/

--
Xinchen Hui
@Laruence
http://www.laruence.com/

Hi Xinchen,

  my draft patch (which already get 0.1% IRs reduce in wordpress)

could you or anyone else help me understand what IR stands for?

Thanks in advance.