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.

1 files changed, 25 insertions, 8 deletions

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.
+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).
 
-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.
+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.