commit 5216fb4be01e88f5b4928a69287e8f7ee3b3af5b
parent 3d6c73c33276ecedba86cb871b4b5a089571629b
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 18 Oct 2024 16:35:17 +0200
Add node and fallback benchmarking
Diffstat:
8 files changed, 86 insertions(+), 37 deletions(-)
diff --git a/python/nissy_module.c b/python/nissy_module.c
@@ -155,7 +155,7 @@ datasize(PyObject *self, PyObject *args)
return long_result(result);
}
-/* TODO: gendata, checkdata and solve */
+/* TODO: gendata, checkdata and solve and countmoves */
static PyMethodDef nissy_methods[] = {
{ "compose", compose, METH_VARARGS, NULL },
diff --git a/shell/shell.c b/shell/shell.c
@@ -422,6 +422,7 @@ solve_exec(args_t *args)
uint8_t nissflag;
FILE *file;
char *buf, solutions[SOLUTIONS_BUFFER_SIZE], path[MAX_PATH_LENGTH];
+ long long stats[NISSY_SIZE_SOLVE_STATS];
int64_t ret, gendata_ret, size;
size_t read;
@@ -475,7 +476,7 @@ solve_exec(args_t *args)
ret = nissy_solve(
args->cube, args->str_solver, nissflag, args->minmoves,
args->maxmoves, args->maxsolutions, args->optimal,
- size, buf, SOLUTIONS_BUFFER_SIZE, solutions);
+ size, buf, SOLUTIONS_BUFFER_SIZE, solutions, stats);
free(buf);
diff --git 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
@@ -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
@@ -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
@@ -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:
diff --git a/tools/200_stats_tables_h48/stats_tables_h48.c b/tools/200_stats_tables_h48/stats_tables_h48.c
@@ -30,7 +30,7 @@ static void *
run_thread(void *arg)
{
char s[12], cube[22];
- long long int ep, eo, cp, co;
+ long long int ep, eo, cp, co, stats[NISSY_SIZE_SOLVE_STATS];
int i, j;
thread_arg_t *a = (thread_arg_t *)arg;
@@ -42,7 +42,7 @@ run_thread(void *arg)
co = randll();
nissy_getcube(ep, eo, cp, co, "fix", cube);
nissy_solve(cube, "h48stats", NISSY_NISSFLAG_NORMAL,
- 0, MAXMOVES, 1, -1, size, buf, 12, s);
+ 0, MAXMOVES, 1, -1, size, buf, 12, s, stats);
for (j = 0; j < 12; j++)
a->v[j][(int)s[j]]++;
if ((i+1) % LOG_EVERY == 0)
diff --git a/tools/300_solve_small/solve_small.c b/tools/300_solve_small/solve_small.c
@@ -7,16 +7,24 @@ int64_t size = 0;
char *buf;
char *scrambles[] = {
- "R D' R2 D R U2 R' D' R U2 R D R'", /* 12 optimal */
- "RLUD RLUD RLUD", /* 12 optimal */
- "R' U' F D2 L2 F R2 U2 R2 B D2 L B2 D' B2 L' R' B D2 B U2 L U2 R' U' F", /* FMC2019 A1 - 16 optimal */
- // "R' U' F D R F2 D L F D2 F2 L' U R' L2 D' R2 F2 R2 D L2 U2 R' U' F", /* FMC2024 A1 - 19 optimal */
+ /* 12 optimal */
+ "R D' R2 D R U2 R' D' R U2 R D R'",
+
+ /* 12 optimal */
+ "RLUD RLUD RLUD",
+
+ /* FMC2019 A1 - 16 optimal */
+ "R' U' F D2 L2 F R2 U2 R2 B D2 L B2 D' B2 L' R' B D2 B U2 L U2 R' U' F",
+
+ /* FMC2024 A1 - 19 optimal */
+ "R' U' F D R F2 D L F D2 F2 L' U R' L2 D' R2 F2 R2 D L2 U2 R' U' F",
NULL
};
void run(void) {
int i;
int64_t n;
+ long long stats[NISSY_SIZE_SOLVE_STATS];
char sol[SOL_BUFFER_LEN], cube[22];
printf("Solved the following scrambles:\n\n");
@@ -29,7 +37,7 @@ void run(void) {
continue;
}
n = nissy_solve(cube, solver, NISSY_NISSFLAG_NORMAL,
- 0, 20, 1, -1, size, buf, SOL_BUFFER_LEN, sol);
+ 0, 20, 1, -1, size, buf, SOL_BUFFER_LEN, sol, stats);
if (n == 0)
printf("No solution found\n");
else
