[ccan] add bottom-up heapsort (#23)

[Rusty Russell]

Maxim Zakharov <notifications at github.com> writes:
> I have added bottom-up heapsort module implementing a modified version of bottom-up heapsort sorting, see details here: http://blog.dataparksearch.org/397
>
> It is unified with asort() to be typesafe and accept context pointer for comparison function.
>
> Would it better to rename bottom_up_heapsort() into bsort() for function name simplicity?

Hi Maxim!

        I like the module, unfortunately a rough benchmark shows it to
only to be faster than asort (ie. glibc's sort) between 256 and 4096
elements, which is not what I expected:

asort-2 = 0.000003
heapsort-2 = 0.000001
asort-4 = 0.000001
heapsort-4 = 0.000001
asort-8 = 0.000001
heapsort-8 = 0.000001
asort-16 = 0.000002
heapsort-16 = 0.000002
asort-32 = 0.000003
heapsort-32 = 0.000003
asort-64 = 0.000006
heapsort-64 = 0.000006
asort-128 = 0.000011
heapsort-128 = 0.000013
asort-256 = 0.000094
heapsort-256 = 0.000024
asort-512 = 0.000108
heapsort-512 = 0.000051
asort-1024 = 0.000159
heapsort-1024 = 0.000108
asort-2048 = 0.000272
heapsort-2048 = 0.000232
asort-4096 = 0.000543
heapsort-4096 = 0.000498
asort-8192 = 0.001055
heapsort-8192 = 0.001073
asort-16384 = 0.002155
heapsort-16384 = 0.002298
asort-32768 = 0.004945
heapsort-32768 = 0.004974
asort-65536 = 0.009596
heapsort-65536 = 0.010618
asort-131072 = 0.020460
heapsort-131072 = 0.022994
asort-262144 = 0.042670
heapsort-262144 = 0.049739
asort-524288 = 0.089806
heapsort-524288 = 0.107007
asort-1048576 = 0.187838
heapsort-1048576 = 0.235675
asort-2097152 = 0.392327
heapsort-2097152 = 0.544562
asort-4194304 = 0.820443
heapsort-4194304 = 1.255215
asort-8388608 = 1.718564
heapsort-8388608 = 2.751897
asort-16777216 = 3.566820
heapsort-16777216 = 6.017466
asort-33554432 = 7.521751
heapsort-33554432 = 13.410207
asort-67108864 = 15.426503
heapsort-67108864 = 28.932382

Thanks,
Rusty.

commit ad0a71e85907a50c0b2807b581142139dd937c15
Author: Rusty Russell <rusty at rustcorp.com.au>
Date:   Tue Jul 28 10:23:46 2015 +0930

    bottom_up_heapsort: add benchmark.
    
    Signed-off-by: Rusty Russell <rusty at rustcorp.com.au>

diff --git a/ccan/bottom_up_heapsort/benchmark/Makefile b/ccan/bottom_up_heapsort/benchmark/Makefile
new file mode 100644
index 0000000..66b0cbd
--- /dev/null
+++ b/ccan/bottom_up_heapsort/benchmark/Makefile
@@ -0,0 +1,18 @@
+CCANDIR := ../../../
+CFLAGS := -Wall -I$(CCANDIR) -O3 -flto
+LDFLAGS := -O3 -flto
+
+benchmark: benchmark.o ccan-asort.o ccan-bottom_up_heapsort.o ccan-time.o ccan-err.o
+
+clean:
+	$(RM) -f *.o
+
+ccan-asort.o: $(CCANDIR)/ccan/asort/asort.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+ccan-bottom_up_heapsort.o: $(CCANDIR)/ccan/bottom_up_heapsort/bottom_up_heapsort.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+ccan-time.o: $(CCANDIR)/ccan/time/time.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+ccan-err.o: $(CCANDIR)/ccan/err/err.c
+	$(CC) $(CFLAGS) -c -o $@ $<
+
diff --git a/ccan/bottom_up_heapsort/benchmark/benchmark.c b/ccan/bottom_up_heapsort/benchmark/benchmark.c
new file mode 100644
index 0000000..42aea04
--- /dev/null
+++ b/ccan/bottom_up_heapsort/benchmark/benchmark.c
@@ -0,0 +1,50 @@
+#include <ccan/asort/asort.h>
+#include <ccan/time/time.h>
+#include <ccan/bottom_up_heapsort/bottom_up_heapsort.h>
+#include <ccan/err/err.h>
+#include <stdio.h>
+
+static int compar(const int *a, const int *b, void *unused)
+{
+	return *a - *b;
+}
+
+int main(int argc, char *argv[])
+{
+	unsigned int i, num;
+	int *randoms;
+	struct timeabs start;
+	struct timerel asort_time, heapsort_time;
+
+	err_set_progname(argv[0]);
+
+	if (argc != 2 || (num = atoi(argv[1])) == 0)
+		errx(1, "Usage: benchmark <nitems>");
+
+	randoms = calloc(sizeof(*randoms), num);
+	srandom(0);
+	for (i = 0; i < num; i++)
+		randoms[i] = random();
+
+	start = time_now();
+	asort(randoms, num, compar, NULL);
+	asort_time = time_between(time_now(), start);
+	
+	srandom(0);
+	for (i = 0; i < num; i++)
+		randoms[i] = random();
+	
+	start = time_now();
+	bottom_up_heapsort(randoms, num, compar, NULL);
+	heapsort_time = time_between(time_now(), start);
+
+	printf("asort-%u = %u.%06u\n"
+	       "heapsort-%u = %u.%06u\n",
+	       num,
+	       (unsigned int)asort_time.ts.tv_sec,
+	       (unsigned int)(asort_time.ts.tv_nsec / 1000),
+	       num,
+	       (unsigned int)heapsort_time.ts.tv_sec,
+	       (unsigned int)(heapsort_time.ts.tv_nsec / 1000));
+	return 0;
+}