Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:94219
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain zeyos.com designates 159.122.110.40 as permitted sender)
Date: Thu, 23 Jun 2016 11:04:54 +0200
To: PHP Internals <internals@lists.php.net>,  	Xinchen Hui <xinchen.h@zend.com>,  	Nikita Popov <nikita.ppv@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Message-ID: <20160623090611.E6AA59F@mx.zeyos.com>
Subject: [PHP-DEV] Inconsistent implementation of array sorting (old zend_qsort in array_multisort)
From: ben.coutu@zeyos.com (Benjamin Coutu)

Hello everyone,

While reviewing the array.c code base, I have noticed that the array_multis=
ort function still uses the old zend_qsort instead of the new zend_sort alg=
orithm that was introduced with PHP 7.

That represents a clear inconsistency, because all other array sorting func=
tions utilize the advanced implementation of quicksort (through zend_hash_s=
ort) that was derived from LLVM's libc++ implementation of std::sort (https=
://marc.info/?l=3Dphp-internals&m=3D142047779209352).

Not only is zend_qsort less efficient, but moreover, because it doesn't rel=
y on the insertion sort fallback for small array chunks that zend_sort prov=
ides (which yields a more stable sorting order), the result might in effect=
 actually differ from that of all the other array sorting functions.

IMHO this inconsistency can be considered a bug.

Also, array_multisort is the only remnant in PHP core that still uses zend_=
qsort (https://github.com/php/php-src/search?q=3Dzend_qsort). If we would e=
liminate that inconsistency, we could probably dispense with the then obsol=
ete zend_qsort all together.

Please let me know your thoughts.

Thanks,

Ben=0A
--=20

Bejamin Coutu
ben.coutu@zeyos.com=0A=0AZeyOS, Inc.
http://www.zeyos.com