X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=debug%2Fsorter%2Fretros.c;h=7bb692f6bead3094d3d3b06a6ea8a9088d3a0042;hb=d84b9fd101d2bf3a72b9dc1d603c9b3960e8cb17;hp=b0de3a824e91b53848ee9f9ca5064cdfd6e86c45;hpb=8c661b20faa518f211d54b59ede9127e3b633914;p=libucw.git

diff --git a/debug/sorter/retros.c b/debug/sorter/retros.c
index b0de3a82..7bb692f6 100644
--- a/debug/sorter/retros.c
+++ b/debug/sorter/retros.c
@@ -1,10 +1,13 @@
 /*
- *  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>
@@ -23,25 +26,12 @@ static u32 sum;
 
 static struct elt *alloc_elts(uns n)
 {
-#if 0
-  return xmalloc(n * sizeof(struct elt));
-#else
-  uns len = ALIGN_TO(n * sizeof(struct elt), PAGE_SIZE);
-  void *p = mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
-  ASSERT(p != MAP_FAILED);
-  return p;
-#endif
+  return big_alloc(n * sizeof(struct elt));
 }
 
 static void free_elts(struct elt *a, uns n)
 {
-#if 0
-  xfree(a);
-  (void) n;
-#else
-  uns len = ALIGN_TO(n * sizeof(struct elt), PAGE_SIZE);
-  munmap(a, len);
-#endif
+  big_free(a, n * sizeof(struct elt));
 }
 
 static int comp(const void *x, const void *y)
@@ -61,13 +51,13 @@ static int comp_ind(const void *x, const void *y)
 #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/sorter/array-simple.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/sorter/array-simple.h"
 
 static void r1_sort(void)
 {
@@ -198,8 +188,8 @@ static void r1c_sse_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));
@@ -625,12 +615,34 @@ static void samplesort2(void)
   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));
 
@@ -641,7 +653,7 @@ static void mk_ary(void)
       if (!(i % 4))
 	{
 	  block[i%16] = i;
-	  MD5Transform(ctx.buf, block);
+	  md5_transform(ctx.buf, block);
 	}
       ary[i].key = ctx.buf[i%4];
 #else
@@ -707,8 +719,11 @@ int main(int argc, char **argv)
   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
@@ -721,24 +736,26 @@ int main(int argc, char **argv)
 	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);