Add node and fallback benchmarking

4 files changed, 68 insertions, 28 deletions

diff --git a/src/nissy.c b/src/nissy.c
index 986f27f..c5cf1d5 100644
--- a/src/nissy.c
+++ b/src/nissy.c
@@ -471,7 +471,8 @@ nissy_solve(
         unsigned long long data_size,
         const char data[data_size],
         unsigned sols_size,
-        char sols[sols_size]
+        char sols[sols_size],
+        long long stats[static NISSY_SIZE_SOLVE_STATS]
 )
 {
         cube_t c;
@@ -511,9 +512,9 @@ nissy_solve(
                 } else {
                         return THREADS > 1 ?
                             solve_h48_multithread(c, minmoves, maxmoves,
-                                maxsols, data_size, data, sols_size, sols) :
+                                maxsols, data_size, data, sols_size, sols, stats) :
                             solve_h48(c, minmoves, maxmoves, maxsols,
-                                data_size, data, sols_size, sols);
+                                data_size, data, sols_size, sols, stats);
                 }
         } else {
                 LOG("solve: unknown solver '%s'\n", solver);
diff --git a/src/nissy.h b/src/nissy.h
index 7a39927..8394fad 100644
--- a/src/nissy.h
+++ b/src/nissy.h
@@ -24,6 +24,7 @@ for example 'rotation UF' or 'mirrored BL'.
 #define NISSY_SIZE_B32            22U
 #define NISSY_SIZE_H48            88U
 #define NISSY_SIZE_TRANSFORMATION 12U
+#define NISSY_SIZE_SOLVE_STATS    10U
 
 /* Flags for NISS options */
 #define NISSY_NISSFLAG_NORMAL  1U
@@ -58,7 +59,8 @@ Return values:
    NISSY_ERROR_INVALID_CUBE  - At least one of the given cubes is invalid.
    NISSY_ERROR_UNKNOWN       - An unknown error occurred.
 */
-long long nissy_compose(
+long long
+nissy_compose(
         const char cube[static NISSY_SIZE_B32],
         const char permutation[static NISSY_SIZE_B32],
         char result[static NISSY_SIZE_B32]
@@ -79,7 +81,8 @@ Return values:
    NISSY_ERROR_INVALID_CUBE  - The given cube is invalid.
    NISSY_ERROR_UNKNOWN       - An unknown error occurred.
 */
-long long nissy_inverse(
+long long
+nissy_inverse(
         const char cube[static NISSY_SIZE_B32],
         char result[static NISSY_SIZE_B32]
 );
@@ -101,7 +104,8 @@ Return values:
    NISSY_ERROR_INVALID_MOVES - The given moves are invalid.
    NISSY_ERROR_NULL_POINTER  - The 'moves' argument is NULL.
 */
-long long nissy_applymoves(
+long long
+nissy_applymoves(
         const char cube[static NISSY_SIZE_B32],
         const char *moves,
         char result[static NISSY_SIZE_B32]
@@ -122,7 +126,8 @@ Return values:
    NISSY_ERROR_INVALID_CUBE  - The given cube is invalid.
    NISSY_ERROR_INVALID_TRANS - The given transformation is invalid.
 */
-long long nissy_applytrans(
+long long
+nissy_applytrans(
         const char cube[static NISSY_SIZE_B32],
         const char transformation[static NISSY_SIZE_TRANSFORMATION],
         char result[static NISSY_SIZE_B32]
@@ -147,7 +152,8 @@ Return values:
    NISSY_ERROR_NULL_POINTER   - At least one of 'format_in', 'format_out' or
                                 'cube_string' arguments is NULL.
 */
-long long nissy_convert(
+long long
+nissy_convert(
         const char *format_in,
         const char *format_out,
         const char *cube_string,
@@ -174,7 +180,8 @@ Return values:
    NISSY_WARNING_UNSOLVABLE - The resulting cube is unsolvable.
    NISSY_ERROR_OPTIONS      - One or more of the given parameters is invalid.
 */
-long long nissy_getcube(
+long long
+nissy_getcube(
         long long ep,
         long long eo,
         long long cp,
@@ -196,7 +203,8 @@ Return values:
    NISSY_ERROR_UNKNOWN        - An unknown error occurred.
    Any value >= 0             - The size of the data, in bytes.
 */
-long long nissy_datasize(
+long long
+nissy_datasize(
         const char *solver
 );
 
@@ -215,7 +223,8 @@ Return values:
    NISSY_ERROR_UNKNOWN        - An error occurred while generating the data.
    Any value >= 0             - The size of the data, in bytes.
 */
-long long nissy_gendata(
+long long
+nissy_gendata(
         const char *solver,
         unsigned long long data_size,
         char data[data_size]
@@ -232,7 +241,8 @@ Return values:
    NISSY_OK         - The data is valid.
    NISSY_ERROR_DATA - The data is invalid.
 */
-long long nissy_checkdata(
+long long
+nissy_checkdata(
         unsigned long long data_size,
         const char data[data_size]
 );
@@ -255,6 +265,7 @@ Parameters:
    sols      - The return parameter for the solutions. The solutions are
                separated by a '\n' (newline) and a '\0' (NULL character)
                terminates the list.
+   stats     - An array to store some statistics about the solve.
 
 Return values:
    NISSY_OK                    - Cube solved succesfully.
@@ -266,7 +277,8 @@ Return values:
    NISSY_ERROR_NULL_POINTER    - The 'solver' argument is null.
    Any value >= 0              - The number of solutions found.
 */
-long long nissy_solve(
+long long
+nissy_solve(
         const char cube[static NISSY_SIZE_B32],
         const char *solver, 
         unsigned nissflag,
@@ -277,7 +289,8 @@ long long nissy_solve(
         unsigned long long data_size,
         const char data[data_size],
         unsigned sols_size,
-        char sols[sols_size]
+        char sols[sols_size],
+        long long stats[static NISSY_SIZE_SOLVE_STATS]
 );
 
 /*
@@ -289,7 +302,8 @@ Return values:
    NISSY_ERROR_NULL_POINTER  - The 'moves' argument is NULL.
    Any value >= 0            - The number of moves.
 */
-long long nissy_countmoves(
+long long
+nissy_countmoves(
         const char *moves
 );
 
@@ -303,7 +317,8 @@ Return values:
    NISSY_OK - Logger set succesfully. No warning or error is goind to be given
               if the logger is NULL or invalid.
 */
-long long nissy_setlogger(
+long long
+nissy_setlogger(
         void (*logger_function)(const char *, ...)
 );
 
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index 778155c..67c596b 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -17,6 +17,8 @@ typedef struct {
         uint8_t nissbranch;
         int8_t npremoves;
         uint8_t premoves[MAXLEN];
+        _Atomic long long *nodes_visited;
+        _Atomic long long *table_fallbacks;
 } dfsarg_solveh48_t;
 
 STATIC uint32_t allowednextmove_h48(uint8_t *, uint8_t, uint8_t);
@@ -24,8 +26,8 @@ STATIC uint32_t allowednextmove_h48(uint8_t *, uint8_t, uint8_t);
 STATIC void solve_h48_appendsolution(dfsarg_solveh48_t *);
 STATIC_INLINE bool solve_h48_stop(dfsarg_solveh48_t *);
 STATIC int64_t solve_h48_dfs(dfsarg_solveh48_t *);
-STATIC int64_t solve_h48(cube_t, int8_t, int8_t,
-    int8_t, uint64_t, const void *, uint64_t, char *);
+STATIC int64_t solve_h48(cube_t, int8_t, int8_t, int8_t, uint64_t,
+    const void *, uint64_t, char *, long long [static NISSY_SIZE_SOLVE_STATS]);
 
 STATIC uint32_t
 allowednextmove_h48(uint8_t *moves, uint8_t n, uint8_t h48branch)
@@ -103,6 +105,8 @@ solve_h48_stop(dfsarg_solveh48_t *arg)
         int8_t cbound, cbound_inv, h48bound, h48bound_inv;
         int64_t coord, coord_inv;
 
+        (*arg->nodes_visited)++;
+
         arg->nissbranch = MM_NORMAL;
         cbound = get_h48_cdata(arg->cube, arg->cocsepdata, &data);
         if (cbound + arg->nmoves + arg->npremoves > arg->depth)
@@ -120,6 +124,7 @@ solve_h48_stop(dfsarg_solveh48_t *arg)
 
         if (arg->k == 2) {
                 if (h48bound == 0) {
+                        (*arg->table_fallbacks)++;
                         h48bound = get_h48_pval(
                             arg->h48data_fallback, coord >> arg->h, 4);
                 } else {
@@ -136,6 +141,7 @@ solve_h48_stop(dfsarg_solveh48_t *arg)
         h48bound_inv = get_h48_pval(arg->h48data, coord_inv, arg->k);
         if (arg->k == 2) {
                 if (h48bound_inv == 0) {
+                        (*arg->table_fallbacks)++;
                         h48bound_inv = get_h48_pval(
                             arg->h48data_fallback, coord_inv >> arg->h, 4);
                 } else {
@@ -209,16 +215,19 @@ solve_h48(
         uint64_t data_size,
         const void *data,
         uint64_t solutions_size,
-        char *solutions
+        char *solutions,
+        long long stats[static NISSY_SIZE_SOLVE_STATS]
 )
 {
         _Atomic int64_t nsols;
+        _Atomic long long nodes, fallbacks;
         dfsarg_solveh48_t arg;
         tableinfo_t info, fbinfo;
 
         if(readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
                 goto solve_h48_error_data;
 
+        nodes = fallbacks = 0;
         arg = (dfsarg_solveh48_t) {
                 .cube = cube,
                 .inverse = inverse(cube),
@@ -230,7 +239,9 @@ solve_h48(
                 .cocsepdata = (uint32_t *)((char *)data + INFOSIZE),
                 .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE,
                 .solutions_size = solutions_size,
-                .nextsol = &solutions
+                .nextsol = &solutions,
+                .nodes_visited = &nodes,
+                .table_fallbacks = &fallbacks
         };
 
         if (info.bits == 2) {
@@ -256,7 +267,11 @@ solve_h48(
                 solve_h48_dfs(&arg);
         }
         **arg.nextsol = '\0';
-        (*arg.nextsol)++;
+
+        stats[0] = nodes;
+        stats[1] = fallbacks;
+        LOG("Nodes visited: %lld\nTable fallbacks: %lld\n", nodes, fallbacks);
+
         return nsols;
 
 solve_h48_error_data:
diff --git a/src/solvers/h48/solve_multithread.h b/src/solvers/h48/solve_multithread.h
index 2755372..394350e 100644
--- a/src/solvers/h48/solve_multithread.h
+++ b/src/solvers/h48/solve_multithread.h
@@ -20,8 +20,8 @@ STATIC void copy_queue(task_queue_t *, task_queue_t *, int, _Atomic int64_t *);
 STATIC void *start_thread(void *);
 STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *, int8_t);
 STATIC int64_t solve_h48_single(dfsarg_solveh48_t *, task_queue_t *);
-STATIC int64_t solve_h48_multithread(cube_t, int8_t, int8_t, int8_t,
-    uint64_t, const void *, uint64_t, char *);
+STATIC int64_t solve_h48_multithread(cube_t, int8_t, int8_t, int8_t, uint64_t,
+    const void *, uint64_t, char *, long long [static NISSY_SIZE_SOLVE_STATS]);
 
 STATIC void
 solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq)
@@ -255,10 +255,12 @@ solve_h48_multithread(
         uint64_t data_size,
         const void *data,
         uint64_t solutions_size,
-        char *solutions
+        char *solutions,
+        long long stats[static NISSY_SIZE_SOLVE_STATS]
 )
 {
         _Atomic int64_t nsols = 0;
+        _Atomic long long nodes, fallbacks;
         int p_depth = 0;
         dfsarg_solveh48_t arg;
         tableinfo_t info, fbinfo;
@@ -267,6 +269,7 @@ solve_h48_multithread(
         if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
                 goto solve_h48_multithread_error_data;
 
+        nodes = fallbacks = 0;
         arg = (dfsarg_solveh48_t){
                 .cube = cube,
                 .inverse = inverse(cube),
@@ -279,7 +282,9 @@ solve_h48_multithread(
                 .cocsepdata = (uint32_t *)((char *)data + INFOSIZE),
                 .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE,
                 .solutions_size = solutions_size,
-                .nextsol = &solutions
+                .nextsol = &solutions,
+                .nodes_visited = &nodes,
+                .table_fallbacks = &fallbacks
         };
 
         if (info.bits == 2) {
@@ -301,7 +306,7 @@ solve_h48_multithread(
         task_queue_t nq;
         init_queue(&nq);
 
-        for (int i = 0; i < THREADS; i++){
+        for (int i = 0; i < THREADS; i++) {
                 pthread_create(&threads[i], NULL, &start_thread, &nq);
         }
 
@@ -323,11 +328,15 @@ solve_h48_multithread(
         atomic_store(&nq.terminate, true);
         pthread_cond_broadcast(&nq.cond);
 
-        for (int i = 0; i < THREADS; i++){
+        for (int i = 0; i < THREADS; i++) {
                 pthread_join(threads[i], NULL);
         }
         **arg.nextsol = '\0';
-        (*arg.nextsol)++;
+
+        stats[0] = nodes;
+        stats[1] = fallbacks;
+        LOG("Nodes visited: %lld\nTable fallbacks: %lld\n", nodes, fallbacks);
+
         return nsols;
 
 solve_h48_multithread_error_data: