diff options
| -rw-r--r-- | README.md | 34 | ||||
| -rw-r--r-- | benchmarks/benchmarks.md | 6 | ||||
| -rw-r--r-- | benchmarks/img/16threads.png | bin | 81629 -> 0 bytes | |||
| -rw-r--r-- | benchmarks/img/16threadsspeedupfactor.png | bin | 0 -> 87877 bytes | |||
| -rw-r--r-- | benchmarks/img/4threads.png | bin | 88252 -> 0 bytes | |||
| -rw-r--r-- | benchmarks/img/4threadsspeedupfactor.png | bin | 0 -> 95085 bytes | |||
| -rw-r--r-- | benchmarks/plot-benchmarks.py | 4 | ||||
| -rw-r--r-- | benchmarks/tables_16_threads.md | 3 | ||||
| -rw-r--r-- | benchmarks/tables_4_threads.md | 3 |
9 files changed, 28 insertions, 22 deletions
| @@ -16,7 +16,7 @@ of pruning tables that were developed independently. | |||
| 16 | This project is mainly developed on UNIX systems (Linux, MacOS, BSD...), | 16 | This project is mainly developed on UNIX systems (Linux, MacOS, BSD...), |
| 17 | but it is also possible to build it on Windows, with some limitations. | 17 | but it is also possible to build it on Windows, with some limitations. |
| 18 | 18 | ||
| 19 | ### UNIX (Linux, MaxOS, BSD...) | 19 | ### UNIX (Linux, MacOS, BSD...) |
| 20 | 20 | ||
| 21 | To build nissy simply run | 21 | To build nissy simply run |
| 22 | 22 | ||
| @@ -35,7 +35,7 @@ $ CC=gcc ./build.sh | |||
| 35 | ``` | 35 | ``` |
| 36 | 36 | ||
| 37 | is going to configure `nissy` to use at most 3 threads, and build it with | 37 | is going to configure `nissy` to use at most 3 threads, and build it with |
| 38 | `gcc`. Se the comments in `./build.sh` for more details. | 38 | `gcc`. See the comments in `./build.sh` for more details. |
| 39 | 39 | ||
| 40 | ### Windows | 40 | ### Windows |
| 41 | 41 | ||
| @@ -43,7 +43,7 @@ It is possible to build this project on Windows using `build.bat`. The | |||
| 43 | [Clang](https://clang.llvm.org/) compiler must be installed, and the | 43 | [Clang](https://clang.llvm.org/) compiler must be installed, and the |
| 44 | command prompt must be correctly configured to run it. | 44 | command prompt must be correctly configured to run it. |
| 45 | 45 | ||
| 46 | We suggest installing Clang via the Visual Studio Istaller, selecting | 46 | We suggest installing Clang via the Visual Studio Installer, selecting |
| 47 | the "C++ development" pack, as well as the "clang" and "Windows SDK 11" | 47 | the "C++ development" pack, as well as the "clang" and "Windows SDK 11" |
| 48 | components. It is advised to use "x64 Native Tools Command Prompt for | 48 | components. It is advised to use "x64 Native Tools Command Prompt for |
| 49 | VS 2022" instead of a regular command prompt to run the build script. | 49 | VS 2022" instead of a regular command prompt to run the build script. |
| @@ -64,13 +64,13 @@ can be used to build the basic shell, while | |||
| 64 | Builds and runs the unit tests. See `build.bat help` for a list of | 64 | Builds and runs the unit tests. See `build.bat help` for a list of |
| 65 | all available options. | 65 | all available options. |
| 66 | 66 | ||
| 67 | Not: At the moment certain optimizations, such as multithreading and | 67 | Note: At the moment certain optimizations, such as multithreading and |
| 68 | advanced CPU instructions, are not supported on Windows. | 68 | advanced CPU instructions, are not supported on Windows. |
| 69 | Work is ongoing to improve Windows support. | 69 | Work is ongoing to improve Windows support. |
| 70 | 70 | ||
| 71 | ## Running tests | 71 | ## Running tests |
| 72 | 72 | ||
| 73 | This project includes a suite of "unit" test. You can run them with: | 73 | This project includes a suite of "unit" tests. You can run them with: |
| 74 | 74 | ||
| 75 | ``` | 75 | ``` |
| 76 | $ ./build.sh test | 76 | $ ./build.sh test |
| @@ -86,14 +86,14 @@ To run only a subset of the tests, you can pass as argument a regular | |||
| 86 | expression that matches only the name of the tests you want to run: | 86 | expression that matches only the name of the tests you want to run: |
| 87 | 87 | ||
| 88 | ``` | 88 | ``` |
| 89 | $ ./buld test coord | 89 | $ ./build.sh test coord |
| 90 | ``` | 90 | ``` |
| 91 | 91 | ||
| 92 | Each subfolder of the test folder contains a test. A test can consist | 92 | Each subfolder of the test folder contains a test. A test can consist |
| 93 | of multiple test cases (.in files). Running a test means compiling and | 93 | of multiple test cases (.in files). Running a test means compiling and |
| 94 | running the corresponding test against each test case. When a test case | 94 | running the corresponding test against each test case. When a test case |
| 95 | is run, the .in file is read a the output of the program is compared | 95 | is run, the .in file is read and the output of the program is compared |
| 96 | to the corresponding .out filei using diff(1). If the two differ, the | 96 | to the corresponding .out file using diff(1). If the two differ, the |
| 97 | difference is printed out and no other test is run. | 97 | difference is printed out and no other test is run. |
| 98 | 98 | ||
| 99 | The results of the last test case run is saved in test/last.out (standard | 99 | The results of the last test case run is saved in test/last.out (standard |
| @@ -108,7 +108,7 @@ More comprehensive tests (integration tests) can be performed with *tools*. | |||
| 108 | ## Running "tools" | 108 | ## Running "tools" |
| 109 | 109 | ||
| 110 | In the tools folder there are some small programs that test various | 110 | In the tools folder there are some small programs that test various |
| 111 | functionality of the H48 library. They work similarly to test, but they | 111 | functionality of the H48 library. They work similarly to tests, but they |
| 112 | are not run in debug mode by default. | 112 | are not run in debug mode by default. |
| 113 | 113 | ||
| 114 | To run a tool you can use: | 114 | To run a tool you can use: |
| @@ -124,13 +124,13 @@ parameters. | |||
| 124 | For example: | 124 | For example: |
| 125 | 125 | ||
| 126 | ``` | 126 | ``` |
| 127 | $ :./build.sh tool gendata h48h2 | 127 | $ ./build.sh tool gendata h48h2 |
| 128 | ``` | 128 | ``` |
| 129 | 129 | ||
| 130 | Will run a tool that generates the data table for the H48 solver with `h=2`. | 130 | Will run a tool that generates the data table for the H48 solver with `h=2`. |
| 131 | 131 | ||
| 132 | Each tool run is automatically timed, so these tools can be used as | 132 | Each tool run is automatically timed, so these tools can be used as |
| 133 | benchmark. The output as well as the time of the run are saved to a | 133 | benchmarks. The output as well as the time of the run are saved to a |
| 134 | file in the tools/results folder. | 134 | file in the tools/results folder. |
| 135 | 135 | ||
| 136 | To build and run a tool in debug mode, use `./build.sh -d tool`. | 136 | To build and run a tool in debug mode, use `./build.sh -d tool`. |
| @@ -150,7 +150,7 @@ If one of the solvetests fails, subsequent tests are going to be skipped. | |||
| 150 | ## Command-line interface | 150 | ## Command-line interface |
| 151 | 151 | ||
| 152 | The `shell` folder contains the code for a rudimentary shell that can | 152 | The `shell` folder contains the code for a rudimentary shell that can |
| 153 | be used to run commands manually. The user experience in not amazing, | 153 | be used to run commands manually. The user experience is not amazing, |
| 154 | as the commands require quite verbose options. | 154 | as the commands require quite verbose options. |
| 155 | 155 | ||
| 156 | To build the shell run: | 156 | To build the shell run: |
| @@ -169,7 +169,7 @@ JLQWSVUH=ZLCUABGIVTKH=A | |||
| 169 | 169 | ||
| 170 | The cube format is meant to be easy to copy-paste and read for the | 170 | The cube format is meant to be easy to copy-paste and read for the |
| 171 | software, but not necessarily intuitive for the user. See below for a | 171 | software, but not necessarily intuitive for the user. See below for a |
| 172 | detaileed description. | 172 | detailed description. |
| 173 | 173 | ||
| 174 | You can also get a random cube | 174 | You can also get a random cube |
| 175 | 175 | ||
| @@ -192,7 +192,7 @@ $ ./run solve_scramble -solver h48h0k4 -n 1 -M 4 -moves "R' U' F" | |||
| 192 | F' U' R | 192 | F' U' R |
| 193 | ``` | 193 | ``` |
| 194 | 194 | ||
| 195 | For a full list of available command, use `./run help`. | 195 | For a full list of available commands, use `./run help`. |
| 196 | 196 | ||
| 197 | ## Using this software as a library | 197 | ## Using this software as a library |
| 198 | 198 | ||
| @@ -204,7 +204,7 @@ The API is documented in the public header file `src/nissy.h`. | |||
| 204 | 204 | ||
| 205 | ### C | 205 | ### C |
| 206 | 206 | ||
| 207 | To use this in a C project, simly include `src/nissy.h`. The tools | 207 | To use this in a C project, simply include `src/nissy.h`. The tools |
| 208 | in the `tools/` folder are a good example for how to use this. | 208 | in the `tools/` folder are a good example for how to use this. |
| 209 | 209 | ||
| 210 | NOTE: this project is developed using the C11 standard. If you are using | 210 | NOTE: this project is developed using the C11 standard. If you are using |
| @@ -317,7 +317,7 @@ cccccccc=eeeeeeeeeeee=r | |||
| 317 | ``` | 317 | ``` |
| 318 | 318 | ||
| 319 | Where the first 8 characters represent the corner, the 12 characters | 319 | Where the first 8 characters represent the corner, the 12 characters |
| 320 | after the first 12 represent the edges and the last character represents | 320 | after the first 8 represent the edges and the last character represents |
| 321 | the orientation of the cube with respect to the base orientation. | 321 | the orientation of the cube with respect to the base orientation. |
| 322 | 322 | ||
| 323 | Edges are numbered as follows (see also constants.h): | 323 | Edges are numbered as follows (see also constants.h): |
| @@ -337,7 +337,7 @@ UFR=0 UBL=1 DFL=2 DBR=3 UFL=4 UBR=5 DFR=6 DBL=7 | |||
| 337 | 337 | ||
| 338 | If the corner is twisted clockwise with respect to the U/D | 338 | If the corner is twisted clockwise with respect to the U/D |
| 339 | axis orientation, the value is increased by 8. If it is twisted | 339 | axis orientation, the value is increased by 8. If it is twisted |
| 340 | counter-clowsie, the value is increased by 16. | 340 | counter-clockwise, the value is increased by 16. |
| 341 | 341 | ||
| 342 | The orientations of the cube are numbered as follows, where e.g. "RB" | 342 | The orientations of the cube are numbered as follows, where e.g. "RB" |
| 343 | means that the R face in on top and the B face is on front: | 343 | means that the R face in on top and the B face is on front: |
diff --git a/benchmarks/benchmarks.md b/benchmarks/benchmarks.md index 3fc2093..baba515 100644 --- a/benchmarks/benchmarks.md +++ b/benchmarks/benchmarks.md | |||
| @@ -146,7 +146,8 @@ Speed-up factor (higher is better). | |||
| 146 | |H48 h8 | 7.1 GiB| 3.53| 3.72| 3.81| | | | 146 | |H48 h8 | 7.1 GiB| 3.53| 3.72| 3.81| | | |
| 147 | |H48 h7 | 3.5 GiB| 3.60| 3.78| 3.80| | | | 147 | |H48 h7 | 3.5 GiB| 3.60| 3.78| 3.80| | | |
| 148 | |H48 h6 | 1.8 GiB| 3.77| 3.82| 3.79| | | | 148 | |H48 h6 | 1.8 GiB| 3.77| 3.82| 3.79| | | |
| 149 | <img src="img/4threads.png"> | 149 | |
| 150 | <img src="img/4threadsspeedupfactor.png"> | ||
| 150 | 151 | ||
| 151 | </details> | 152 | </details> |
| 152 | 153 | ||
| @@ -174,7 +175,8 @@ Speed-up factor (higher is better). | |||
| 174 | |H48 h8 | 7.1 GiB| 8.08| 9.91| 10.40| | | | 175 | |H48 h8 | 7.1 GiB| 8.08| 9.91| 10.40| | | |
| 175 | |H48 h7 | 3.5 GiB| 8.59| 10.30| 10.57| | | | 176 | |H48 h7 | 3.5 GiB| 8.59| 10.30| 10.57| | | |
| 176 | |H48 h6 | 1.8 GiB| 9.60| 10.39| 10.54| | | | 177 | |H48 h6 | 1.8 GiB| 9.60| 10.39| 10.54| | | |
| 177 | <img src="img/16threads.png"> | 178 | |
| 179 | <img src="img/16threadsspeedupfactor.png"> | ||
| 178 | 180 | ||
| 179 | </details> | 181 | </details> |
| 180 | 182 | ||
diff --git a/benchmarks/img/16threads.png b/benchmarks/img/16threads.png deleted file mode 100644 index 8161758..0000000 --- a/benchmarks/img/16threads.png +++ /dev/null | |||
| Binary files differ | |||
diff --git a/benchmarks/img/16threadsspeedupfactor.png b/benchmarks/img/16threadsspeedupfactor.png new file mode 100644 index 0000000..5dcaaef --- /dev/null +++ b/benchmarks/img/16threadsspeedupfactor.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/4threads.png b/benchmarks/img/4threads.png deleted file mode 100644 index a0cfb2f..0000000 --- a/benchmarks/img/4threads.png +++ /dev/null | |||
| Binary files differ | |||
diff --git a/benchmarks/img/4threadsspeedupfactor.png b/benchmarks/img/4threadsspeedupfactor.png new file mode 100644 index 0000000..49badc4 --- /dev/null +++ b/benchmarks/img/4threadsspeedupfactor.png | |||
| Binary files differ | |||
diff --git a/benchmarks/plot-benchmarks.py b/benchmarks/plot-benchmarks.py index 027e0fe..1a6fc39 100644 --- a/benchmarks/plot-benchmarks.py +++ b/benchmarks/plot-benchmarks.py | |||
| @@ -108,6 +108,7 @@ with open(benchmarks_4_threads, "w") as f: | |||
| 108 | f.write("Speed-up factor (higher is better).\n") | 108 | f.write("Speed-up factor (higher is better).\n") |
| 109 | f.write("\n") | 109 | f.write("\n") |
| 110 | print_factor_table(f, results_h48.h48_single_thread, results_h48.h48_4_threads) | 110 | print_factor_table(f, results_h48.h48_single_thread, results_h48.h48_4_threads) |
| 111 | f.write("\n") | ||
| 111 | f.write('<img src="img/4threadsspeedupfactor.png">\n') | 112 | f.write('<img src="img/4threadsspeedupfactor.png">\n') |
| 112 | f.write("\n") | 113 | f.write("\n") |
| 113 | f.write("</details>\n") | 114 | f.write("</details>\n") |
| @@ -123,6 +124,7 @@ with open(benchmarks_16_threads, "w") as f: | |||
| 123 | f.write("Speed-up factor (higher is better).\n") | 124 | f.write("Speed-up factor (higher is better).\n") |
| 124 | f.write("\n") | 125 | f.write("\n") |
| 125 | print_factor_table(f, results_h48.h48_single_thread, results_h48.h48_16_threads) | 126 | print_factor_table(f, results_h48.h48_single_thread, results_h48.h48_16_threads) |
| 127 | f.write("\n") | ||
| 126 | f.write('<img src="img/16threadsspeedupfactor.png">\n') | 128 | f.write('<img src="img/16threadsspeedupfactor.png">\n') |
| 127 | f.write("\n") | 129 | f.write("\n") |
| 128 | f.write("</details>\n") | 130 | f.write("</details>\n") |
| @@ -178,7 +180,7 @@ def plot_multithread_scatter(title, slow, fast): | |||
| 178 | plt.legend(loc = "right") | 180 | plt.legend(loc = "right") |
| 179 | filename = title.replace(" ", "").replace(",", "") + ".png" | 181 | filename = title.replace(" ", "").replace(",", "") + ".png" |
| 180 | plt.savefig(benchmarks_img_dir / filename, dpi=300) | 182 | plt.savefig(benchmarks_img_dir / filename, dpi=300) |
| 181 | plt.show() | 183 | #plt.show() |
| 182 | 184 | ||
| 183 | plot_multithread_scatter("4 threads speedup factor", results_h48.h48_single_thread, results_h48.h48_4_threads) | 185 | plot_multithread_scatter("4 threads speedup factor", results_h48.h48_single_thread, results_h48.h48_4_threads) |
| 184 | plot_multithread_scatter("16 threads speedup factor", results_h48.h48_single_thread, results_h48.h48_16_threads) | 186 | plot_multithread_scatter("16 threads speedup factor", results_h48.h48_single_thread, results_h48.h48_16_threads) |
diff --git a/benchmarks/tables_16_threads.md b/benchmarks/tables_16_threads.md index e9c0d19..49d391a 100644 --- a/benchmarks/tables_16_threads.md +++ b/benchmarks/tables_16_threads.md | |||
| @@ -22,6 +22,7 @@ Speed-up factor (higher is better). | |||
| 22 | |H48 h8 | 7.1 GiB| 8.08| 9.91| 10.40| | | | 22 | |H48 h8 | 7.1 GiB| 8.08| 9.91| 10.40| | | |
| 23 | |H48 h7 | 3.5 GiB| 8.59| 10.30| 10.57| | | | 23 | |H48 h7 | 3.5 GiB| 8.59| 10.30| 10.57| | | |
| 24 | |H48 h6 | 1.8 GiB| 9.60| 10.39| 10.54| | | | 24 | |H48 h6 | 1.8 GiB| 9.60| 10.39| 10.54| | | |
| 25 | <img src="img/16threads.png"> | 25 | |
| 26 | <img src="img/16threadsspeedupfactor.png"> | ||
| 26 | 27 | ||
| 27 | </details> | 28 | </details> |
diff --git a/benchmarks/tables_4_threads.md b/benchmarks/tables_4_threads.md index 9da909c..95ec22c 100644 --- a/benchmarks/tables_4_threads.md +++ b/benchmarks/tables_4_threads.md | |||
| @@ -22,6 +22,7 @@ Speed-up factor (higher is better). | |||
| 22 | |H48 h8 | 7.1 GiB| 3.53| 3.72| 3.81| | | | 22 | |H48 h8 | 7.1 GiB| 3.53| 3.72| 3.81| | | |
| 23 | |H48 h7 | 3.5 GiB| 3.60| 3.78| 3.80| | | | 23 | |H48 h7 | 3.5 GiB| 3.60| 3.78| 3.80| | | |
| 24 | |H48 h6 | 1.8 GiB| 3.77| 3.82| 3.79| | | | 24 | |H48 h6 | 1.8 GiB| 3.77| 3.82| 3.79| | | |
| 25 | <img src="img/4threads.png"> | 25 | |
| 26 | <img src="img/4threadsspeedupfactor.png"> | ||
| 26 | 27 | ||
| 27 | </details> | 28 | </details> |
