/*
- * An experiment with sorting algorithms
+ * Experiments with various sorting algorithms
+ *
+ * (c) 2007--2008 Martin Mares <mj@ucw.cz>
*/
#include "sherlock/sherlock.h"
-#include "lib/getopt.h"
-#include "lib/md5.h"
+#include "ucw/getopt.h"
+#include "ucw/md5.h"
+#include "ucw/heap.h"
#include <stdio.h>
#include <stdlib.h>
#define ASORT_ELT(i) a[i].key
#define ASORT_SWAP(i,j) do { struct elt t=a[i]; a[i]=a[j]; a[j]=t; } while (0)
#define ASORT_EXTRA_ARGS , struct elt *a
-#include "lib/arraysort.h"
+#include "ucw/arraysort.h"
#define ASORT_PREFIX(x) asi_##x
#define ASORT_KEY_TYPE u32
#define ASORT_ELT(i) ind[i]->key
#define ASORT_SWAP(i,j) do { struct elt *t=ind[i]; ind[i]=ind[j]; ind[j]=t; } while (0)
-#include "lib/arraysort.h"
+#include "ucw/arraysort.h"
static void r1_sort(void)
{
struct elt *ptrs[256], *x, *lim;
ASSERT(sizeof(struct elt) == 16);
- ASSERT(!((addr_int_t)alt & 15));
- ASSERT(!((addr_int_t)ary & 15));
+ ASSERT(!((uintptr_t)alt & 15));
+ ASSERT(!((uintptr_t)ary & 15));
x = ary; lim = ary + n;
bzero(cnt, sizeof(cnt));
xfree(aux);
}
+static void heapsort(void)
+{
+#define H_LESS(_a,_b) ((_a).key > (_b).key)
+ struct elt *heap = ary-1;
+ HEAP_INIT(struct elt, heap, n, H_LESS, HEAP_SWAP);
+ uns nn = n;
+ while (nn)
+ HEAP_DELMIN(struct elt, heap, nn, H_LESS, HEAP_SWAP);
+#undef H_LESS
+}
+
+static void heapsort_ind(void)
+{
+#define H_LESS(_a,_b) ((_a)->key > (_b)->key)
+ struct elt **heap = ind-1;
+ HEAP_INIT(struct elt *, heap, n, H_LESS, HEAP_SWAP);
+ uns nn = n;
+ while (nn)
+ HEAP_DELMIN(struct elt *, heap, nn, H_LESS, HEAP_SWAP);
+#undef H_LESS
+}
+
static void mk_ary(void)
{
ary = array0;
alt = array1;
- struct MD5Context ctx;
- MD5Init(&ctx);
+ md5_context ctx;
+ md5_init(&ctx);
u32 block[16];
bzero(block, sizeof(block));
if (!(i % 4))
{
block[i%16] = i;
- MD5Transform(ctx.buf, block);
+ md5_transform(ctx.buf, block);
}
ary[i].key = ctx.buf[i%4];
#else
for (uns i=0; i<n; i++)
array0[i] = array1[i] = (struct elt) { 0 };
+ log(L_INFO, "Testing with %u elements", n);
+
mk_ary();
- init_timer();
+ timestamp_t timer;
+ init_timer(&timer);
for (uns i=0; i<5; i++)
{
#if 1
ary[j] = alt[j];
#endif
}
- log(L_DEBUG, "memcpy: %d", get_timer()/10);
+ log(L_DEBUG, "memcpy: %d", get_timer(&timer)/10);
-#define BENCH(type, name, func) mk_##type(); init_timer(); func; log(L_DEBUG, name ": %d", get_timer()); chk_##type()
+#define BENCH(type, name, func) mk_##type(); init_timer(&timer); func; log(L_DEBUG, name ": %d", get_timer(&timer)); chk_##type()
- //BENCH(ary, "qsort", qsort(ary, n, sizeof(struct elt), comp));
- //BENCH(ary, "arraysort", as_sort(n, ary));
- //BENCH(ind, "indirect qsort", qsort(ind, n, sizeof(struct elt *), comp_ind));
- //BENCH(ind, "indirect arraysort", asi_sort(n));
- //BENCH(ary, "radix1", r1_sort());
- //BENCH(ary, "radix1b", r1b_sort());
+ BENCH(ary, "qsort", qsort(ary, n, sizeof(struct elt), comp));
+ BENCH(ary, "arraysort", as_sort(n, ary));
+ BENCH(ind, "indirect qsort", qsort(ind, n, sizeof(struct elt *), comp_ind));
+ BENCH(ind, "indirect arraysort", asi_sort(n));
+ BENCH(ary, "radix1", r1_sort());
+ BENCH(ary, "radix1b", r1b_sort());
BENCH(ary, "radix1c", r1c_sort());
- //BENCH(ary, "radix1c-sse", r1c_sse_sort());
- //BENCH(ary, "radix1d", r1d_sort());
- //BENCH(ary, "radix2", r2_sort());
+ BENCH(ary, "radix1c-sse", r1c_sse_sort());
+ BENCH(ary, "radix1d", r1d_sort());
+ BENCH(ary, "radix2", r2_sort());
BENCH(ary, "radix3", r3_sort());
- //BENCH(ary, "mergesort", mergesort());
- //BENCH(ary, "samplesort", samplesort());
- //BENCH(ary, "samplesort2", samplesort2());
+ BENCH(ary, "mergesort", mergesort());
+ BENCH(ary, "samplesort", samplesort());
+ BENCH(ary, "samplesort2", samplesort2());
+ BENCH(ary, "heapsort", heapsort());
+ BENCH(ind, "indirect heapsort", heapsort_ind());
free_elts(array0, n);
free_elts(array1, n);