On Fri, May 19, 2017 at 09:04:30AM -0600, Todd C. Miller wrote:
> On Thu, 18 May 2017 09:58:14 -0600, "Todd C. Miller" wrote:
>
> > I believe the best approach is to switch qsort.c to "introsort".
> > The changes are minimal and the elimination of the O(n^2) worst
> > case is compelling.
>
> I've added input arrays to the qsort regress test that exhibit
> quadratic behavior in our quicksort. The introsort diff prevents
> qsort from going quadratic.
>
> McIlroy's "A Killer Adversary for Quicksort" was used to generate
> the test vectors. http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
>
> - todd
Hmm, on arm I get:
cc -O2 -pipe -g -Wimplicit -I/usr/src/lib/libc/include
-I/usr/src/lib/libc/hidden -D__LIBC__
-Werror-implicit-function-declaration -include namespace.h
-Werror=deprecated-declarations -DAPIWARN -DYP -I/usr/src/lib/libc/yp
-DSOFTFLOAT_FOR_GCC -I/usr/src/lib/libc/softfloat -I/usr/src/lib/libc
-I/usr/src/lib/libc/gdtoa -I/usr/src/lib/libc/arch/arm/gdtoa
-DINFNAN_CHECK -DMULTIPLE_THREADS -DNO_FENV_H -DUSE_LOCALE
-I/usr/src/lib/libc -I/usr/src/lib/libc/citrus -DRESOLVSORT
-DFLOATING_POINT -DPRINTF_WIDE_CHAR -DSCANF_WIDE_CHAR -DSOFTFLOAT -c
/usr/src/lib/libc/stdlib/qsort.c -o qsort.o
/usr/src/lib/libc/stdlib/qsort.c: In function 'introsort':
/usr/src/lib/libc/stdlib/qsort.c:104: error: 'heapsort' is deprecated
(declared at /usr/src/lib/libc/hidden/stdlib.h:95)
*** Error 1 in /usr/src/lib/libc (<bsd.lib.mk>:41 'qsort.o': @cc -O2
-pipe -g -Wimplicit -I/usr/src/lib/libc/include -I/usr/src/lib/libc/hid...)
-Otto
