Date: Sat, 16 Sep 2017 12:18:02 -0400 From: Rich Felker <dalias@...c.org> To: musl@...ts.openwall.com Subject: Re: Wrong info in libc comparison On Sat, Sep 16, 2017 at 11:37:53AM +0200, Szabolcs Nagy wrote: > > Algorithms can be compared on a number of metrics, and just the name > > doesn't tell us much (e.g. quicksort with naive "first element" pivot > > selection has a pathological case on sorted input, while quicksort with > > med3 pivot selection handles that very well). If you really want to know > > something specific, you'll have to look it up in source, anyway. > > "mergesort+quicksort" sounds good to me, > it tells enough about what's going on, if there is some > known implementation mistake that can be added to the > description (like "naive" quicksort for dietlibc implying > O(n^2) worst case compares and potentially large stack use) Even non-naive quicksort has O(n²) time; there is a way to avoid this with an esoteric efficient algorithm for finding the median to use as the pivot, but nobody does it because the constant is so bad. The only known practical way to avoid the n² worst-case is some kind of introsort. So "naive" is really only about the problem of blowing up the stack. I agree something like "mergesort+quicksort" sounds good, but just to make sure, was mergesort already in use in the glibc version in the comparison? i.e. can I make this fix without inconsistently reflecting information from different glibc versions? Rich
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.