Added time_tool.sh to tools for quick timing.

Modified gf_methods to be a little more flexible.

2 files changed, 256 insertions, 81 deletions

diff --git a/tools/gf_methods.c b/tools/gf_methods.c
index 90ddd15..298c1ec 100644
--- a/tools/gf_methods.c
+++ b/tools/gf_methods.c
@@ -17,109 +17,189 @@
 #include "gf_method.h"
 #include "gf_int.h"
 
+#define BNMULTS (7)
+static char *BMULTS[BNMULTS] = { "CARRY_FREE", "GROUP48", 
+                               "TABLE", "LOG", "SPLIT4", "SPLIT88", "COMPOSITE" };
 #define NMULTS (16)
-static char *mults[NMULTS] = { "SHIFT", "CARRY_FREE", "GROUP44", "GROUP48", "BYTWO_p", "BYTWO_b",
+static char *MULTS[NMULTS] = { "CARRY_FREE", "GROUP44", "GROUP48", "BYTWO_p", "BYTWO_b",
                                "TABLE", "LOG", "LOG_ZERO", "LOG_ZERO_EXT", "SPLIT2",
                                "SPLIT4", "SPLIT8", "SPLIT16", "SPLIT88", "COMPOSITE" };
 
+/* Make sure CAUCHY is last */
+
 #define NREGIONS (7) 
-static char *regions[NREGIONS] = { "DOUBLE", "QUAD", "LAZY", "SSE", "NOSSE", 
+static char *REGIONS[NREGIONS] = { "DOUBLE", "QUAD", "LAZY", "SSE", "NOSSE", 
                                    "ALTMAP", "CAUCHY" };
 
+#define BNREGIONS (4) 
+static char *BREGIONS[BNREGIONS] = { "DOUBLE", "QUAD", "ALTMAP", "CAUCHY" };
+
 #define NDIVS (2)
 static char *divides[NDIVS] = { "MATRIX", "EUCLID" }; 
 
+void usage(char *s)
+{
+   fprintf(stderr, "usage: gf_methods w -BADCM -LUMDRB\n");
+   fprintf(stderr, "\n");
+   fprintf(stderr, "       w can be 1-32, 64, 128\n");
+   fprintf(stderr, "\n");
+   fprintf(stderr, "       -B lists basic methods that are useful\n");
+   fprintf(stderr, "       -A does a nearly exhaustive listing\n");
+   fprintf(stderr, "       -D adds EUCLID and MATRIX division\n");
+   fprintf(stderr, "       -C adds CAUCHY when possible\n");
+   fprintf(stderr, "       Combinations are fine.\n");
+   fprintf(stderr, "\n");
+   fprintf(stderr, "       -L Simply lists methods\n");
+   fprintf(stderr, "       -U Produces calls to gf_unit\n");
+   fprintf(stderr, "       -M Produces calls to time_tool.sh for single multiplications\n");
+   fprintf(stderr, "       -D Produces calls to time_tool.sh for single divisions\n");
+   fprintf(stderr, "       -R Produces calls to time_tool.sh for region multiplications\n");
+   fprintf(stderr, "       -B Produces calls to time_tool.sh for the fastest region multiplications\n");
+   fprintf(stderr, "       Cannot combine L, U, T.\n");
+   if (s != NULL) {
+     fprintf(stderr, "\n");
+     fprintf(stderr, "%s\n", s);
+   }
+   exit(1);
+}
 
 int main(int argc, char *argv[])
 {
-  int m, r, d, w, i, sa, j, k, reset;
-  char *gf_argv[50];
+  int m, r, d, w, i, sa, j, k, reset, ok;
+  int nregions;
+  int nmults;
+  char **regions;
+  char **mults;
+  int exhaustive = 0;
+  int divide = 0;
+  int cauchy = 0;
+  int listing;
+  char *gf_argv[50], *x;
   gf_t gf;
   char divs[200], ks[10], ls[10];
-  char * w_str = "w=%d:";
+  char * w_str;
 
-  if (argc == 2) {
-    if (!strcmp (argv[1], "-U")) {
-      w_str = "%d A -1";
+  if (argc != 4) usage(NULL);
+  w = atoi(argv[1]);
+  ok = (w >= 1 && w <= 32);
+  if (w == 64) ok = 1;
+  if (w == 128) ok = 1;
+  if (!ok) usage("Bad w");
+  
+  if (argv[2][0] != '-' || argv[3][0] != '-' || strlen(argv[2]) == 1 || strlen(argv[3]) != 2) {
+    usage(NULL);
+  }
+  for (i = 1; argv[2][i] != '\0'; i++) {
+    switch(argv[2][i]) {
+      case 'B': exhaustive = 0; break;
+      case 'A': exhaustive = 1; break;
+      case 'D': divide = 1; break;
+      case 'C': cauchy = 1; break;
+      default: usage("Bad -BADC");
     }
   }
 
-  for (i = 2; i < 8; i++) {
-    w = (1 << i);
-    gf_argv[0] = "-";
-    if (create_gf_from_argv(&gf, w, 1, gf_argv, 0) > 0) {
-      printf(w_str, w);
-      printf(" - \n");
-      gf_free(&gf, 1);
-    } else if (_gf_errno == GF_E_DEFAULT) {
-      fprintf(stderr, "Unlabeled failed method: w=%d: -\n", 2);
-      exit(1);
+  if (strchr("LUMDRB", argv[3][1]) == NULL) { usage("Bad -LUMDRB"); }
+  listing = argv[3][1];
+
+  if (listing == 'U') {
+    w_str = "../test/gf_unit %d A -1";
+  } else if (listing == 'L') {
+    w_str = "w=%d:";
+  } else {
+    w_str = strdup("sh time_tool.sh X %d");
+    x = strchr(w_str, 'X');
+    *x = listing;
+  }
+
+  gf_argv[0] = "-";
+  if (create_gf_from_argv(&gf, w, 1, gf_argv, 0) > 0) {
+    printf(w_str, w);
+    printf(" - \n");
+    gf_free(&gf, 1);
+  } else if (_gf_errno == GF_E_DEFAULT) {
+    fprintf(stderr, "Unlabeled failed method: w=%d: -\n", 2);
+    exit(1);
+  }
+
+  nregions = (exhaustive) ? NREGIONS : BNREGIONS;
+  if (!cauchy) nregions--;
+  regions = (exhaustive) ? REGIONS : BREGIONS;
+  mults = (exhaustive) ? MULTS : BMULTS;
+  nmults = (exhaustive) ? NMULTS : BNMULTS;
+
+
+  for (m = 0; m < nmults; m++) {
+    sa = 0;
+    gf_argv[sa++] = "-m";
+    if (strcmp(mults[m], "GROUP44") == 0) {
+      gf_argv[sa++] = "GROUP";
+      gf_argv[sa++] = "4";
+      gf_argv[sa++] = "4";
+    } else if (strcmp(mults[m], "GROUP48") == 0) {
+      gf_argv[sa++] = "GROUP";
+      gf_argv[sa++] = "4";
+      gf_argv[sa++] = "8";
+    } else if (strcmp(mults[m], "SPLIT2") == 0) {
+      gf_argv[sa++] = "SPLIT";
+      sprintf(ls, "%d", w);
+      gf_argv[sa++] = ls;
+      gf_argv[sa++] = "2";
+    } else if (strcmp(mults[m], "SPLIT4") == 0) {
+      gf_argv[sa++] = "SPLIT";
+      sprintf(ls, "%d", w);
+      gf_argv[sa++] = ls;
+      gf_argv[sa++] = "4";
+    } else if (strcmp(mults[m], "SPLIT8") == 0) {
+      gf_argv[sa++] = "SPLIT";
+      sprintf(ls, "%d", w);
+      gf_argv[sa++] = ls;
+      gf_argv[sa++] = "8";
+    } else if (strcmp(mults[m], "SPLIT16") == 0) {
+      gf_argv[sa++] = "SPLIT";
+      sprintf(ls, "%d", w);
+      gf_argv[sa++] = ls;
+      gf_argv[sa++] = "16";
+    } else if (strcmp(mults[m], "SPLIT88") == 0) {
+      gf_argv[sa++] = "SPLIT";
+      gf_argv[sa++] = "8";
+      gf_argv[sa++] = "8";
+    } else if (strcmp(mults[m], "COMPOSITE") == 0) {
+      gf_argv[sa++] = "COMPOSITE";
+      gf_argv[sa++] = "2";
+      gf_argv[sa++] = "-";
+    } else {
+      gf_argv[sa++] = mults[m];
     }
+    reset = sa;
 
-    for (m = 0; m < NMULTS; m++) {
-      sa = 0;
-      gf_argv[sa++] = "-m";
-      if (strcmp(mults[m], "GROUP44") == 0) {
-        gf_argv[sa++] = "GROUP";
-        gf_argv[sa++] = "4";
-        gf_argv[sa++] = "4";
-      } else if (strcmp(mults[m], "GROUP48") == 0) {
-        gf_argv[sa++] = "GROUP";
-        gf_argv[sa++] = "4";
-        gf_argv[sa++] = "8";
-      } else if (strcmp(mults[m], "SPLIT2") == 0) {
-        gf_argv[sa++] = "SPLIT";
-        sprintf(ls, "%d", w);
-        gf_argv[sa++] = ls;
-        gf_argv[sa++] = "2";
-      } else if (strcmp(mults[m], "SPLIT4") == 0) {
-        gf_argv[sa++] = "SPLIT";
-        sprintf(ls, "%d", w);
-        gf_argv[sa++] = ls;
-        gf_argv[sa++] = "4";
-      } else if (strcmp(mults[m], "SPLIT8") == 0) {
-        gf_argv[sa++] = "SPLIT";
-        sprintf(ls, "%d", w);
-        gf_argv[sa++] = ls;
-        gf_argv[sa++] = "8";
-      } else if (strcmp(mults[m], "SPLIT16") == 0) {
-        gf_argv[sa++] = "SPLIT";
-        sprintf(ls, "%d", w);
-        gf_argv[sa++] = ls;
-        gf_argv[sa++] = "16";
-      } else if (strcmp(mults[m], "SPLIT88") == 0) {
-        gf_argv[sa++] = "SPLIT";
-        gf_argv[sa++] = "8";
-        gf_argv[sa++] = "8";
-      } else if (strcmp(mults[m], "COMPOSITE") == 0) {
-        gf_argv[sa++] = "COMPOSITE";
-        gf_argv[sa++] = "2";
-        gf_argv[sa++] = "-";
-      } else {
-        gf_argv[sa++] = mults[m];
-      }
-      reset = sa;
-      for (r = 0; r < (1 << NREGIONS); r++) {
-        sa = reset;
-        for (k = 0; k < NREGIONS; k++) {
-          if (r & 1 << k) {
-            gf_argv[sa++] = "-r";
-            gf_argv[sa++] = regions[k];
-          }
-        }
-        gf_argv[sa++] = "-";
-        if (create_gf_from_argv(&gf, w, sa, gf_argv, 0) > 0) {
-          printf(w_str, w);
-          for (j = 0; j < sa; j++) printf(" %s", gf_argv[j]);
-          printf("\n");
-          gf_free(&gf, 1);
-        } else if (_gf_errno == GF_E_DEFAULT) {
-          fprintf(stderr, "Unlabeled failed method: w=%d:", w);
-          for (j = 0; j < sa; j++) fprintf(stderr, " %s", gf_argv[j]);
-          fprintf(stderr, "\n");
-          exit(1);
+    for (r = 0; r < (1 << nregions); r++) {
+      sa = reset;
+      for (k = 0; k < nregions; k++) {
+        if (r & (1 << k)) {
+          gf_argv[sa++] = "-r";
+          gf_argv[sa++] = regions[k];
         }
-        sa--;
+      }
+      gf_argv[sa++] = "-";
+      /*
+      printf("Hmmmm. %s", gf_argv[0]);
+      for (j = 0; j < sa; j++) printf(" %s", gf_argv[j]);
+      printf("\n"); */
+  
+      if (create_gf_from_argv(&gf, w, sa, gf_argv, 0) > 0) {
+        printf(w_str, w);
+        for (j = 0; j < sa; j++) printf(" %s", gf_argv[j]);
+        printf("\n");
+        gf_free(&gf, 1);
+      } else if (_gf_errno == GF_E_DEFAULT) {
+        fprintf(stderr, "Unlabeled failed method: w=%d:", w);
+        for (j = 0; j < sa; j++) fprintf(stderr, " %s", gf_argv[j]);
+        fprintf(stderr, "\n");
+        exit(1);
+      }
+      sa--;
+      if (divide) {
         for (d = 0; d < NDIVS; d++) {
           gf_argv[sa++] = "-d";
           gf_argv[sa++] = divides[d];
diff --git a/tools/time_tool.sh b/tools/time_tool.sh
new file mode 100644
index 0000000..d2aa591
--- /dev/null
+++ b/tools/time_tool.sh
@@ -0,0 +1,95 @@
+# time_tool.sh - Shell script to test various timings.  
+# This is a rough tester -- its job is to work quickly rather than precisely.
+# (Jim Plank)
+
+#!/bin/sh
+
+if [ $# -lt 3 ]; then
+  echo 'usage sh time_tool.sh M|D|R|B w method' >&2
+  exit 1
+fi
+
+op=$1
+w=$2
+
+shift ; shift
+
+method="$*"
+
+if [ $op != M -a $op != D -a $op != R -a $op != B ]; then
+  echo 'usage sh time_tool.sh M|D|R|B w method' >&2
+  echo 'You have to specify a test: ' >&2 
+  echo '  M=Multiplication' >&2 
+  echo '  D=Division' >&2 
+  echo '  R=Regions' >&2 
+  echo '  B=Best-Region' >&2 
+  exit 1
+fi
+
+# First, use a 16K buffer to test the performance of single multiplies.
+
+fac=`echo $w | awk '{ n = $1; while (n != 0 && n%2==0) n /= 2; print n }'`
+if [ $fac -eq 0 ]; then
+  echo 'usage sh time_tool.sh M|D|R|B w method' >&2
+  echo 'Bad w' >&2
+  exit 1
+fi
+
+bsize=16384
+bsize=`echo $bsize $fac | awk '{ print $1 * $2 }'`
+
+if [ `./gf_time $w M -1 $bsize 1 $method 2>&1 | wc | awk '{ print $1 }'` -gt 2 ]; then
+  echo 'usage sh time_tool.sh w method' >&2
+  echo "Bad method"
+  exit 1
+fi
+
+if [ $op = M -o $op = D ]; then
+  iter=1
+  c1=`./gf_time $w $op -1 $bsize $iter $method`
+  t=`echo $c1 | awk '{ printf "%d\n", $4*1000 }'`
+  s=`echo $c1 | awk '{ print $8 }'`
+  bs=$s
+  
+  while [ $t -lt 1 ]; do
+    bs=$s
+    iter=`echo $iter | awk '{ print $1*2 }'`
+    c1=`./gf_time $w $op -1 $bsize $iter $method`
+    t=`echo $c1 | awk '{ printf "%d\n", $4*1000 }'`
+    s=`echo $c1 | awk '{ print $8 }'`
+  done
+  
+  echo "$op speed (MB/s): " $bs "    W-Method:" $w $method 
+  exit 0
+fi
+  
+bsize=16384
+bsize=`echo $bsize $fac | awk '{ print $1 * $2 }'`
+
+best=0
+while [ $bsize -le 4194304 ]; do
+  iter=1
+  c1=`./gf_time $w G -1 $bsize $iter $method`
+  t=`echo $c1 | awk '{ printf "%d\n", $6*1000 }'`
+  s=`echo $c1 | awk '{ print $10 }'`
+  bs=$s
+
+  while [ $t -lt 1 ]; do
+    bs=$s
+    iter=`echo $iter | awk '{ print $1*2 }'`
+    c1=`./gf_time $w G -1 $bsize $iter $method`
+    t=`echo $c1 | awk '{ printf "%d\n", $6*1000 }'`
+    s=`echo $c1 | awk '{ print $10 }'`
+  done
+  if [ $bsize -lt 1048576 ]; then
+    str=`echo $bsize | awk '{ printf "%3dK\n", $1/1024 }'`
+  else 
+    str=`echo $bsize | awk '{ printf "%3dM\n", $1/1024/1024 }'`
+  fi
+  if [ $op = R ]; then
+    echo "Region Buffer-Size: $str (MB/s): " $bs "    W-Method:" $w $method 
+  fi
+  best=`echo $best $bs | awk '{ print ($1 > $2) ? $1 : $2 }'`
+  bsize=`echo $bsize | awk '{ print $1 * 2 }'`
+done
+echo "Region Best (MB/s): "$best "    W-Method:" $w $method