Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

[libucw.git] / lib / sorter / sort-test.c

diff --git a/lib/sorter/sort-test.c b/lib/sorter/sort-test.c
index ddf6734dc238c3acf400413abcba1394482393f6..e7d5873020d2bb527e2ac0efb312bbe5ff0b8e4f 100644 (file)
--- a/lib/sorter/sort-test.c
+++ b/lib/sorter/sort-test.c
@@ -11,6 +11,7 @@
 #include "lib/getopt.h"
 #include "lib/conf.h"
 #include "lib/fastbuf.h"
 #include "lib/getopt.h"
 #include "lib/conf.h"
 #include "lib/fastbuf.h"

+#include "lib/ff-binary.h"

 #include "lib/hashfunc.h"
 #include "lib/md5.h"
 
 #include "lib/hashfunc.h"
 #include "lib/md5.h"
 


@@ -18,19 +19,32 @@
 #include <stdio.h>
 #include <string.h>
 #include <fcntl.h>
 #include <stdio.h>
 #include <string.h>
 #include <fcntl.h>

+#include <unistd.h>
+
+/*** A hack for overriding radix-sorter configuration ***/
+
+#ifdef FORCE_RADIX_BITS
+#undef CONFIG_UCW_RADIX_SORTER_BITS
+#define CONFIG_UCW_RADIX_SORTER_BITS FORCE_RADIX_BITS
+#endif

 
 /*** Time measurement ***/
 
 
 /*** Time measurement ***/
 

+static timestamp_t timer;
+static uns test_id;
+

 static void
 start(void)
 {
 static void
 start(void)
 {

-  init_timer();
+  sync();
+  init_timer(&timer);

 }
 
 static void
 stop(void)
 {
 }
 
 static void
 stop(void)
 {

-  log(L_INFO, "Test took %.3fs", get_timer() / 1000.);
+  sync();
+  msg(L_INFO, "Test %d took %.3fs", test_id, get_timer(&timer) / 1000.);

 }
 
 /*** Simple 4-byte integer keys ***/
 }
 
 /*** Simple 4-byte integer keys ***/


