Merge branch 'sebastianotronto:master' into master

1 files changed, 230 insertions, 136 deletions

diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h
index 2a62b1d..3445570 100644
--- a/src/solvers/h48/gendata_h48.h
+++ b/src/solvers/h48/gendata_h48.h
@@ -33,6 +33,7 @@ _t by _ttrep).
 typedef struct {
         uint8_t h;
         uint8_t k;
+        uint8_t base;
         uint8_t maxdepth;
         tableinfo_t info;
         void *buf;
@@ -56,6 +57,12 @@ typedef struct {
         uint8_t *table;
         uint64_t *selfsim;
         cube_t *crep;
+        uint64_t start;
+        uint64_t end;
+        uint64_t count;
+        uint64_t *distribution;
+        pthread_mutex_t *distribution_mutex;
+        pthread_mutex_t *table_mutex[CHUNKS];
 } h48h0k4_bfs_arg_t;
 
 typedef struct {
@@ -75,17 +82,28 @@ typedef struct {
         uint64_t *count;
 } h48k2_dfs_arg_t;
 
+typedef struct {
+        cube_t cube;
+        int8_t depth;
+        uint8_t h;
+        uint8_t k;
+        uint32_t *cocsepdata;
+        uint64_t *selfsim;
+        uint8_t *table;
+        pthread_mutex_t **table_mutex;
+} gendata_h48_mark_t;
+
 STATIC uint64_t gendata_h48short(gendata_h48short_arg_t *);
 STATIC size_t gendata_h48(gendata_h48_arg_t *);
 STATIC size_t gendata_h48h0k4(gendata_h48_arg_t *);
-STATIC int64_t gendata_h48h0k4_bfs(h48h0k4_bfs_arg_t *);
-STATIC int64_t gendata_h48h0k4_bfs_fromdone(h48h0k4_bfs_arg_t *);
-STATIC int64_t gendata_h48h0k4_bfs_fromnew(h48h0k4_bfs_arg_t *);
 STATIC size_t gendata_h48k2(gendata_h48_arg_t *);
-STATIC void * gendata_h48k2_runthread(void *);
-STATIC_INLINE void gendata_h48k2_mark(cube_t, int8_t, h48k2_dfs_arg_t *);
-STATIC_INLINE bool gendata_h48k2_dfs_stop(cube_t, uint8_t, h48k2_dfs_arg_t *);
+STATIC void * gendata_h48h0k4_runthread(void *);
+STATIC_INLINE uint64_t gendata_h48_mark(gendata_h48_mark_t *);
+STATIC_INLINE bool gendata_h48k2_dfs_stop(cube_t, int8_t, h48k2_dfs_arg_t *);
+STATIC size_t gendata_h48k2_realcoord(gendata_h48_arg_t *);
 STATIC void gendata_h48k2_dfs(h48k2_dfs_arg_t *arg);
+STATIC void * gendata_h48k2_runthread(void *);
+STATIC tableinfo_t makeinfo_h48k2(gendata_h48_arg_t *, uint8_t);
 
 STATIC uint32_t *get_cocsepdata_ptr(const void *);
 STATIC uint8_t *get_h48data_ptr(const void *);
@@ -147,8 +165,12 @@ gendata_h48(gendata_h48_arg_t *arg)
         arg->cocsepdata = (uint32_t *)cocsepdata_offset;
         arg->h48buf = (char *)arg->buf + cocsepsize;
 
+        arg->base = 99; // TODO: set this somewhere else
+
         if (arg->h == 0 && arg->k == 4) {
                 h48size = gendata_h48h0k4(arg);
+        } else if ((arg->h == 0 || arg->h == 11) && arg->k == 2) {
+                h48size = gendata_h48k2_realcoord(arg);
         } else if (arg->k == 2) {
                 h48size = gendata_h48k2(arg);
         } else {
@@ -179,17 +201,15 @@ gendata_h48_error:
         return 0;
 }
 
-/*
-TODO description
-generating fixed table with h=0, k=4
-*/
 STATIC size_t
 gendata_h48h0k4(gendata_h48_arg_t *arg)
 {
-        uint32_t j;
         uint8_t *table;
-        h48h0k4_bfs_arg_t bfsarg;
-        int64_t sc, cc, done, h48max;
+        int64_t sc, done, d, h48max;
+        uint64_t t, tt, isize, cc;
+        h48h0k4_bfs_arg_t bfsarg[THREADS];
+        pthread_t thread[THREADS];
+        pthread_mutex_t distribution_mutex, table_mutex[CHUNKS];
 
         if (arg->buf == NULL)
                 goto gendata_h48h0k4_return_size;
@@ -216,109 +236,134 @@ gendata_h48h0k4(gendata_h48_arg_t *arg)
         sc = coord_h48(SOLVED_CUBE, arg->cocsepdata, 0);
         set_h48_pval(table, sc, 4, 0);
         arg->info.distribution[0] = 1;
-        bfsarg = (h48h0k4_bfs_arg_t) {
-                .cocsepdata = arg->cocsepdata,
-                .table = table,
-                .selfsim = arg->selfsim,
-                .crep = arg->crep
-        };
-        for (
-                done = 1, bfsarg.depth = 1, cc = 0;
-                done < h48max && bfsarg.depth <= arg->maxdepth;
-                bfsarg.depth++
-        ) {
-                LOG("h48: generating depth %" PRIu8 "\n", bfsarg.depth);
-                cc = gendata_h48h0k4_bfs(&bfsarg);
-                done += cc;
-                arg->info.distribution[bfsarg.depth] = cc;
-                LOG("found %" PRId64 "\n", cc);
+
+        isize = h48max / THREADS;
+        isize = (isize / H48_COEFF(arg->k)) * H48_COEFF(arg->k);
+        pthread_mutex_init(&distribution_mutex, NULL);
+        for (t = 0; t < CHUNKS; t++)
+                pthread_mutex_init(&table_mutex[t], NULL);
+        for (t = 0; t < THREADS; t++) {
+                bfsarg[t] = (h48h0k4_bfs_arg_t) {
+                        .cocsepdata = arg->cocsepdata,
+                        .table = table,
+                        .selfsim = arg->selfsim,
+                        .crep = arg->crep,
+                        .start = isize * t,
+                        .end = t == THREADS-1 ? (uint64_t)h48max : isize * (t+1),
+                        .distribution = arg->info.distribution,
+                        .distribution_mutex = &distribution_mutex,
+                };
+                for (tt = 0; tt < CHUNKS; tt++)
+                        bfsarg[t].table_mutex[tt] = &table_mutex[tt];
         }
+        for (done = 1, d = 1; done < h48max && d <= arg->maxdepth; d++) {
+                LOG("h48: generating depth %" PRIu8 "\n", d);
+
+                for (t = 0; t < THREADS; t++) {
+                        bfsarg[t].depth = d;
+                        bfsarg[t].count = 0;
+                        pthread_create(&thread[t], NULL,
+                            gendata_h48h0k4_runthread, &bfsarg[t]);
+                }
 
-        arg->info.maxvalue = bfsarg.depth-1;
+                for (t = 0, cc = 0; t < THREADS; t++) {
+                        pthread_join(thread[t], NULL);
+                        cc += bfsarg[t].count;
+                }
 
-        LOG("h48 pruning table computed\n");
-        LOG("Maximum pruning value: %" PRIu32 "\n", arg->info.maxvalue);
-        LOG("Pruning value distribution:\n");
-        for (j = 0; j <= arg->info.maxvalue; j++)
-                LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, arg->info.distribution[j]);
+                done += cc;
+                arg->info.distribution[d] = cc;
 
+                LOG("found %" PRId64 "\n", cc);
+        }
+
+        arg->info.maxvalue = d - 1;
         writetableinfo(&arg->info, arg->h48buf);
 
 gendata_h48h0k4_return_size:
         return H48_TABLESIZE(0, 4) + INFOSIZE;
 }
 
-STATIC int64_t
-gendata_h48h0k4_bfs(h48h0k4_bfs_arg_t *arg)
-{
-        const uint8_t breakpoint = 10; /* Hand-picked optimal */
+/*
+TODO: the following function suffers from a big performance loss (about 40%)
+because of all the mutex locking. It is possible to reduce the first lock
+(at the beginning of the outermost for loop) by caching the next few items at
+once and then looping over the cached elements. But for the second one (inner
+loop) the access is non-sequential, so this cannot be done.
 
-        if (arg->depth < breakpoint)
-                return gendata_h48h0k4_bfs_fromdone(arg);
-        else
-                return gendata_h48h0k4_bfs_fromnew(arg);
-}
+However, in both cases in theory we do not care if we are reading the old
+value or the updated one. Depending on the compiler guarantees on concurrent
+memory access, we may be fine just removing the locks altogether.
 
-STATIC int64_t
-gendata_h48h0k4_bfs_fromdone(h48h0k4_bfs_arg_t *arg)
+It is probably possible to solve part of this by using atomics.
+*/
+STATIC void *
+gendata_h48h0k4_runthread(void *arg)
 {
-        uint8_t c, m, x;
-        uint32_t cc;
-        int64_t i, j, k;
+        static const uint8_t breakpoint = 10; /* Hand-picked optimal */
+
+        uint8_t c, m;
+        uint64_t i, d, mutex;
+        int64_t j;
         cube_t cube, moved;
+        gendata_h48_mark_t markarg;
+        h48h0k4_bfs_arg_t *bfsarg;
 
-        for (i = 0, cc = 0; i < (int64_t)H48_COORDMAX(0); i++) {
-                c = get_h48_pval(arg->table, i, 4);
-                if (c != arg->depth - 1)
-                        continue;
-                cube = invcoord_h48(i, arg->crep, 0);
-                for (m = 0; m < 18; m++) {
-                        moved = move(cube, m);
-                        j = coord_h48(moved, arg->cocsepdata, 0);
-                        if (get_h48_pval(arg->table, j, 4) <= arg->depth)
-                                continue;
-                        FOREACH_H48SIM(moved, arg->cocsepdata, arg->selfsim,
-                                k = coord_h48(moved, arg->cocsepdata, 0);
-                                x = get_h48_pval(arg->table, k, 4);
-                                set_h48_pval(arg->table, k, 4, arg->depth);
-                                cc += x != arg->depth;
-                        )
-                }
-        }
+        bfsarg = (h48h0k4_bfs_arg_t *)arg;
 
-        return cc;
-}
+        markarg = (gendata_h48_mark_t) {
+                .depth = bfsarg->depth,
+                .h = 0,
+                .k = 4,
+                .cocsepdata = bfsarg->cocsepdata,
+                .selfsim = bfsarg->selfsim,
+                .table = bfsarg->table,
+                .table_mutex = bfsarg->table_mutex,
+        };
 
-STATIC int64_t
-gendata_h48h0k4_bfs_fromnew(h48h0k4_bfs_arg_t *arg)
-{
-        uint8_t c, m, x;
-        uint32_t cc;
-        int64_t i, j;
-        cube_t cube, moved;
+        /*
+         * If depth < breakpoint, scan all neighbors of coordinates at depth-1.
+         * Otherwise, scan all neighbors of unvisited coordinates.
+         */
+        for (i = bfsarg->start, d = 0; i < bfsarg->end; i++) {
+                mutex = H48_INDEX(i, 4) % CHUNKS;
+                pthread_mutex_lock(bfsarg->table_mutex[mutex]);
+                c = get_h48_pval(bfsarg->table, i, 4);
+                pthread_mutex_unlock(bfsarg->table_mutex[mutex]);
 
-        for (i = 0, cc = 0; i < (int64_t)H48_COORDMAX(0); i++) {
-                c = get_h48_pval(arg->table, i, 4);
-                if (c != 0xF)
+                if ((bfsarg->depth < breakpoint && c != bfsarg->depth - 1) ||
+                    (bfsarg->depth >= breakpoint && c != 0xF))
                         continue;
-                cube = invcoord_h48(i, arg->crep, 0);
+
+                cube = invcoord_h48(i, bfsarg->crep, 0);
                 for (m = 0; m < 18; m++) {
                         moved = move(cube, m);
-                        j = coord_h48(moved, arg->cocsepdata, 0);
-                        x = get_h48_pval(arg->table, j, 4);
-                        if (x >= arg->depth)
-                                continue;
-                        FOREACH_H48SIM(cube, arg->cocsepdata, arg->selfsim,
-                                j = coord_h48(cube, arg->cocsepdata, 0);
-                                x = get_h48_pval(arg->table, j, 4);
-                                set_h48_pval(arg->table, j, 4, arg->depth);
-                                cc += x == 0xF;
-                        )
-                        break; /* Enough to find one, skip the rest */
+                        j = coord_h48(moved, bfsarg->cocsepdata, 0);
+                        mutex = H48_INDEX(j, 4) % CHUNKS;
+                        pthread_mutex_lock(bfsarg->table_mutex[mutex]);
+                        c = get_h48_pval(bfsarg->table, j, 4);
+                        pthread_mutex_unlock(bfsarg->table_mutex[mutex]);
+                        if (bfsarg->depth < breakpoint) {
+                                if (c <= bfsarg->depth)
+                                        continue;
+                                markarg.cube = moved;
+                                d += gendata_h48_mark(&markarg);
+                        } else {
+                                if (c >= bfsarg->depth)
+                                        continue;
+                                markarg.cube = cube;
+                                d += gendata_h48_mark(&markarg);
+                                break; /* Enough to find one, skip the rest */
+                        }
                 }
         }
 
-        return cc;
+        pthread_mutex_lock(bfsarg->distribution_mutex);
+        bfsarg->count += d;
+        bfsarg->distribution[bfsarg->depth] += d;
+        pthread_mutex_unlock(bfsarg->distribution_mutex);
+
+        return NULL;
 }
 
 STATIC size_t
@@ -369,24 +414,8 @@ gendata_h48k2(gendata_h48_arg_t *arg)
         };
         gendata_h48short(&shortarg);
 
-        selectedbase = base[arg->h];
-        arg->info = (tableinfo_t) {
-                .solver = "h48 solver h =  , k = 2",
-                .type = TABLETYPE_PRUNING,
-                .infosize = INFOSIZE,
-                .fullsize = H48_TABLESIZE(arg->h, 2) + INFOSIZE,
-                .hash = 0, /* TODO */
-                .entries = H48_COORDMAX(arg->h),
-                .classes = 0,
-                .h48h = arg->h,
-                .bits = 2,
-                .base = selectedbase,
-                .maxvalue = 3,
-                .next = 0,
-        };
-        arg->info.solver[15] = (arg->h % 10) + '0';
-        if (arg->h >= 10)
-                arg->info.solver[14] = (arg->h / 10) + '0';
+        selectedbase = arg->base < 20 ? arg->base : base[arg->h];
+        arg->info = makeinfo_h48k2(arg, selectedbase);
 
         inext = count = 0;
         pthread_mutex_init(&shortcubes_mutex, NULL);
@@ -419,6 +448,7 @@ gendata_h48k2(gendata_h48_arg_t *arg)
 
         h48map_destroy(&shortcubes);
 
+        /* TODO: inline into mark */
         for (j = 0; j < H48_COORDMAX(arg->h); j++) {
                 t = get_h48_pval(table, j, 2);
                 arg->info.distribution[t]++;
@@ -474,21 +504,36 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t *arg)
         int8_t d;
         uint8_t m[4];
         cube_t cube[4];
+        gendata_h48_mark_t markarg;
+
+        markarg = (gendata_h48_mark_t) {
+                .h = arg->h,
+                .k = arg->k,
+                .cocsepdata = arg->cocsepdata,
+                .selfsim = arg->selfsim,
+                .table = arg->table,
+                .table_mutex = arg->table_mutex,
+        };
 
         d = (int8_t)arg->shortdepth - (int8_t)arg->base;
 
         /* Depth d+0 (shortcubes) */
-        gendata_h48k2_mark(arg->cube, d, arg);
+        markarg.depth = d;
+        markarg.cube = arg->cube;
+        gendata_h48_mark(&markarg);
 
         /* Depth d+1 */
         for (m[0] = 0; m[0] < 18; m[0]++) {
+                markarg.depth = d+1;
                 cube[0] = move(arg->cube, m[0]);
                 if (gendata_h48k2_dfs_stop(cube[0], d+1, arg))
                         continue;
-                gendata_h48k2_mark(cube[0], d+1, arg);
+                markarg.cube = cube[0];
+                gendata_h48_mark(&markarg);
 
                 /* Depth d+2 */
                 for (m[1] = 0; m[1] < 18; m[1]++) {
+                        markarg.depth = d+2;
                         if (m[0] / 3 == m[1] / 3) {
                                 m[1] += 2;
                                 continue;
@@ -496,12 +541,14 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t *arg)
                         cube[1] = move(cube[0], m[1]);
                         if (gendata_h48k2_dfs_stop(cube[1], d+2, arg))
                                 continue;
-                        gendata_h48k2_mark(cube[1], d+2, arg);
+                        markarg.cube = cube[1];
+                        gendata_h48_mark(&markarg);
                         if (d >= 0)
                                 continue;
 
                         /* Depth d+3 */
                         for (m[2] = 0; m[2] < 18; m[2]++) {
+                                markarg.depth = d+3;
                                 if (!allowednextmove(m, 3)) {
                                         m[2] += 2;
                                         continue;
@@ -509,48 +556,55 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t *arg)
                                 cube[2] = move(cube[1], m[2]);
                                 if (gendata_h48k2_dfs_stop(cube[2], d+3, arg))
                                         continue;
-                                gendata_h48k2_mark(cube[2], d+3, arg);
+                                markarg.cube = cube[2];
+                                gendata_h48_mark(&markarg);
                                 if (d >= -1)
                                         continue;
 
                                 /* Depth d+4 */
                                 for (m[3] = 0; m[3] < 18; m[3]++) {
+                                        markarg.depth = d+4;
                                         if (!allowednextmove(m, 4)) {
                                                 m[3] += 2;
                                                 continue;
                                         }
                                         cube[3] = move(cube[2], m[3]);
-                                        gendata_h48k2_mark(cube[3], d+4, arg);
+                                        markarg.cube = cube[3];
+                                        gendata_h48_mark(&markarg);
                                 }
                         }
                 }
         }
 }
 
-STATIC_INLINE void
-gendata_h48k2_mark(cube_t cube, int8_t depth, h48k2_dfs_arg_t *arg)
+STATIC_INLINE uint64_t
+gendata_h48_mark(gendata_h48_mark_t *arg)
 {
         uint8_t oldval, newval;
-        int64_t coord, fullcoord, mutex;
+        uint64_t d;
+        int64_t coord, mutex;
 
-        FOREACH_H48SIM(cube, arg->cocsepdata, arg->selfsim,
-                fullcoord = coord_h48(cube, arg->cocsepdata, 11);
-                coord = fullcoord >> (int64_t)(11 - arg->h);
+        d = 0;
+        FOREACH_H48SIM(arg->cube, arg->cocsepdata, arg->selfsim,
+                coord = coord_h48(arg->cube, arg->cocsepdata, arg->h);
                 mutex = H48_INDEX(coord, arg->k) % CHUNKS;
                 pthread_mutex_lock(arg->table_mutex[mutex]);
                 oldval = get_h48_pval(arg->table, coord, arg->k);
-                newval = (uint8_t)MAX(depth, 0);
+                newval = (uint8_t)MAX(arg->depth, 0);
+                d += newval < oldval;
                 set_h48_pval(arg->table, coord, arg->k, MIN(oldval, newval));
                 pthread_mutex_unlock(arg->table_mutex[mutex]);
         )
+
+        return d;
 }
 
 STATIC_INLINE bool
-gendata_h48k2_dfs_stop(cube_t cube, uint8_t depth, h48k2_dfs_arg_t *arg)
+gendata_h48k2_dfs_stop(cube_t cube, int8_t depth, h48k2_dfs_arg_t *arg)
 {
         uint64_t val;
         int64_t coord;
-        uint8_t oldval;
+        int8_t oldval;
 
         if (arg->h == 0 || arg->h == 11) {
                 /* We are in the "real coordinate" case, we can stop
@@ -568,26 +622,44 @@ gendata_h48k2_dfs_stop(cube_t cube, uint8_t depth, h48k2_dfs_arg_t *arg)
         }
 }
 
-STATIC_INLINE uint8_t
-get_h48_pval(const uint8_t *table, int64_t i, uint8_t k)
+STATIC size_t
+gendata_h48k2_realcoord(gendata_h48_arg_t *arg)
 {
-        return (table[H48_INDEX(i, k)] & H48_MASK(i, k)) >> H48_SHIFT(i, k);
+        /* TODO */
+        return gendata_h48k2(arg);
 }
 
-STATIC_INLINE void
-set_h48_pval(uint8_t *table, int64_t i, uint8_t k, uint8_t val)
+STATIC void *
+gendata_h48k2_realcoord_runthread(void *arg)
 {
-        table[H48_INDEX(i, k)] = (table[H48_INDEX(i, k)] & (~H48_MASK(i, k)))
-            | (val << H48_SHIFT(i, k));
+        /* TODO */
+        return NULL;
 }
 
-STATIC_INLINE uint8_t
-get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint8_t k, uint8_t *table)
+STATIC tableinfo_t
+makeinfo_h48k2(gendata_h48_arg_t *arg, uint8_t base)
 {
-        int64_t coord;
+        tableinfo_t info;
 
-        coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h);
-        return get_h48_pval(table, coord, k);
+        info = (tableinfo_t) {
+                .solver = "h48 solver h =  , k = 2",
+                .type = TABLETYPE_PRUNING,
+                .infosize = INFOSIZE,
+                .fullsize = H48_TABLESIZE(arg->h, 2) + INFOSIZE,
+                .hash = 0, /* TODO */
+                .entries = H48_COORDMAX(arg->h),
+                .classes = 0,
+                .h48h = arg->h,
+                .bits = 2,
+                .base = base,
+                .maxvalue = 3,
+                .next = 0,
+        };
+        info.solver[15] = (arg->h % 10) + '0';
+        if (arg->h >= 10)
+                info.solver[14] = (arg->h / 10) + '0';
+
+        return info;
 }
 
 STATIC uint32_t *
@@ -601,3 +673,25 @@ get_h48data_ptr(const void *data)
 {
         return (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE;
 }
+
+STATIC_INLINE uint8_t
+get_h48_pval(const uint8_t *table, int64_t i, uint8_t k)
+{
+        return (table[H48_INDEX(i, k)] & H48_MASK(i, k)) >> H48_SHIFT(i, k);
+}
+
+STATIC_INLINE void
+set_h48_pval(uint8_t *table, int64_t i, uint8_t k, uint8_t val)
+{
+        table[H48_INDEX(i, k)] = (table[H48_INDEX(i, k)] & (~H48_MASK(i, k)))
+            | (val << H48_SHIFT(i, k));
+}
+
+STATIC_INLINE uint8_t
+get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint8_t k, uint8_t *table)
+{
+        int64_t coord;
+
+        coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h);
+        return get_h48_pval(table, coord, k);
+}