diff options
| author | Sebastiano Tronto <sebastiano@tronto.net> | 2024-12-07 16:38:40 +0100 |
|---|---|---|
| committer | Sebastiano Tronto <sebastiano@tronto.net> | 2024-12-07 16:38:40 +0100 |
| commit | 9ac266c76f39620d8343e46ca41cb09d1534384c (patch) | |
| tree | 823bd419d99fe0f00e6b5b713237a73b4ec7ffca /src/nissy.c | |
| parent | ea25a7ccad625c4e664dfd114147971b8a2677f3 (diff) | |
| download | nissy-core-9ac266c76f39620d8343e46ca41cb09d1534384c.tar.gz nissy-core-9ac266c76f39620d8343e46ca41cb09d1534384c.zip | |
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 <sebastiano@tronto.net>
Date: Sat Dec 7 16:06:48 2024 +0100
Fix indentation
commit cc5d489a251812b6188c0ba264ac6cb2236f1afe
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sat Dec 7 15:56:19 2024 +0100
Updated documentation
commit a3f605dd628546e52564f82b139feb473b0725f3
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sat Dec 7 14:01:11 2024 +0100
use eoesep table as second fallback
commit c75e43c9116c64f97e92b0fe038be8a032925a72
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri Dec 6 16:13:23 2024 +0100
First commit for gendata_eoesep
commit fea7688ab8bdc5ae0c3480622e2510a3bcd39248
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Dec 3 17:31:00 2024 +0100
Add scramble to tool
commit 66866cb71dea4ca8278ecb9e90ff4295771feb42
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Dec 3 17:22:59 2024 +0100
Added tool to check multiple solutions
commit ef65611c772c3996bddca8d181da3538e0af1674
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Dec 3 17:16:20 2024 +0100
Write all solutions for symmetric positions
commit e3ded26db7d7d4ae7c0e2488151ed14f581f7b8e
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Nov 26 09:14:54 2024 +0100
Added symmetry filter (TODO: print excluded solutions)
commit 864c437a9751c58d58562650ca9eba4a9e6ad3eb
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon Nov 25 14:51:13 2024 +0100
Improved task split
commit b88926d36d7ab0c64c5fe3bb954fd15d41267fba
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri Nov 22 19:06:41 2024 +0100
Reworked tasks for multi-threading in view of symmetry filter
commit 26fa653f97df8cd601aecb80eaf89f0a00e9ba9f
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu Oct 31 15:37:43 2024 +0100
Added transform move
commit 19f655ef94d658eaa2fefb5cea3c167a3ec58db6
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu Oct 31 09:29:15 2024 +0100
Clarified doc
commit 3b0fe1e5ef8b628854e30f0f0067300e2763c954
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu Oct 31 08:36:58 2024 +0100
Handle solved cube correctly
commit 57705cbc4982e3abe97a36ed64871738d4f721c0
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu Oct 31 08:24:30 2024 +0100
Close file
commit fc7d462b58bcf3d3a3fbf26c1f3bd04c640a4898
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Oct 29 15:05:48 2024 +0100
Removed stats tool
commit 359bf7cb49ef405ee76ed662207d47cb2abcc5a9
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Oct 29 15:01:51 2024 +0100
Updated theory doc
commit 39c315af562bc4ce896f41004388a4c34d475d37
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Oct 29 14:51:40 2024 +0100
Remove unused constants
commit 57a5d24538aa59a4df9221dad2f99e9f0286bd9d
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Oct 29 10:20:38 2024 +0100
Add tool to solve scrambles from file
commit 07e2918c216636891b1fa6adecc9756086a901e9
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon Oct 28 17:00:00 2024 +0100
Add make table to tool
commit f5e5266c654eb027a5a35c57cc618555246f5e5e
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon Oct 28 09:35:49 2024 +0100
Remove old solver, other small things
commit a1ec78025b7959dbb845213f7f4e6851ecebc204
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sun Oct 27 02:00:29 2024 +0200
Improvements
commit 8eea23dbe888d923e662e24ae969130e2c67b999
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sat Oct 26 12:24:19 2024 +0200
Makefile fix
commit 3fc3927beacc78971cefeb42da8d71fe6c015fc1
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri Oct 25 18:25:09 2024 +0200
More performance gains
commit 7b4efa1f9af9722de1ab9ccfc27899825a0d12c4
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri Oct 25 15:53:20 2024 +0200
Alternative solver implementation, small performance gain
Diffstat (limited to '')
| -rw-r--r-- | src/nissy.c | 80 |
1 files changed, 37 insertions, 43 deletions
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 @@ | |||
| 12 | #include "core/core.h" | 12 | #include "core/core.h" |
| 13 | #include "solvers/solvers.h" | 13 | #include "solvers/solvers.h" |
| 14 | 14 | ||
| 15 | int parse_h48_solver(const char *, uint8_t [static 1], uint8_t [static 1]); | 15 | long long parse_h48_solver( |
| 16 | const char *, uint8_t [static 1], uint8_t [static 1]); | ||
| 16 | STATIC bool checkdata(const char *, const tableinfo_t *); | 17 | STATIC bool checkdata(const char *, const tableinfo_t *); |
| 17 | STATIC bool distribution_equal(const uint64_t [static INFO_DISTRIBUTION_LEN], | 18 | STATIC bool distribution_equal(const uint64_t [static INFO_DISTRIBUTION_LEN], |
| 18 | const uint64_t [static INFO_DISTRIBUTION_LEN], uint8_t); | 19 | const uint64_t [static INFO_DISTRIBUTION_LEN], uint8_t); |
| 19 | STATIC long long write_result(cube_t, char [static NISSY_SIZE_B32]); | 20 | STATIC long long write_result(cube_t, char [static NISSY_SIZE_B32]); |
| 20 | STATIC size_t my_strnlen(const char *, size_t); | 21 | STATIC size_t my_strnlen(const char *, size_t); |
| 22 | STATIC long long nissy_gendata_unsafe( | ||
| 23 | const char *, unsigned long long, char *); | ||
| 21 | 24 | ||
| 22 | #define GETCUBE_OPTIONS(S, F) { .option = S, .fix = F } | 25 | #define GETCUBE_OPTIONS(S, F) { .option = S, .fix = F } |
| 23 | struct { | 26 | struct { |
| @@ -28,19 +31,13 @@ struct { | |||
| 28 | GETCUBE_OPTIONS(NULL, NULL) | 31 | GETCUBE_OPTIONS(NULL, NULL) |
| 29 | }; | 32 | }; |
| 30 | 33 | ||
| 31 | int | 34 | long long |
| 32 | parse_h48_solver(const char *buf, uint8_t h[static 1], uint8_t k[static 1]) | 35 | parse_h48_solver(const char *buf, uint8_t h[static 1], uint8_t k[static 1]) |
| 33 | { | 36 | { |
| 34 | const char *fullbuf = buf; | 37 | const char *fullbuf = buf; |
| 35 | 38 | ||
| 36 | buf += 3; | 39 | buf += 3; |
| 37 | 40 | ||
| 38 | if (!strcmp(buf, "stats")) { | ||
| 39 | *h = 0; | ||
| 40 | *k = 4; | ||
| 41 | return 0; | ||
| 42 | } | ||
| 43 | |||
| 44 | if (*buf != 'h') | 41 | if (*buf != 'h') |
| 45 | goto parse_h48_solver_error; | 42 | goto parse_h48_solver_error; |
| 46 | buf++; | 43 | buf++; |
| @@ -62,9 +59,9 @@ parse_h48_solver(const char *buf, uint8_t h[static 1], uint8_t k[static 1]) | |||
| 62 | parse_h48_solver_error: | 59 | parse_h48_solver_error: |
| 63 | *h = 0; | 60 | *h = 0; |
| 64 | *k = 0; | 61 | *k = 0; |
| 65 | LOG("Error parsing solver: must be in \"h48h*k*\" format" | 62 | LOG("Error parsing solver: must be in \"h48h*k*\" format," |
| 66 | " or \"h48stats\", but got %s\n", fullbuf); | 63 | " but got %s\n", fullbuf); |
| 67 | return -1; | 64 | return NISSY_ERROR_INVALID_SOLVER; |
| 68 | } | 65 | } |
| 69 | 66 | ||
| 70 | STATIC bool | 67 | STATIC bool |
| @@ -360,20 +357,6 @@ nissy_getcube( | |||
| 360 | } | 357 | } |
| 361 | 358 | ||
| 362 | long long | 359 | long long |
| 363 | nissy_datasize( | ||
| 364 | const char *solver | ||
| 365 | ) | ||
| 366 | { | ||
| 367 | if (solver == NULL) { | ||
| 368 | LOG("Error: 'solver' argument is NULL\n"); | ||
| 369 | return NISSY_ERROR_NULL_POINTER; | ||
| 370 | } | ||
| 371 | |||
| 372 | /* gendata() handles a NULL *data as a "dryrun" request */ | ||
| 373 | return nissy_gendata(solver, 0, NULL); | ||
| 374 | } | ||
| 375 | |||
| 376 | long long | ||
| 377 | nissy_datainfo( | 360 | nissy_datainfo( |
| 378 | uint64_t data_size, | 361 | uint64_t data_size, |
| 379 | const char data[data_size], | 362 | const char data[data_size], |
| @@ -423,13 +406,32 @@ nissy_datainfo( | |||
| 423 | } | 406 | } |
| 424 | 407 | ||
| 425 | long long | 408 | long long |
| 409 | nissy_datasize( | ||
| 410 | const char *solver | ||
| 411 | ) | ||
| 412 | { | ||
| 413 | /* gendata() handles a NULL *data as a "dryrun" request */ | ||
| 414 | return nissy_gendata_unsafe(solver, 0, NULL); | ||
| 415 | } | ||
| 416 | |||
| 417 | long long | ||
| 426 | nissy_gendata( | 418 | nissy_gendata( |
| 427 | const char *solver, | 419 | const char *solver, |
| 428 | unsigned long long data_size, | 420 | unsigned long long data_size, |
| 429 | char data[data_size] | 421 | char data[data_size] |
| 430 | ) | 422 | ) |
| 431 | { | 423 | { |
| 432 | int p; | 424 | return nissy_gendata_unsafe(solver, data_size, data); |
| 425 | } | ||
| 426 | |||
| 427 | STATIC long long | ||
| 428 | nissy_gendata_unsafe( | ||
| 429 | const char *solver, | ||
| 430 | unsigned long long data_size, | ||
| 431 | char *data | ||
| 432 | ) | ||
| 433 | { | ||
| 434 | long long parse_ret; | ||
| 433 | gendata_h48_arg_t arg; | 435 | gendata_h48_arg_t arg; |
| 434 | 436 | ||
| 435 | if (solver == NULL) { | 437 | if (solver == NULL) { |
| @@ -440,10 +442,10 @@ nissy_gendata( | |||
| 440 | arg.buf_size = data_size; | 442 | arg.buf_size = data_size; |
| 441 | arg.buf = data; | 443 | arg.buf = data; |
| 442 | if (!strncmp(solver, "h48", 3)) { | 444 | if (!strncmp(solver, "h48", 3)) { |
| 443 | p = parse_h48_solver(solver, &arg.h, &arg.k); | 445 | parse_ret = parse_h48_solver(solver, &arg.h, &arg.k); |
| 444 | arg.maxdepth = 20; | 446 | arg.maxdepth = 20; |
| 445 | if (p != 0) | 447 | if (parse_ret != NISSY_OK) |
| 446 | return NISSY_ERROR_UNKNOWN; | 448 | return parse_ret; |
| 447 | return gendata_h48(&arg); | 449 | return gendata_h48(&arg); |
| 448 | } else { | 450 | } else { |
| 449 | LOG("gendata: unknown solver %s\n", solver); | 451 | LOG("gendata: unknown solver %s\n", solver); |
| @@ -495,7 +497,7 @@ nissy_solve( | |||
| 495 | ) | 497 | ) |
| 496 | { | 498 | { |
| 497 | cube_t c; | 499 | cube_t c; |
| 498 | int p; | 500 | long long parse_ret; |
| 499 | uint8_t h, k; | 501 | uint8_t h, k; |
| 500 | 502 | ||
| 501 | if (solver == NULL) { | 503 | if (solver == NULL) { |
| @@ -521,20 +523,12 @@ nissy_solve( | |||
| 521 | } | 523 | } |
| 522 | 524 | ||
| 523 | if (!strncmp(solver, "h48", 3)) { | 525 | if (!strncmp(solver, "h48", 3)) { |
| 524 | if (!strcmp(solver, "h48stats")) | 526 | parse_ret = parse_h48_solver(solver, &h, &k); |
| 525 | return solve_h48stats(c, maxmoves, data, sols); | 527 | if (parse_ret == NISSY_OK) |
| 526 | 528 | return solve_h48(c, minmoves, maxmoves, maxsols, | |
| 527 | p = parse_h48_solver(solver, &h, &k); | ||
| 528 | if (p != 0) { | ||
| 529 | LOG("solve: unknown solver %s\n", solver); | ||
| 530 | return NISSY_ERROR_INVALID_SOLVER; | ||
| 531 | } else { | ||
| 532 | return THREADS > 1 ? | ||
| 533 | solve_h48_multithread(c, minmoves, maxmoves, | ||
| 534 | maxsols, data_size, data, sols_size, sols, stats) : | ||
| 535 | solve_h48(c, minmoves, maxmoves, maxsols, | ||
| 536 | data_size, data, sols_size, sols, stats); | 529 | data_size, data, sols_size, sols, stats); |
| 537 | } | 530 | else |
| 531 | return parse_ret; | ||
| 538 | } else { | 532 | } else { |
| 539 | LOG("solve: unknown solver '%s'\n", solver); | 533 | LOG("solve: unknown solver '%s'\n", solver); |
| 540 | return NISSY_ERROR_INVALID_SOLVER; | 534 | return NISSY_ERROR_INVALID_SOLVER; |
