aboutsummaryrefslogtreecommitdiff
path: root/src/solvers/h48/gendata_cocsep.h
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2024-12-07 16:38:40 +0100
committerSebastiano Tronto <sebastiano@tronto.net>2024-12-07 16:38:40 +0100
commit9ac266c76f39620d8343e46ca41cb09d1534384c (patch)
tree823bd419d99fe0f00e6b5b713237a73b4ec7ffca /src/solvers/h48/gendata_cocsep.h
parentea25a7ccad625c4e664dfd114147971b8a2677f3 (diff)
downloadnissy-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.h34
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 @@
1STATIC_INLINE bool get_visited(const uint8_t *, int64_t); 1STATIC_INLINE bool gendata_cocsep_get_visited(const uint8_t *, int64_t);
2STATIC_INLINE void set_visited(uint8_t *, int64_t); 2STATIC_INLINE void gendata_cocsep_set_visited(uint8_t *, int64_t);
3 3
4STATIC size_t gendata_cocsep( 4STATIC size_t gendata_cocsep(
5 char [static COCSEP_FULLSIZE+INFOSIZE], uint64_t *, cube_t *); 5 char [static COCSEP_FULLSIZE], uint64_t *, cube_t *);
6STATIC uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t *); 6STATIC uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t *);
7STATIC void getdistribution_cocsep(const uint32_t *, uint64_t [static 21]); 7STATIC void getdistribution_cocsep(const uint32_t *, uint64_t [static 21]);
8 8
9STATIC_INLINE int8_t get_h48_cdata(cube_t, const uint32_t *, uint32_t *); 9STATIC_INLINE int8_t get_h48_cdata(cube_t, const uint32_t *, uint32_t *);
10 10
11/*
12Each 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
16After 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*/
22STATIC size_t 11STATIC size_t
23gendata_cocsep( 12gendata_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
157STATIC_INLINE bool 147STATIC_INLINE bool
158get_visited(const uint8_t *a, int64_t i) 148gendata_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
163STATIC_INLINE void 153STATIC_INLINE void
164set_visited(uint8_t *a, int64_t i) 154gendata_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}

Generated with cgit - Back to sebastiano.tronto.net