@@ -45,6 +59,7 @@ struct key1 {
 #define SORT_OUTPUT_FB
 #define SORT_UNIQUE
 #define SORT_INT(k) (k).x
 #define SORT_OUTPUT_FB
 #define SORT_UNIQUE
 #define SORT_INT(k) (k).x

+#define SORT_DELETE_INPUT 0

 
 #include "lib/sorter/sorter.h"
 
 
 #include "lib/sorter/sorter.h"
 


@@ -53,7 +68,7 @@ test_int(int mode, u64 size)
 {
   uns N = size ? nextprime(MIN(size/4, 0xffff0000)) : 0;
   uns K = N/4*3;
 {
   uns N = size ? nextprime(MIN(size/4, 0xffff0000)) : 0;
   uns K = N/4*3;

-  log(L_INFO, ">>> Integers (%s, N=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
+  msg(L_INFO, ">>> Integers (%s, N=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);

 
   struct fastbuf *f = bopen_tmp(65536);
   for (uns i=0; i<N; i++)
 
   struct fastbuf *f = bopen_tmp(65536);
   for (uns i=0; i<N; i++)


@@ -69,7 +84,7 @@ test_int(int mode, u64 size)
     {
       uns j = bgetl(f);
       if (i != j)
     {
       uns j = bgetl(f);
       if (i != j)

-       die("Discrepancy: %d instead of %d", j, i);
+       die("Discrepancy: %u instead of %u", j, i);

     }
   bclose(f);
 }
     }
   bclose(f);
 }


@@ -88,13 +103,6 @@ static inline void s2_write_merged(struct fastbuf *f, struct key2 **k, void **d
   bwrite(f, k[0], sizeof(struct key2));
 }
 
   bwrite(f, k[0], sizeof(struct key2));
 }
 

-static inline void s2_copy_merged(struct key2 **k, struct fastbuf **d UNUSED, uns n, struct fastbuf *dest)
-{
-  for (uns i=1; i<n; i++)
-    k[0]->cnt += k[i]->cnt;
-  bwrite(dest, k[0], sizeof(struct key2));
-}
-

 #define SORT_KEY_REGULAR struct key2
 #define SORT_PREFIX(x) s2_##x
 #define SORT_INPUT_FB
 #define SORT_KEY_REGULAR struct key2
 #define SORT_PREFIX(x) s2_##x
 #define SORT_INPUT_FB


@@ -113,7 +121,7 @@ test_counted(int mode, u64 size)
     mult++;
   uns N = items ? nextprime(items/(2*mult)) : 0;
   uns K = N/4*3;
     mult++;
   uns N = items ? nextprime(items/(2*mult)) : 0;
   uns K = N/4*3;

-  log(L_INFO, ">>> Counted integers (%s, N=%d, mult=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N, mult);
+  msg(L_INFO, ">>> Counted integers (%s, N=%u, mult=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N, mult);

 
   struct fastbuf *f = bopen_tmp(65536);
   for (uns m=0; m<mult; m++)
 
   struct fastbuf *f = bopen_tmp(65536);
   for (uns m=0; m<mult; m++)


@@ -134,10 +142,10 @@ test_counted(int mode, u64 size)
     {
       uns j = bgetl(f);
       if (i != j)
     {
       uns j = bgetl(f);
       if (i != j)

-       die("Discrepancy: %d instead of %d", j, i);
+       die("Discrepancy: %u instead of %u", j, i);

       uns k = bgetl(f);
       if (k != 2*mult)
       uns k = bgetl(f);
       if (k != 2*mult)

-       die("Discrepancy: %d has count %d instead of %d", j, k, mult);
+       die("Discrepancy: %u has count %u instead of %u", j, k, 2*mult);

     }
   bclose(f);
 }
     }
   bclose(f);
 }


@@ -152,9 +160,10 @@ struct key3 {
 
 static inline int s3_compare(struct key3 *x, struct key3 *y)
 {
 
 static inline int s3_compare(struct key3 *x, struct key3 *y)
 {

-  /* FIXME: Maybe unroll manually? */
-  for (uns i=0; i<4; i++)
-    COMPARE(x->hash[i], y->hash[i]);
+  COMPARE(x->hash[0], y->hash[0]);
+  COMPARE(x->hash[1], y->hash[1]);
+  COMPARE(x->hash[2], y->hash[2]);
+  COMPARE(x->hash[3], y->hash[3]);

   return 0;
 }
 
   return 0;
 }
 


@@ -205,7 +214,7 @@ static void
 test_hashes(int mode, u64 size)
 {
   uns N = MIN(size / sizeof(struct key3), 0xffffffff);
 test_hashes(int mode, u64 size)
 {
   uns N = MIN(size / sizeof(struct key3), 0xffffffff);

-  log(L_INFO, ">>> Hashes (%s, N=%d)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);
+  msg(L_INFO, ">>> Hashes (%s, N=%u)", ((char *[]) { "increasing", "decreasing", "random" })[mode], N);

   struct key3 k, lastk;
 
   struct fastbuf *f = bopen_tmp(65536);
   struct key3 k, lastk;
 
   struct fastbuf *f = bopen_tmp(65536);


@@ -323,7 +332,7 @@ test_strings(uns mode, u64 size)
 {
   uns avg_item_size = KEY4_MAX/2 + 4 + (mode ? 128 : 0);
   uns N = MIN(size / avg_item_size, 0xffffffff);
 {
   uns avg_item_size = KEY4_MAX/2 + 4 + (mode ? 128 : 0);
   uns N = MIN(size / avg_item_size, 0xffffffff);

-  log(L_INFO, ">>> Strings %s(N=%d)", (mode ? "with data " : ""), N);
+  msg(L_INFO, ">>> Strings %s(N=%u)", (mode ? "with data " : ""), N);

   srand(1);
 
   struct key4 k, lastk;
   srand(1);
 
   struct key4 k, lastk;


@@ -388,7 +397,7 @@ static int s5_gen(struct s5_pair *p)
 {
   if (s5_j >= s5_N)
     {
 {
   if (s5_j >= s5_N)
     {

-      if (s5_i >= s5_N-1)
+      if (!s5_N || s5_i >= s5_N-1)

        return 0;
       s5_j = 0;
       s5_i++;
        return 0;
       s5_j = 0;
       s5_i++;


@@ -407,7 +416,6 @@ static int s5_gen(struct s5_pair *p)
 
 static void s5_write_merged(struct fastbuf *f, struct key5 **keys, void **data, uns n, void *buf)
 {
 
 static void s5_write_merged(struct fastbuf *f, struct key5 **keys, void **data, uns n, void *buf)
 {

-  /* FIXME: Allow mode where this function is not defined? */

   u32 *a = buf;
   uns m = 0;
   for (uns i=0; i<n; i++)
   u32 *a = buf;
   uns m = 0;
   for (uns i=0; i<n; i++)


@@ -418,7 +426,7 @@ static void s5_write_merged(struct fastbuf *f, struct key5 **keys, void **data,
   s5m_sort(m, a);
   keys[0]->cnt = m;
   bwrite(f, keys[0], sizeof(struct key5));
   s5m_sort(m, a);
   keys[0]->cnt = m;
   bwrite(f, keys[0], sizeof(struct key5));

-  bwrite(f, a, 4*m);                   /* FIXME: Might overflow here */
+  bwrite(f, a, 4*m);

 }
 
 static void s5_copy_merged(struct key5 **keys, struct fastbuf **data, uns n, struct fastbuf *dest)
 }
 
 static void s5_copy_merged(struct key5 **keys, struct fastbuf **data, uns n, struct fastbuf *dest)


@@ -453,13 +461,10 @@ static inline int s5p_lt(struct s5_pair x, struct s5_pair y)
   return 0;
 }
 
   return 0;
 }
 

-/* FIXME: Use smarter internal sorter when it's available */

 #define ASORT_PREFIX(x) s5p_##x
 #define ASORT_KEY_TYPE struct s5_pair
 #define ASORT_PREFIX(x) s5p_##x
 #define ASORT_KEY_TYPE struct s5_pair

-#define ASORT_ELT(i) ary[i]

 #define ASORT_LT(x,y) s5p_lt(x,y)
 #define ASORT_LT(x,y) s5p_lt(x,y)

-#define ASORT_EXTRA_ARGS , struct s5_pair *ary
-#include "lib/arraysort.h"
+#include "lib/sorter/array.h"

 
 static int s5_presort(struct fastbuf *dest, void *buf, size_t bufsize)
 {
 
 static int s5_presort(struct fastbuf *dest, void *buf, size_t bufsize)
 {


@@ -470,7 +475,7 @@ static int s5_presort(struct fastbuf *dest, void *buf, size_t bufsize)
     n++;
   if (!n)
     return 0;
     n++;
   if (!n)
     return 0;

-  s5p_sort(n, a);
+  s5p_sort(a, n);

   uns i = 0;
   while (i < n)
     {
   uns i = 0;
   while (i < n)
     {


@@ -489,6 +494,7 @@ static int s5_presort(struct fastbuf *dest, void *buf, size_t bufsize)
 #define SORT_PREFIX(x) s5_##x
 #define SORT_DATA_SIZE(k) (4*(k).cnt)
 #define SORT_UNIFY
 #define SORT_PREFIX(x) s5_##x
 #define SORT_DATA_SIZE(k) (4*(k).cnt)
 #define SORT_UNIFY

+#define SORT_UNIFY_WORKSPACE(k) SORT_DATA_SIZE(k)

 #define SORT_INPUT_PRESORT
 #define SORT_OUTPUT_THIS_FB
 #define SORT_INT(k) (k).x
 #define SORT_INPUT_PRESORT
 #define SORT_OUTPUT_THIS_FB
 #define SORT_INT(k) (k).x


@@ -499,6 +505,7 @@ static int s5_presort(struct fastbuf *dest, void *buf, size_t bufsize)
 #define SORT_PREFIX(x) s5b_##x
 #define SORT_DATA_SIZE(k) (4*(k).cnt)
 #define SORT_UNIFY
 #define SORT_PREFIX(x) s5b_##x
 #define SORT_DATA_SIZE(k) (4*(k).cnt)
 #define SORT_UNIFY

+#define SORT_UNIFY_WORKSPACE(k) SORT_DATA_SIZE(k)

 #define SORT_INPUT_FB
 #define SORT_OUTPUT_THIS_FB
 #define SORT_INT(k) (k).x
 #define SORT_INPUT_FB
 #define SORT_OUTPUT_THIS_FB
 #define SORT_INT(k) (k).x


@@ -513,10 +520,13 @@ test_graph(uns mode, u64 size)
   uns N = 3;
   while ((u64)N*(N+2)*4 < size)
     N = nextprime(N);
   uns N = 3;
   while ((u64)N*(N+2)*4 < size)
     N = nextprime(N);

-  log(L_INFO, ">>> Graph%s (N=%d)", (mode ? "" : " with custom presorting"), N);
+  if (!size)
+    N = 0;
+  msg(L_INFO, ">>> Graph%s (N=%u)", (mode ? "" : " with custom presorting"), N);

   s5_N = N;
   s5_K = N/4*3;
   s5_L = N/3*2;
   s5_N = N;
   s5_K = N/4*3;
   s5_L = N/3*2;

+  s5_i = s5_j = 0;

 
   struct fastbuf *in = NULL;
   if (mode)
 
   struct fastbuf *in = NULL;
   if (mode)


@@ -558,11 +568,53 @@ test_graph(uns mode, u64 size)
   bclose(f);
 }
 
   bclose(f);
 }
 

+/*** Simple 8-byte integer keys ***/
+
+struct key6 {
+  u64 x;
+};
+
+#define SORT_KEY_REGULAR struct key6
+#define SORT_PREFIX(x) s6_##x
+#define SORT_INPUT_FB
+#define SORT_OUTPUT_FB
+#define SORT_UNIQUE
+#define SORT_INT64(k) (k).x
+
+#include "lib/sorter/sorter.h"
+
+static void
+test_int64(int mode, u64 size)
+{
+  u64 N = size ? nextprime(MIN(size/8, 0xffff0000)) : 0;
+  u64 K = N/4*3;
+  msg(L_INFO, ">>> 64-bit integers (%s, N=%llu)", ((char *[]) { "increasing", "decreasing", "random" })[mode], (long long)N);
+
+  struct fastbuf *f = bopen_tmp(65536);
+  for (u64 i=0; i<N; i++)
+    bputq(f, 777777*((mode==0) ? i : (mode==1) ? N-1-i : ((u64)i * K + 17) % N));
+  brewind(f);
+
+  start();
+  f = s6_sort(f, NULL, 777777*(N-1));
+  stop();
+
+  SORT_XTRACE(2, "Verifying");
+  for (u64 i=0; i<N; i++)
+    {
+      u64 j = bgetq(f);
+      if (777777*i != j)
+       die("Discrepancy: %llu instead of %llu", (long long)j, 777777*(long long)i);
+    }
+  bclose(f);
+}
+

 /*** Main ***/
 
 static void
 run_test(uns i, u64 size)
 {
 /*** Main ***/
 
 static void
 run_test(uns i, u64 size)
 {

+  test_id = i;

   switch (i)
     {
     case 0:
   switch (i)
     {
     case 0:


@@ -591,7 +643,13 @@ run_test(uns i, u64 size)
       test_graph(0, size); break;
     case 12:
       test_graph(1, size); break;
       test_graph(0, size); break;
     case 12:
       test_graph(1, size); break;

-#define TMAX 13
+    case 13:
+      test_int64(0, size); break;
+    case 14:
+      test_int64(1, size); break;
+    case 15:
+      test_int64(2, size); break;
+#define TMAX 16

     }
 }
 
     }
 }
 


@@ -614,9 +672,20 @@ main(int argc, char **argv)
          goto usage;
        break;
       case 't':
          goto usage;
        break;
       case 't':

-       t = atol(optarg);
-       if (t >= TMAX)
-         goto usage;
+         {
+           char *w[32];
+           int f = sepsplit(optarg, ',', w, ARRAY_SIZE(w));
+           if (f < 0)
+             goto usage;
+           t = 0;
+           for (int i=0; i<f; i++)
+             {
+               int j = atol(w[i]);
+               if (j >= TMAX)
+                 goto usage;
+               t |= 1 << j;
+             }
+         }

        break;
       case 'v':
        sorter_trace++;
        break;
       case 'v':
        sorter_trace++;


@@ -629,10 +698,8 @@ main(int argc, char **argv)
   if (optind != argc)
     goto usage;
 
   if (optind != argc)
     goto usage;
 

-  if (t != ~0U)
-    run_test(t, size);
-  else
-    for (uns i=0; i<TMAX; i++)
+  for (uns i=0; i<TMAX; i++)
+    if (t & (1 << i))

       run_test(i, size);
 
   return 0;
       run_test(i, size);
 
   return 0;