<div dir="ltr">It look like my patch was garbled on github so I attach it here in e-mail reply.<br></div><div class="gmail_extra"><br><div class="gmail_quote">On 28 July 2015 at 11:06, Rusty Russell <span dir="ltr"><<a href="mailto:rusty@rustcorp.com.au" target="_blank">rusty@rustcorp.com.au</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">Maxim Zakharov <<a href="mailto:notifications@github.com">notifications@github.com</a>> writes:<br>
> I have added bottom-up heapsort module implementing a modified version of bottom-up heapsort sorting, see details here: <a href="http://blog.dataparksearch.org/397" rel="noreferrer" target="_blank">http://blog.dataparksearch.org/397</a><br>
><br>
</span><div><div class="h5">> It is unified with asort() to be typesafe and accept context pointer for comparison function.<br>
><br>
> Would it better to rename bottom_up_heapsort() into bsort() for function name simplicity?<br>
<br>
Hi Maxim!<br>
<br>
        I like the module, unfortunately a rough benchmark shows it to<br>
only to be faster than asort (ie. glibc's sort) between 256 and 4096<br>
elements, which is not what I expected:<br>
<br>
asort-2 = 0.000003<br>
heapsort-2 = 0.000001<br>
asort-4 = 0.000001<br>
heapsort-4 = 0.000001<br>
asort-8 = 0.000001<br>
heapsort-8 = 0.000001<br>
asort-16 = 0.000002<br>
heapsort-16 = 0.000002<br>
asort-32 = 0.000003<br>
heapsort-32 = 0.000003<br>
asort-64 = 0.000006<br>
heapsort-64 = 0.000006<br>
asort-128 = 0.000011<br>
heapsort-128 = 0.000013<br>
asort-256 = 0.000094<br>
heapsort-256 = 0.000024<br>
asort-512 = 0.000108<br>
heapsort-512 = 0.000051<br>
asort-1024 = 0.000159<br>
heapsort-1024 = 0.000108<br>
asort-2048 = 0.000272<br>
heapsort-2048 = 0.000232<br>
asort-4096 = 0.000543<br>
heapsort-4096 = 0.000498<br>
asort-8192 = 0.001055<br>
heapsort-8192 = 0.001073<br>
asort-16384 = 0.002155<br>
heapsort-16384 = 0.002298<br>
asort-32768 = 0.004945<br>
heapsort-32768 = 0.004974<br>
asort-65536 = 0.009596<br>
heapsort-65536 = 0.010618<br>
asort-131072 = 0.020460<br>
heapsort-131072 = 0.022994<br>
asort-262144 = 0.042670<br>
heapsort-262144 = 0.049739<br>
asort-524288 = 0.089806<br>
heapsort-524288 = 0.107007<br>
asort-1048576 = 0.187838<br>
heapsort-1048576 = 0.235675<br>
asort-2097152 = 0.392327<br>
heapsort-2097152 = 0.544562<br>
asort-4194304 = 0.820443<br>
heapsort-4194304 = 1.255215<br>
asort-8388608 = 1.718564<br>
heapsort-8388608 = 2.751897<br>
asort-16777216 = 3.566820<br>
heapsort-16777216 = 6.017466<br>
asort-33554432 = 7.521751<br>
heapsort-33554432 = 13.410207<br>
asort-67108864 = 15.426503<br>
heapsort-67108864 = 28.932382<br>
<br>
Thanks,<br>
Rusty.<br>
<br>
commit ad0a71e85907a50c0b2807b581142139dd937c15<br>
</div></div>Author: Rusty Russell <<a href="mailto:rusty@rustcorp.com.au">rusty@rustcorp.com.au</a>><br>
<span class="">Date:   Tue Jul 28 10:23:46 2015 +0930<br>
<br>
    bottom_up_heapsort: add benchmark.<br>
<br>
</span>    Signed-off-by: Rusty Russell <<a href="mailto:rusty@rustcorp.com.au">rusty@rustcorp.com.au</a>><br>
<div><div class="h5"><br>
diff --git a/ccan/bottom_up_heapsort/benchmark/Makefile b/ccan/bottom_up_heapsort/benchmark/Makefile<br>
new file mode 100644<br>
index 0000000..66b0cbd<br>
--- /dev/null<br>
+++ b/ccan/bottom_up_heapsort/benchmark/Makefile<br>
@@ -0,0 +1,18 @@<br>
+CCANDIR := ../../../<br>
+CFLAGS := -Wall -I$(CCANDIR) -O3 -flto<br>
+LDFLAGS := -O3 -flto<br>
+<br>
+benchmark: benchmark.o ccan-asort.o ccan-bottom_up_heapsort.o ccan-time.o ccan-err.o<br>
+<br>
+clean:<br>
+       $(RM) -f *.o<br>
+<br>
+ccan-asort.o: $(CCANDIR)/ccan/asort/asort.c<br>
+       $(CC) $(CFLAGS) -c -o $@ $<<br>
+ccan-bottom_up_heapsort.o: $(CCANDIR)/ccan/bottom_up_heapsort/bottom_up_heapsort.c<br>
+       $(CC) $(CFLAGS) -c -o $@ $<<br>
+ccan-time.o: $(CCANDIR)/ccan/time/time.c<br>
+       $(CC) $(CFLAGS) -c -o $@ $<<br>
+ccan-err.o: $(CCANDIR)/ccan/err/err.c<br>
+       $(CC) $(CFLAGS) -c -o $@ $<<br>
+<br>
diff --git a/ccan/bottom_up_heapsort/benchmark/benchmark.c b/ccan/bottom_up_heapsort/benchmark/benchmark.c<br>
new file mode 100644<br>
index 0000000..42aea04<br>
--- /dev/null<br>
+++ b/ccan/bottom_up_heapsort/benchmark/benchmark.c<br>
@@ -0,0 +1,50 @@<br>
+#include <ccan/asort/asort.h><br>
+#include <ccan/time/time.h><br>
+#include <ccan/bottom_up_heapsort/bottom_up_heapsort.h><br>
+#include <ccan/err/err.h><br>
+#include <stdio.h><br>
+<br>
+static int compar(const int *a, const int *b, void *unused)<br>
+{<br>
+       return *a - *b;<br>
+}<br>
+<br>
+int main(int argc, char *argv[])<br>
+{<br>
+       unsigned int i, num;<br>
+       int *randoms;<br>
+       struct timeabs start;<br>
+       struct timerel asort_time, heapsort_time;<br>
+<br>
+       err_set_progname(argv[0]);<br>
+<br>
+       if (argc != 2 || (num = atoi(argv[1])) == 0)<br>
+               errx(1, "Usage: benchmark <nitems>");<br>
+<br>
+       randoms = calloc(sizeof(*randoms), num);<br>
+       srandom(0);<br>
+       for (i = 0; i < num; i++)<br>
+               randoms[i] = random();<br>
+<br>
+       start = time_now();<br>
+       asort(randoms, num, compar, NULL);<br>
+       asort_time = time_between(time_now(), start);<br>
+<br>
+       srandom(0);<br>
+       for (i = 0; i < num; i++)<br>
+               randoms[i] = random();<br>
+<br>
+       start = time_now();<br>
+       bottom_up_heapsort(randoms, num, compar, NULL);<br>
+       heapsort_time = time_between(time_now(), start);<br>
+<br>
+       printf("asort-%u = %u.%06u\n"<br>
+              "heapsort-%u = %u.%06u\n",<br>
+              num,<br>
+              (unsigned int)asort_time.ts.tv_sec,<br>
+              (unsigned int)(asort_time.ts.tv_nsec / 1000),<br>
+              num,<br>
+              (unsigned int)heapsort_time.ts.tv_sec,<br>
+              (unsigned int)(heapsort_time.ts.tv_nsec / 1000));<br>
+       return 0;<br>
+}<br>
</div></div>_______________________________________________<br>
ccan mailing list<br>
<a href="mailto:ccan@lists.ozlabs.org">ccan@lists.ozlabs.org</a><br>
<a href="https://lists.ozlabs.org/listinfo/ccan" rel="noreferrer" target="_blank">https://lists.ozlabs.org/listinfo/ccan</a><br>
</blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature"><div dir="ltr"><a href="http://au.linkedin.com/in/dpmaxime/" target="_blank">http://au.linkedin.com/in/dpmaxime/</a></div></div>
</div>