Performance improvement for gendata_cocsep

5 files changed, 185 insertions, 23 deletions

diff --git a/.gitignore b/.gitignore
index d47841b..0191ea5 100644
--- a/.gitignore
+++ b/.gitignore
@@ -7,3 +7,4 @@ test/*/runtest
 test/run
 test/last.*
 *.o
+*.s
diff --git a/Makefile b/Makefile
index 4afb030..c51be91 100644
--- a/Makefile
+++ b/Makefile
@@ -2,6 +2,9 @@ include config.mk
 
 all: cube.o debugcube.o
 
+cube.s: clean
+        ${CC} -D${CUBETYPE} ${CFLAGS} -c -S -o cube.s cube.c
+
 cube.o: clean
         ${CC} -D${CUBETYPE} ${CFLAGS} -c -o cube.o cube.c
 
diff --git a/TODO.txt b/TODO.txt
index 7cb5169..e0ea12d 100644
--- a/TODO.txt
+++ b/TODO.txt
@@ -1,4 +1,3 @@
-TODO optimize cocsep generation (very slow!)
 TODO check which is faster: foreach_move or simple for loop?
      same for transformations
 TODO implement big pruning table for H48 solver
diff --git a/cube.c b/cube.c
index c3c03f8..c3f2b6a 100644
--- a/cube.c
+++ b/cube.c
@@ -1075,6 +1075,7 @@ previous sections, while some other operate directly on the cube.
         invertco_fast(compose_fast(compose_fast(_trans_cube_ ## T, c), \
         _trans_cube_ ## T ## _inverse))
 
+/*
 #define _foreach_move(_m, _c, _d, instruction) \
         _m = U;  _d = _move(U,  _c); instruction \
         _m = U2; _d = _move(U2, _c); instruction \
@@ -1094,10 +1095,9 @@ previous sections, while some other operate directly on the cube.
         _m = B;  _d = _move(B,  _c); instruction \
         _m = B2; _d = _move(B2, _c); instruction \
         _m = B3; _d = _move(B3, _c); instruction
-/*
+*/
 #define _foreach_move(_m, _c, _d, instruction) \
         for (_m = 0; _m < 18; _m++) { _d = move(_c, _m); instruction }
-*/
 
 cube_t solvedcube(void);
 bool isconsistent(cube_t);
@@ -1867,7 +1867,8 @@ Section: auxiliary procedures for H48 optimal solver (temporary)
 ******************************************************************************/
 
 _static size_t gendata_cocsep(void *);
-_static uint32_t dfs_cocsep(cube_fast_t, uint8_t, uint8_t, uint16_t *, uint32_t *);
+_static uint32_t dfs_cocsep(
+    cube_fast_t, uint8_t, uint8_t, uint16_t *, uint32_t *, bool *);
 
 /*
 Each element of the cocsep table is a uint32_t used as follows:
@@ -1883,33 +1884,36 @@ After the data as described above, more auxiliary information is appended:
 _static size_t
 gendata_cocsep(void *buf)
 {
+        static size_t tablesize = _3p7 << 7U;
+
+        cube_fast_t solved;
         uint32_t *buf32, cc;
         uint16_t n;
         uint8_t i, j;
-        size_t tablesize;
-
-        tablesize = _3p7 << 7U;
+        bool visited[tablesize];
 
         buf32 = (uint32_t *)buf;
         memset(buf32, 0xFFU, 4*tablesize);
         memset(buf32 + tablesize, 0, 21*4);
 
-        for (i = 0, n = 0, cc = 0; cc != 0 || i == 0; i++) {
+        solved = cubetofast(solvedcube());
+        buf32[tablesize+1] = 9U; /* Known max pruning value */
+        for (i = 0, n = 0, cc = 0; i < 10; i++) {
+                memset(visited, 0, tablesize); /* Set visited bit for dfs */
                 DBG_LOG("gendata_cocsep: generating depth %" PRIu8 "\n", i);
-                cc = dfs_cocsep(cubetofast(solvedcube()), 0, i, &n, buf32);
+                cc = dfs_cocsep(solved, 0, i, &n, buf32, visited);
                 buf32[tablesize+i+2] = cc;
                 DBG_LOG("found %" PRIu32 "\n", cc);
         }
         buf32[tablesize] = (uint32_t)n;
