On 4/20/23 09:12, Jessica Clarke wrote:
On 20 Apr 2023, at 08:08, Hans Petter Selasky <hsela...@freebsd.org> wrote:
On 4/20/23 08:50, Jessica Clarke wrote:
On 20 Apr 2023, at 07:26, Hans Petter Selasky <hsela...@freebsd.org> wrote:
On 4/20/23 00:31, Jessica Clarke wrote:
On 19 Apr 2023, at 22:41, Hans Petter Selasky <hsela...@freebsd.org> wrote:
On 4/19/23 22:17, Jessica Clarke wrote:
pdqsort is n log n time, in-place and doesn’t allocate, and is used,
for example, for Rust’s standard sort_unstable.
Hi Jessica,
Like many many people have tried over the years, to improve the belated
QuickSort (*) algorithm since it was invented, by catching bad behaviour and
then fallback to other algorithms, pdqsort() is not a solution!
Yes, it is probably "N log N" time, but if you read the code carefully, it
falls back to heapsort(), which indeed uses malloc(), which is exactly my point, that I
want to avoid.
Hi,
Citation needed. This directly contradicts Rust’s documentation:
Sure, look at line 448 in there:
https://github.com/orlp/pdqsort/blob/master/pdqsort.h#L448
That’s not Rust, and that’s also a comment, not a malloc call.
This sort is unstable (i.e., may reorder equal elements), in-place (i.e., does
not allocate), and O(n * log(n)) worst-case.
Unfortunately it can end up allocating memory.
Again. Citation needed. Rust’s documentation says otherwise.
Hi Jessica,
Here are my citations:
cd /usr/ports/lang/rust
make extract
less work/rustc-1.68.2-src/library/alloc/src/slice.rs
/// The current algorithm is based on [pattern-defeating
quicksort][pdqsort] by Orson Peters,
/// which combines the fast average case of randomized quicksort with the
fast worst case of
/// heapsort, while achieving linear time on slices with certain patterns.
It uses some
/// randomization to avoid degenerate cases, but with a fixed seed to
always provide
/// deterministic behavior.
And? That’s just a comment, it’s not a memory allocation.
less /usr/src/lib/libc/stdlib/heapsort.c
The first thing heapsort() does is go and grab memory:
if ((k = malloc(size)) == NULL)
return (-1);
That’s our heapsort. Neither Rust’s nor pdqsort’s calls heapsort(3). So
again, point me at the malloc that you claim is made by either Rust or
pdqsort despite Rust’s own documentation explicitly stating it does not
do that.
This conversation is getting extremely tiresome.
Hi Jessica,
FreeBSD's libc is written in C and not Rust. Please point to something
written in C.
Probably that malloc() can be on-stack for small sizes in libc's heapsort().
On GitHub : hselasky/qsortbench you can apply this patch:
diff --git a/Makefile b/Makefile
index a0d85e0..634fabc 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,5 @@
-CC := gcc
-CFLAGS = -Ofast -march=native -Wall -Wextra -std=c11 # -Dcheck=1
+CC := clang # gcc
+CFLAGS = -O3 -march=native -Wall -Wextra -std=c11 # -Dcheck=1
#CFLAGS = -Os -march=native -Wall -Wextra -std=c11 # -Dcheck=1
LDFLAGS = -flto
diff --git a/qsort.c b/qsort.c
index b18a4f9..079fb07 100644
--- a/qsort.c
+++ b/qsort.c
@@ -175,6 +175,7 @@ int main(int argc, char *argv[]) {
{ musl_qsort, "musl" , 0, 0 },
{ diet_qsort, "diet" , 0, 0 },
{ bsort_qsort, "bsort" , 0, 0 },
+ { heapsort, "heapsort", 0, 0 },
{ bsd_qsort, "bsd" , 0, 0 },
{ uclibc_qsort, "uclibc" , 0, 0 },
{ plan9_qsort, "plan9" , 0, 0 },
Then you do "gmake" and run the test-bench:
./qsort 1000000
Comparing heapsort() to bsort() gives the following results:
leaderboard
1. illumos 0.998335 1.000000
2. mine 1.013954 1.015645
3. system 1.154811 1.156737
4. glibc 1.033140 1.034864
5. freebsd 1.212156 1.214178
6. plan9 1.503944 1.506453
7. bsd 1.467272 1.469719
8. wada 1.713490 1.716349
9. mini 2.545149 2.549395
10. bsort 2.819615 2.824318
11. linux 2.051919 2.055342
12. musl 3.194471 3.199800
13. diet 2.242223 2.245964
14. uclibc 3.561086 3.567026
15. heapsort 2.879076 2.883879
Our libc's heapsort() is on the bottom.
--HPS
