[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <20170913135154.pfwpg7f32nv4dhja@voyager>
Date: Wed, 13 Sep 2017 15:51:54 +0200
From: Markus Wichmann <nullplan@....net>
To: musl@...ts.openwall.com
Subject: Wrong info in libc comparison
Hello,
there's a mistake on the libc comparison page
http://www.etalabs.net/compare_libcs.html: Namely it states that glibc
uses introsort as sorting algorithm. It doesn't. Glibc uses a
bog-standard merge sort as main sorting algorithm. A major part of the
implementation is actually just devoted to optimized copying, and for
arrays of large objects it uses an interesting way to indirectly sort
them (i.e. it then allocates an array of references, sorts the
references, then uses a clever algorithm to get from sorted references
to a sorted array). But it's all just a standard merge sort.
However, merge sort on arrays requires a linear amount of scratch space,
so this merge sort has to allocate memory. Memory allocation is allowed
to fail, but sorting isn't, so, as a fallback, in case the allocation
fails (or would use more than half the physical memory, for some
reason), it falls back to quicksort. This quicksort is implemented with
a really funky scheme for an explicit stack (i.e., while I'd use
push_total_problem();
while (stack_not_empty()) {
pop_subprob();
if (subprob_worth_bothering_with()) {
sort_partition();
push_larger_subprob();
push_smaller_subprob();
}
}
they do something more like:
push_pseudo_problem();
while (stack_not_empty()) {
if (subprob_worth_bothering_with()) {
sort_partition();
figure_out_next_subproblem();
then_maybe_push_or_pop_stuff();
}
}
), a median-of-three pivot selection, two-way partitioning (why couldn't
you be perfect for me?), and a minimum partition size of 4,
necessitating an insertion sort stage afterwards.
So, yeah, no introsort in sight. Introsort would be merge sort on large
arrays, then quicksort on smaller partitions, and finally insertion sort
for the smallest partitions.
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.
