Date: Sat, 16 Sep 2017 21:34:34 +0200 From: Markus Wichmann <nullplan@....net> To: musl@...ts.openwall.com Subject: Re: Wrong info in libc comparison On Sat, Sep 16, 2017 at 07:11:54PM +0200, Szabolcs Nagy wrote: > glibc, uclibc, dietlibc, newlib, netbsd, openbsd, freebsd > qsort are all O(n^2) worst-case, musl qsort is O(n log(n)). > Yes, sorry, I mixed that up. Quicksort is loglinear only in the average case. Same for Shell sort being O(sqrt(n^3)). > i think this is not a sidetrack, but relevant detail > for a libc comparision page. > (the openbsd proof of concept stack clash exploit > relied on the unbounded stack use in qsort, that > would not work against musl, but all the other libcs > are affected.) No, stack usage is not necessarily linear even with quicksort. dietlibc and avr-libc have linear stack usage (with avr-libc always recursing into the first subproblem, and dietlibc always recursing into both subproblems), that's right, but glibc uses a constant amount of stack (automatic allocation of an array to hold the maximum possible number of subproblems, which is equal to the number of bits in a machine word), and newlib uses recursion into the smaller subproblem, thus using a logarithmic amount of stack (functionally constant, since you can give an upper limit). And uclibc also uses a constant amount of stack. Shell sort doesn't need recursion. Ciao, Markus
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.