From 9ac266c76f39620d8343e46ca41cb09d1534384c Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 7 Dec 2024 16:38:40 +0100 Subject: Merge the "solver-experiments" branch that I have been working on for a few weeks. This include mainly three things: 1. Various tweaks for a total performance gain of around 30%. 2. Take into account symmetries and avoid repeated work. This required a re-work of the splitting into tasks before the solve. 3. Add a second fallback table (eoesep). This gives huge performance gains for particular scrambles (e.g. superflip). After merging this commit, remove and re-generate all pruning tables. Squashed commit of the following: commit 60f0705d2d69050e6a30581a2810f686d6f69b80 Author: Sebastiano Tronto Date: Sat Dec 7 16:06:48 2024 +0100 Fix indentation commit cc5d489a251812b6188c0ba264ac6cb2236f1afe Author: Sebastiano Tronto Date: Sat Dec 7 15:56:19 2024 +0100 Updated documentation commit a3f605dd628546e52564f82b139feb473b0725f3 Author: Sebastiano Tronto Date: Sat Dec 7 14:01:11 2024 +0100 use eoesep table as second fallback commit c75e43c9116c64f97e92b0fe038be8a032925a72 Author: Sebastiano Tronto Date: Fri Dec 6 16:13:23 2024 +0100 First commit for gendata_eoesep commit fea7688ab8bdc5ae0c3480622e2510a3bcd39248 Author: Sebastiano Tronto Date: Tue Dec 3 17:31:00 2024 +0100 Add scramble to tool commit 66866cb71dea4ca8278ecb9e90ff4295771feb42 Author: Sebastiano Tronto Date: Tue Dec 3 17:22:59 2024 +0100 Added tool to check multiple solutions commit ef65611c772c3996bddca8d181da3538e0af1674 Author: Sebastiano Tronto Date: Tue Dec 3 17:16:20 2024 +0100 Write all solutions for symmetric positions commit e3ded26db7d7d4ae7c0e2488151ed14f581f7b8e Author: Sebastiano Tronto Date: Tue Nov 26 09:14:54 2024 +0100 Added symmetry filter (TODO: print excluded solutions) commit 864c437a9751c58d58562650ca9eba4a9e6ad3eb Author: Sebastiano Tronto Date: Mon Nov 25 14:51:13 2024 +0100 Improved task split commit b88926d36d7ab0c64c5fe3bb954fd15d41267fba Author: Sebastiano Tronto Date: Fri Nov 22 19:06:41 2024 +0100 Reworked tasks for multi-threading in view of symmetry filter commit 26fa653f97df8cd601aecb80eaf89f0a00e9ba9f Author: Sebastiano Tronto Date: Thu Oct 31 15:37:43 2024 +0100 Added transform move commit 19f655ef94d658eaa2fefb5cea3c167a3ec58db6 Author: Sebastiano Tronto Date: Thu Oct 31 09:29:15 2024 +0100 Clarified doc commit 3b0fe1e5ef8b628854e30f0f0067300e2763c954 Author: Sebastiano Tronto Date: Thu Oct 31 08:36:58 2024 +0100 Handle solved cube correctly commit 57705cbc4982e3abe97a36ed64871738d4f721c0 Author: Sebastiano Tronto Date: Thu Oct 31 08:24:30 2024 +0100 Close file commit fc7d462b58bcf3d3a3fbf26c1f3bd04c640a4898 Author: Sebastiano Tronto Date: Tue Oct 29 15:05:48 2024 +0100 Removed stats tool commit 359bf7cb49ef405ee76ed662207d47cb2abcc5a9 Author: Sebastiano Tronto Date: Tue Oct 29 15:01:51 2024 +0100 Updated theory doc commit 39c315af562bc4ce896f41004388a4c34d475d37 Author: Sebastiano Tronto Date: Tue Oct 29 14:51:40 2024 +0100 Remove unused constants commit 57a5d24538aa59a4df9221dad2f99e9f0286bd9d Author: Sebastiano Tronto Date: Tue Oct 29 10:20:38 2024 +0100 Add tool to solve scrambles from file commit 07e2918c216636891b1fa6adecc9756086a901e9 Author: Sebastiano Tronto Date: Mon Oct 28 17:00:00 2024 +0100 Add make table to tool commit f5e5266c654eb027a5a35c57cc618555246f5e5e Author: Sebastiano Tronto Date: Mon Oct 28 09:35:49 2024 +0100 Remove old solver, other small things commit a1ec78025b7959dbb845213f7f4e6851ecebc204 Author: Sebastiano Tronto Date: Sun Oct 27 02:00:29 2024 +0200 Improvements commit 8eea23dbe888d923e662e24ae969130e2c67b999 Author: Sebastiano Tronto Date: Sat Oct 26 12:24:19 2024 +0200 Makefile fix commit 3fc3927beacc78971cefeb42da8d71fe6c015fc1 Author: Sebastiano Tronto Date: Fri Oct 25 18:25:09 2024 +0200 More performance gains commit 7b4efa1f9af9722de1ab9ccfc27899825a0d12c4 Author: Sebastiano Tronto Date: Fri Oct 25 15:53:20 2024 +0200 Alternative solver implementation, small performance gain --- src/nissy.c | 80 ++++++++++++++++++++++++++++--------------------------------- 1 file changed, 37 insertions(+), 43 deletions(-) (limited to 'src/nissy.c') diff --git a/src/nissy.c b/src/nissy.c index c09c99e..f933cab 100644 --- a/src/nissy.c +++ b/src/nissy.c @@ -12,12 +12,15 @@ #include "core/core.h" #include "solvers/solvers.h" -int parse_h48_solver(const char *, uint8_t [static 1], uint8_t [static 1]); +long long parse_h48_solver( + const char *, uint8_t [static 1], uint8_t [static 1]); STATIC bool checkdata(const char *, const tableinfo_t *); STATIC bool distribution_equal(const uint64_t [static INFO_DISTRIBUTION_LEN], const uint64_t [static INFO_DISTRIBUTION_LEN], uint8_t); STATIC long long write_result(cube_t, char [static NISSY_SIZE_B32]); STATIC size_t my_strnlen(const char *, size_t); +STATIC long long nissy_gendata_unsafe( + const char *, unsigned long long, char *); #define GETCUBE_OPTIONS(S, F) { .option = S, .fix = F } struct { @@ -28,19 +31,13 @@ struct { GETCUBE_OPTIONS(NULL, NULL) }; -int +long long parse_h48_solver(const char *buf, uint8_t h[static 1], uint8_t k[static 1]) { const char *fullbuf = buf; buf += 3; - if (!strcmp(buf, "stats")) { - *h = 0; - *k = 4; - return 0; - } - if (*buf != 'h') goto parse_h48_solver_error; buf++; @@ -62,9 +59,9 @@ parse_h48_solver(const char *buf, uint8_t h[static 1], uint8_t k[static 1]) parse_h48_solver_error: *h = 0; *k = 0; - LOG("Error parsing solver: must be in \"h48h*k*\" format" - " or \"h48stats\", but got %s\n", fullbuf); - return -1; + LOG("Error parsing solver: must be in \"h48h*k*\" format," + " but got %s\n", fullbuf); + return NISSY_ERROR_INVALID_SOLVER; } STATIC bool @@ -359,20 +356,6 @@ nissy_getcube( return write_result(c, result); } -long long -nissy_datasize( - const char *solver -) -{ - if (solver == NULL) { - LOG("Error: 'solver' argument is NULL\n"); - return NISSY_ERROR_NULL_POINTER; - } - - /* gendata() handles a NULL *data as a "dryrun" request */ - return nissy_gendata(solver, 0, NULL); -} - long long nissy_datainfo( uint64_t data_size, @@ -422,6 +405,15 @@ nissy_datainfo( return NISSY_OK; } +long long +nissy_datasize( + const char *solver +) +{ + /* gendata() handles a NULL *data as a "dryrun" request */ + return nissy_gendata_unsafe(solver, 0, NULL); +} + long long nissy_gendata( const char *solver, @@ -429,7 +421,17 @@ nissy_gendata( char data[data_size] ) { - int p; + return nissy_gendata_unsafe(solver, data_size, data); +} + +STATIC long long +nissy_gendata_unsafe( + const char *solver, + unsigned long long data_size, + char *data +) +{ + long long parse_ret; gendata_h48_arg_t arg; if (solver == NULL) { @@ -440,10 +442,10 @@ nissy_gendata( arg.buf_size = data_size; arg.buf = data; if (!strncmp(solver, "h48", 3)) { - p = parse_h48_solver(solver, &arg.h, &arg.k); + parse_ret = parse_h48_solver(solver, &arg.h, &arg.k); arg.maxdepth = 20; - if (p != 0) - return NISSY_ERROR_UNKNOWN; + if (parse_ret != NISSY_OK) + return parse_ret; return gendata_h48(&arg); } else { LOG("gendata: unknown solver %s\n", solver); @@ -495,7 +497,7 @@ nissy_solve( ) { cube_t c; - int p; + long long parse_ret; uint8_t h, k; if (solver == NULL) { @@ -521,20 +523,12 @@ nissy_solve( } if (!strncmp(solver, "h48", 3)) { - if (!strcmp(solver, "h48stats")) - return solve_h48stats(c, maxmoves, data, sols); - - p = parse_h48_solver(solver, &h, &k); - if (p != 0) { - LOG("solve: unknown solver %s\n", solver); - return NISSY_ERROR_INVALID_SOLVER; - } else { - return THREADS > 1 ? - solve_h48_multithread(c, minmoves, maxmoves, - maxsols, data_size, data, sols_size, sols, stats) : - solve_h48(c, minmoves, maxmoves, maxsols, + parse_ret = parse_h48_solver(solver, &h, &k); + if (parse_ret == NISSY_OK) + return solve_h48(c, minmoves, maxmoves, maxsols, data_size, data, sols_size, sols, stats); - } + else + return parse_ret; } else { LOG("solve: unknown solver '%s'\n", solver); return NISSY_ERROR_INVALID_SOLVER; -- cgit v1.3