From: Mark Wooding <mdw@distorted.org.uk>
Date: Wed, 12 Sep 2018 10:41:49 +0000 (+0100)
Subject: mm.c (rate): Simplify the algorithm.
X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/mm/commitdiff_plain/44e8ae5a663f4ece6982dce93b7f4018d71ef764?ds=sidebyside

mm.c (rate): Simplify the algorithm.

Now we don't need to take a copy of the code histogram, and there's less
conditional stuff to do in the loop.  This gives an overall 25%
performance improvement, as measured by running `time mm -a 4 8'.
---

diff --git a/mm.c b/mm.c
index 16f635b..2176e33 100644
--- a/mm.c
+++ b/mm.c
@@ -70,12 +70,10 @@ typedef struct mm {
  *   * %$t$% is temporary work space for the rating function.
  *
  * The rating function works by taking a pass over the guess, computing a
- * count table %$v'$%; but for each guess symbol which matches the
- * corresponding code symbol, decrementing the count %$v_i$% for that symbol
- * (in a temporary copy of the table %$v$%).  The black count is then the
- * number of such matches, and the white count is given by
+ * count table %$v'$%.  The black count %$b$% is then the number of such
+ * matches, and the white count is given by
  *
- *   %$w = \displaystyle \sum_{0<i\le n} \min(v_i, v'_i).$%
+ *   %$w = \displaystyle \sum_{0<i\le n} \min(v_i, v'_i) - b.$%
  *
  * Thus, the work is %$O(k + n)$%, rather than the %$O(k^2)$% for a
  * %%na\"\i{}ve%% implementation.
@@ -94,7 +92,7 @@ static ratectx *rate_alloc(const mm *m)
   dig *v;
 
   r = CREATE(ratectx);
-  v = xmalloc((3 * m->n + m->k) * sizeof(dig));
+  v = xmalloc((2 * m->n + m->k) * sizeof(dig));
   r->m = *m;
   r->v = v;
   r->s = r->v + m->n;
@@ -125,24 +123,18 @@ static void rate(const ratectx *r, const dig *g, unsigned  *b, unsigned *w)
   unsigned i;
   unsigned k = r->m.k, n = r->m.n;
   dig *v = r->t;
-  dig *vv = v + n;
   const dig *s = r->s;
   unsigned bb = 0, ww = 0;
 
   memset(v, 0, n * sizeof(dig));
-  memcpy(vv, r->v, n * sizeof(dig));
   for (i = 0; i < k; i++) {
-    if (g[i] != s[i])
-      v[g[i]]++;
-    else {
-      vv[g[i]]--;
-      bb++;
-    }
+    if (g[i] == s[i]) bb++;
+    v[g[i]]++;
   }
   for (i = 0; i < n; i++)
-    ww += v[i] < vv[i] ? v[i] : vv[i];
+    ww += v[i] < r->v[i] ? v[i] : r->v[i];
   *b = bb;
-  *w = ww;
+  *w = ww - bb;
 }
 
 static void rate_free(ratectx *r) { xfree(r->v); DESTROY(r); }