| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
There was a small (but kinda silly) error in the prunin table
generation for H48 solvers, resulting in some positions showing
a higher lower bound than they actually had. This means that the
solvers where in theory broken and could have skipped some solutions
- but we have not found any example, as this would be an extremely
rare situation. This affected all tables from H48h2 to H48h11.
This bug was found by LLM-based coding analysis in the context of
the development of egg-solver: https://github.com/ArhanChaudhary/egg-solver
Thanks to Arhan Chaudhary for reporting the bug.
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
MSVC is not fully C11-compliant, even when compiling with /std:c11.
Some changes were needed to make the codebase compatible. Notably, the
notation a[static N] and a[n] for function parameters of array type is
not supported, so that had to be hidden behind a macro. Atomic types
are also an experimental feature, apparently, but at least they work
with the correct compiler flag.
One thing that MSVC does well, however, is warning on integer conversions
on /W4 level. I am not sure if Clang and GCC have something similar,
so I took this chance to fix some of these.
|
| | |
|
| | |
|
| |
|
|
| |
Ask before overwriting a table file.
|
| | |
|
| |
|
|
|
|
|
| |
- Use multithreading (works with a sufficiently recent version of
the Microsoft developer tools / C SDK).
- Detect CPU architecture and use AVX2 or NEON when appropriate.
- Automatically detect python installation path.
|
| |\ |
|
| | |
| |
| | |
Fix various typos in README.md (thanks to aashvikt).
|
| |/ |
|
| | |
|
| |
|
|
|
|
|
|
|
| |
With this commit we re-structure how the node expansion in the
H48 solution search works to allow prefetching of pruning values,
showing performance improvements in the range of 30-45% on x86,
depending on table size and solution length.
A small bug fix related to appending solutions is included in this commit.
|
| | |
|
| | |
|
| | |
|
| | |
|
| |\ |
|
| | |
| |
| |
| |
| |
| |
| |
| |
| | |
Add a trivial check to H48 solver. The benchmarks show, surprisingly,
a more noticeable improvement for larger solvers (h10, h11). I was expecting
it to be more noticeable for smaller solvers.
It is likely that this change is irrelevant to performance and all changes
in the benchmark results are just random chance.
|
| |\| |
|
| | | |
|
| |/ |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
(See the last 12 commits or so)
H48 now uses interleaved fallback tables, similarly to nxopt / vcube.
This allowed us to simplify the code (we don't use k != 2 anymore for
H48) and gives some nice performance improvement, although repeated
measurements show inconsistent results. The actual speed up depends on
the table, and it is more pronounced on larger versions of the solver.
The nasty part about using interleaved tables is that they are the
most efficient when they are aligned in memory to 512 bits, but the
core library defers memory management to the implementor, so there is
no way to ensure this. For example, any application that wants to save
the tables to a file and then re-load them on a subsequent run (such
as our shell and tools) should make sure to load the data in a 512-bit
aligned memory buffer. The best we can do on the library side having
our main lookup table be 512-bit alinged within the whole solver data
(which includes e.g. cocsepdata and a preamble).
I have also moved some conditionals around in the various checks in the
search dfs hoping to improve the performance further, but the results
have been barely noticeable.
The benchmarks have been updated. Moreover, there is now a way to re-run
them with a single script (see the updates in the benchmarks folder
for details).
Further attempts at optimizing the code via known techniques (such as
prefetching) have failed, but I'll come back to this.
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| |\ |
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
for H48.
This commit fixes two bugs:
- A bug that caused duplicates solutions for symmetric scrambles.
- An overflow in the maxsols parameter for the H48 solver, which
caused it to find much fewer solutions than existed.
Moreover, the H48 solvers has been improved by reducing by symmetry not
only from the starting position, but also up to the first 4 moves.
|
| | | |
|
| |/ |
|
| | |
|
| | |
|
| | |
|