-        buf32[tablesize+1] = (uint32_t)(i-2);
 
         DBG_LOG("cocsep data computed, %" PRIu32 " symmetry classes\n", n);
         DBG_LOG("Maximum pruning value: %" PRIu32 "\n", buf32[tablesize+1]);
         DBG_LOG("Pruning value distribution:\n");
-        for (j = 0; j < i-1; j++)
+        for (j = 0; j < 10; j++)
                 DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, buf32[tablesize+j+2]);
 
-        return 4*(tablesize + i + 1);
+        return 4*(tablesize + 12);
 }
 
 _static uint32_t
@@ -1918,25 +1922,31 @@ dfs_cocsep(
         uint8_t depth,
         uint8_t maxdepth,
         uint16_t *n,
-        uint32_t *buf32
+        uint32_t *buf32,
+        bool *visited
 )
 {
         uint8_t m, t, tinv, olddepth;
-        uint32_t cc, oldvalue;
+        uint32_t cc;
         uint64_t i;
         cube_fast_t d;
 
-        oldvalue = buf32[coord_fast_cocsep(c)];
+        i = coord_fast_cocsep(c);
+        olddepth = (uint8_t)(buf32[i] & 0xFFU);
+        if (olddepth < depth || visited[i])
+                return 0;
+        visited[i] = true;
+
         if (depth == maxdepth) {
-                if ((oldvalue & 0xFFU) != 0xFFU)
+                if ((buf32[i] & 0xFFU) != 0xFFU)
                         return 0;
 
                 for (t = 0, cc = 0; t < 48; t++) {
                         d = transform(c, t);
                         i = coord_fast_cocsep(d);
+                        visited[i] = true;
                         tinv = inverse_trans(t);
-                        if ((buf32[i] & 0xFFU) == 0xFFU)
-                                cc++;
+                        cc += (buf32[i] & 0xFFU) == 0xFFU;
                         buf32[i] = (*n << 16U) | (tinv << 8U) | depth;
                 }
                 (*n)++;
@@ -1944,13 +1954,9 @@ dfs_cocsep(
                 return cc;
         }
 
-        olddepth = (uint8_t)(oldvalue & 0xFFU);
-        if (olddepth != depth)
-                return 0;
-
         cc = 0;
         _foreach_move(m, c, d,
-                cc += dfs_cocsep(d, depth+1, maxdepth, n, buf32);
+                cc += dfs_cocsep(d, depth+1, maxdepth, n, buf32, visited);
         )
 
         return cc;
diff --git a/old/gendata_bfs_attempt.c b/old/gendata_bfs_attempt.c
new file mode 100644
index 0000000..4cd5ae9
--- /dev/null
+++ b/old/gendata_bfs_attempt.c
@@ -0,0 +1,153 @@
+_static size_t gendata_cocsep(void *);
+_static uint32_t dfs_cocsep(cube_fast_t, uint8_t, uint8_t, uint32_t *);
+
+/*
+Each element of the cocsep table is a uint32_t used as follows:
+  - Lowest 8-bit block: pruning value
+  - Second-lower 8-bit block: "ttrep" (transformation to representative)
+  - Top 16-bit block: symcoord value
+After the data as described above, more auxiliary information is appended:
+  - A uint32_t representing the number of symmetry classes
+  - A uint32_t representing the highest value of the pruning table
+  - One uint32_t for each "line" of the pruning table, representing the number
+    of positions having that pruning value.
+*/
+_static size_t
+gendata_cocsep(void *buf)
+{
+        uint32_t *buf32, cc;
+        uint64_t i64;
+        uint16_t n;
+        uint8_t i, j;
+        size_t tablesize;
+
+        tablesize = _3p7 << 7U;
+
+        buf32 = (uint32_t *)buf;
+        memset(buf32, 0xFFU, 4*tablesize);
+        memset(buf32 + tablesize, 0, 21*4);
+
+/* New impl BFS
+
+        uint32_t nold = 0, nnew = 0;
+        uint64_t coord;
+        uint8_t m, olddepth;
+        cube_fast_t c, d, oldlevel[100000], newlevel[100000];
+        newlevel[0] = cubetofast(solvedcube());
+        nnew = 1;
+        buf32[coord_fast_cocsep(newlevel[0])] = UFr << 8U;
+        n = 1;
+        DBG_LOG("gendata_cocsep: found 1 position at depth 0\n");
+        for (i = 1; i < 10; i++) {
+                DBG_LOG("gendata_cocsep: generating depth %" PRIu8 "\n", i);
+                memcpy(oldlevel, newlevel, nnew * sizeof(cube_fast_t));
+                nold = nnew;
+                nnew = 0;
+                for (j = 0; j < nold; j++) {
+                        _foreach_move(m, oldlevel[j], newlevel[nnew],
+                                coord = coord_fast_cocsep(newlevel[nnew]);
+                                olddepth = buf32[coord] & 0xFFU;
+                                buf32[coord] = i;
+                                nnew += olddepth > i;
+                        )
+                }
+                DBG_LOG("found %" PRIu32 "\n", nnew);
+        }
+
+End new impl BFS */
+
+        /* Pruning values */
+        buf32[tablesize+1] = 9U; /* Known max pruning value */
+        for (i = 0, cc = 0; i < 10; i++) {
+                DBG_LOG("gendata_cocsep: generating depth %" PRIu8 "\n", i);
+                cc = dfs_cocsep(cubetofast(solvedcube()), 0, i, buf32);
+                buf32[tablesize+i+2] = cc;
+                DBG_LOG("found %" PRIu32 "\n", cc);
+        }
+
+        /* Symmetries */
+        for (i64 = 0, n = 0; i64 < tablesize; i64++) {
+        }
+        buf32[tablesize] = (uint32_t)n;
+
+        DBG_LOG("cocsep data computed, %" PRIu32 " symmetry classes\n", n);
+        DBG_LOG("Maximum pruning value: %" PRIu32 "\n", buf32[tablesize+1]);
+        DBG_LOG("Pruning value distribution:\n");
+        for (j = 0; j < 10; j++)
+                DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, buf32[tablesize+j+2]);
+
+        return 4*(tablesize + 11);
+}
+
+_static uint32_t
+dfs_cocsep(cube_fast_t c, uint8_t depth, uint8_t maxdepth, uint32_t *buf32)
+{
+        uint8_t m, olddepth;
+        uint32_t update, cc;
+        uint64_t i;
+        cube_fast_t d;
+
+        i = coord_fast_cocsep(c);
+        olddepth = (uint8_t)(buf32[i] & 0xFFU);
+        if (olddepth < depth)
+                return 0;
+
+        if (depth == maxdepth) {
+                update = (buf32[i] & 0xFFU) == 0xFFU;
+                buf32[i] = depth;
+                return update;
+        }
+
+        cc = 0;
+        _foreach_move(m, c, d,
+                cc += dfs_cocsep(d, depth+1, maxdepth, buf32);
+        )
+
+        return cc;
+}
+
+/*
+_static uint32_t
+dfs_cocsep(
+        cube_fast_t c,
+        uint8_t depth,
+        uint8_t maxdepth,
+        uint16_t *n,
+        uint32_t *buf32
+)
+{
+        uint8_t m, t, tinv, olddepth;
+        uint32_t cc, oldvalue;
+        uint64_t i;
+        cube_fast_t d;
+
+        oldvalue = buf32[coord_fast_cocsep(c)];
+        if (depth == maxdepth) {
+                if ((oldvalue & 0xFFU) != 0xFFU)
+                        return 0;
+
+                for (t = 0, cc = 0; t < 48; t++) {
+                        d = transform(c, t);
+                        i = coord_fast_cocsep(d);
+                        tinv = inverse_trans(t);
+                        if ((buf32[i] & 0xFFU) == 0xFFU)
+                                cc++;
+                        buf32[i] = (*n << 16U) | (tinv << 8U) | depth;
+                }
+                (*n)++;
+
+                return cc;
+        }
+
+        olddepth = (uint8_t)(oldvalue & 0xFFU);
+        if (olddepth != depth)
+                return 0;
+
+        cc = 0;
+        _foreach_move(m, c, d,
+                cc += dfs_cocsep(d, depth+1, maxdepth, n, buf32);
+        )
+
+        return cc;
+}
+*/