From 9a013b7c68f94e6be0fe8748c9012a441fe0273f Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 12 Jan 2026 18:09:43 +0100 Subject: Improve performance of H48 solver with prefetching 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. --- doc/h48.md | 35 ++++++++++++++++++++++++++--------- 1 file changed, 26 insertions(+), 9 deletions(-) (limited to 'doc/h48.md') diff --git a/doc/h48.md b/doc/h48.md index d9ef192..694a07d 100644 --- a/doc/h48.md +++ b/doc/h48.md @@ -251,15 +251,18 @@ Moreover, as an additional heuristic, in case of a 0 read we also look up another pruning value in a table that takes into account only the position of the edges. This table is small (around 1MB), so repeated accesses to it are not too slow. In practice, this gives a small speed up -of around 5%. More tables could be used to refine the fallback estimate, -but each additional table leads to longer lookup times, especially if -it is too large to fit in cache. - -Previous versions of this implementation (up to commit 6c42463, or -to version 0.2) also included the possibility of a table with 4 bits -per entry, at least for the `h0` case. Such tables did not require -a fallback lookup, but due to their large size they were not less -efficient. Therefore, they have been removed. +of around 5% for random scrambles. However, for small solvers (low values +of h) and positions where corners are close to solved, this fallback +table gives dramatic improvements (up to a factor of 1000x in some +manual tests). + +More tables could be used to refine the fallback estimate, but each +additional table leads to longer lookup times, especially if it is too +large to fit in cache. Previous versions of this implementation (up +to commit 6c42463, or to version 0.2) also included the possibility of +a table with 4 bits per entry, at least for the `h0` case. Such tables +did not require a fallback lookup, but due to their large size they were +not less efficient. Therefore, they have been removed. ### Estimation refinements @@ -312,6 +315,20 @@ inverse position*, then the coordinate on the normal position has not changed. Thus if we keep track of the last computed pruning value, we can reuse it and avoid an expensive table lookup. +### Pruning pipeline and prefetching + +To improve the memory access pattern and exploit +[prefetching](https://en.wikipedia.org/wiki/Cache_prefetching) +opportunities, we don't expand each neighbor one by one in the +pruning phase. Instead, we employ a *pruning pipeline*, where we +first compute the cube and inverse position for each neighbor, and +then we proceed through a series of stages, at each of which we +compute some prune off some nodes and we pre-compute the data +necessary for the next step. + +This pipeline-based strategy gives an speedup of around 25%. +Adding manual prefetching, we get an additional 20% speedup. + ### Other optimizations The H48 solver uses various other optimizations. -- cgit v1.3