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

[Maxim Zakharov]

It look like my patch was garbled on github so I attach it here in e-mail
reply.

On 28 July 2015 at 11:06, Rusty Russell <rusty at rustcorp.com.au> wrote:

> 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;
> +}
> _______________________________________________
> ccan mailing list
> ccan at lists.ozlabs.org
> https://lists.ozlabs.org/listinfo/ccan
>



-- 
http://au.linkedin.com/in/dpmaxime/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ozlabs.org/pipermail/ccan/attachments/20150729/7d5bede4/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: b.patch
Type: text/x-patch
Size: 7672 bytes
Desc: not available
URL: <http://lists.ozlabs.org/pipermail/ccan/attachments/20150729/7d5bede4/attachment.bin>