[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20170916161802.GY1627@brightrain.aerifal.cx>
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.
