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/solvers/h48/gendata_cocsep.h | |
| 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 'src/solvers/h48/gendata_cocsep.h')
| -rw-r--r-- | src/solvers/h48/gendata_cocsep.h | 34 |
1 files changed, 12 insertions, 22 deletions
diff --git a/src/solvers/h48/gendata_cocsep.h b/src/solvers/h48/gendata_cocsep.h index b46bcf3..291ae48 100644 --- a/src/solvers/h48/gendata_cocsep.h +++ b/src/solvers/h48/gendata_cocsep.h | |||
| @@ -1,27 +1,16 @@ | |||
| 1 | STATIC_INLINE bool get_visited(const uint8_t *, int64_t); | 1 | STATIC_INLINE bool gendata_cocsep_get_visited(const uint8_t *, int64_t); |
| 2 | STATIC_INLINE void set_visited(uint8_t *, int64_t); | 2 | STATIC_INLINE void gendata_cocsep_set_visited(uint8_t *, int64_t); |
| 3 | 3 | ||
| 4 | STATIC size_t gendata_cocsep( | 4 | STATIC size_t gendata_cocsep( |
| 5 | char [static COCSEP_FULLSIZE+INFOSIZE], uint64_t *, cube_t *); | 5 | char [static COCSEP_FULLSIZE], uint64_t *, cube_t *); |
| 6 | STATIC uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t *); | 6 | STATIC uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t *); |
| 7 | STATIC void getdistribution_cocsep(const uint32_t *, uint64_t [static 21]); | 7 | STATIC void getdistribution_cocsep(const uint32_t *, uint64_t [static 21]); |
| 8 | 8 | ||
| 9 | STATIC_INLINE int8_t get_h48_cdata(cube_t, const uint32_t *, uint32_t *); | 9 | STATIC_INLINE int8_t get_h48_cdata(cube_t, const uint32_t *, uint32_t *); |
| 10 | 10 | ||
| 11 | /* | ||
| 12 | Each element of the cocsep table is a uint32_t used as follows: | ||
| 13 | - Lowest 8-bit block: pruning value | ||
| 14 | - Second-lowest 8-bit block: "ttrep" (transformation to representative) | ||
| 15 | - Top 16-bit block: symcoord value | ||
| 16 | After the data as described above, more auxiliary information is appended: | ||
| 17 | - A uint32_t representing the number of symmetry classes | ||
| 18 | - A uint32_t representing the highest value of the pruning table | ||
| 19 | - One uint32_t for each "line" of the pruning table, representing the number | ||
| 20 | of positions having that pruning value. | ||
| 21 | */ | ||
| 22 | STATIC size_t | 11 | STATIC size_t |
| 23 | gendata_cocsep( | 12 | gendata_cocsep( |
| 24 | char buf[static COCSEP_FULLSIZE+INFOSIZE], | 13 | char buf[static COCSEP_FULLSIZE], |
| 25 | uint64_t *selfsim, | 14 | uint64_t *selfsim, |
| 26 | cube_t *rep | 15 | cube_t *rep |
| 27 | ) | 16 | ) |
| @@ -36,7 +25,7 @@ gendata_cocsep( | |||
| 36 | goto gendata_cocsep_return_size; | 25 | goto gendata_cocsep_return_size; |
| 37 | 26 | ||
| 38 | memset(buf, 0xFF, COCSEP_FULLSIZE); | 27 | memset(buf, 0xFF, COCSEP_FULLSIZE); |
| 39 | buf32 = (uint32_t *)((char *)buf + INFOSIZE); | 28 | buf32 = (uint32_t *)(buf + INFOSIZE); |
| 40 | if (selfsim != NULL) | 29 | if (selfsim != NULL) |
| 41 | memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES); | 30 | memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES); |
| 42 | 31 | ||
| @@ -69,7 +58,7 @@ gendata_cocsep( | |||
| 69 | info.distribution[i] = cc; | 58 | info.distribution[i] = cc; |
| 70 | } | 59 | } |
| 71 | 60 | ||
| 72 | writetableinfo(&info, COCSEP_FULLSIZE+INFOSIZE, buf); | 61 | writetableinfo(&info, COCSEP_FULLSIZE, buf); |
| 73 | 62 | ||
| 74 | DBG_ASSERT(n == COCSEP_CLASSES, 0, | 63 | DBG_ASSERT(n == COCSEP_CLASSES, 0, |
| 75 | "cocsep: computed %" PRIu16 " symmetry classes, " | 64 | "cocsep: computed %" PRIu16 " symmetry classes, " |
| @@ -101,9 +90,10 @@ gendata_cocsep_dfs(cocsep_dfs_arg_t *arg) | |||
| 101 | 90 | ||
| 102 | i = coord_cocsep(arg->cube); | 91 | i = coord_cocsep(arg->cube); |
| 103 | olddepth = (uint8_t)(arg->buf32[i] & 0xFF); | 92 | olddepth = (uint8_t)(arg->buf32[i] & 0xFF); |
| 104 | if (olddepth < arg->depth || get_visited(arg->visited, i)) | 93 | if (olddepth < arg->depth || |
| 94 | gendata_cocsep_get_visited(arg->visited, i)) | ||
| 105 | return 0; | 95 | return 0; |
| 106 | set_visited(arg->visited, i); | 96 | gendata_cocsep_set_visited(arg->visited, i); |
| 107 | 97 | ||
| 108 | if (arg->depth == arg->maxdepth) { | 98 | if (arg->depth == arg->maxdepth) { |
| 109 | if ((arg->buf32[i] & 0xFF) != 0xFF) | 99 | if ((arg->buf32[i] & 0xFF) != 0xFF) |
| @@ -118,7 +108,7 @@ gendata_cocsep_dfs(cocsep_dfs_arg_t *arg) | |||
| 118 | arg->selfsim[*arg->n] |= UINT64_C(1) << t; | 108 | arg->selfsim[*arg->n] |= UINT64_C(1) << t; |
| 119 | if (COCLASS(arg->buf32[j]) != UINT32_C(0xFFFF)) | 109 | if (COCLASS(arg->buf32[j]) != UINT32_C(0xFFFF)) |
| 120 | continue; | 110 | continue; |
| 121 | set_visited(arg->visited, j); | 111 | gendata_cocsep_set_visited(arg->visited, j); |
| 122 | tinv = inverse_trans(t); | 112 | tinv = inverse_trans(t); |
| 123 | olddepth = arg->buf32[j] & 0xFF; | 113 | olddepth = arg->buf32[j] & 0xFF; |
| 124 | cc += olddepth == 0xFF; | 114 | cc += olddepth == 0xFF; |
| @@ -155,13 +145,13 @@ getdistribution_cocsep(const uint32_t *table, uint64_t distr[static 21]) | |||
| 155 | } | 145 | } |
| 156 | 146 | ||
| 157 | STATIC_INLINE bool | 147 | STATIC_INLINE bool |
| 158 | get_visited(const uint8_t *a, int64_t i) | 148 | gendata_cocsep_get_visited(const uint8_t *a, int64_t i) |
| 159 | { | 149 | { |
| 160 | return a[VISITED_IND(i)] & VISITED_MASK(i); | 150 | return a[VISITED_IND(i)] & VISITED_MASK(i); |
| 161 | } | 151 | } |
| 162 | 152 | ||
| 163 | STATIC_INLINE void | 153 | STATIC_INLINE void |
| 164 | set_visited(uint8_t *a, int64_t i) | 154 | gendata_cocsep_set_visited(uint8_t *a, int64_t i) |
| 165 | { | 155 | { |
| 166 | a[VISITED_IND(i)] |= VISITED_MASK(i); | 156 | a[VISITED_IND(i)] |= VISITED_MASK(i); |
| 167 | } | 157 | } |
