aboutsummaryrefslogtreecommitdiff
path: root/doc/h48.md
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2025-12-17 17:36:16 +0100
committerSebastiano Tronto <sebastiano@tronto.net>2025-12-17 17:36:16 +0100
commitec9593e2ff0856d78b37df3a977a753be82bfddc (patch)
tree684dad42207f48125db40ce0afb32046cdba1726 /doc/h48.md
parentac3a91f4f173e7a38c70d5cd0caf5a025642312b (diff)
downloadnissy-core-ec9593e2ff0856d78b37df3a977a753be82bfddc.tar.gz
nissy-core-ec9593e2ff0856d78b37df3a977a753be82bfddc.zip
Fix alignment
Diffstat (limited to 'doc/h48.md')
-rw-r--r--doc/h48.md12
1 files changed, 12 insertions, 0 deletions
diff --git a/doc/h48.md b/doc/h48.md
index 2487aad..d9ef192 100644
--- a/doc/h48.md
+++ b/doc/h48.md
@@ -225,6 +225,8 @@ of 1, 2 or 3 can be used directly as a lower bound of b+1, b+2 and b+3
225respectively. However, a value of 0 could mean that the actual lower 225respectively. However, a value of 0 could mean that the actual lower
226bound is anything between 0 and b, so we cannot take b as a lower bound. 226bound is anything between 0 and b, so we cannot take b as a lower bound.
227 227
228#### Fallback tables
229
228To be able to still use some sort of pruning value even when we get a 230To be able to still use some sort of pruning value even when we get a
2290 read, we use a **fallback table**. Inspired by nxopt, this table is 2310 read, we use a **fallback table**. Inspired by nxopt, this table is
230interleaved with the main table for cache efficiency: every 254 entries 232interleaved with the main table for cache efficiency: every 254 entries
@@ -235,6 +237,16 @@ when looking up the minimum value in the fallback table after a 0 read.
235Smaller lines (of 256 or 128 bits) have been tried, but they do not 237Smaller lines (of 256 or 128 bits) have been tried, but they do not
236give any significant improvement over 512 bit lines. 238give any significant improvement over 512 bit lines.
237 239
240This trick provides the gratest performance benefits if the main pruning
241table is properly aligned. Unfortunately, as a design choice, the
242solver is implemented here as a library that defer all memory allocation
243business to the implementor. We do make sure that the table is properly
244aligned in the programs provided in this repository (for example, the
245rudimentary shell and the tools), but we do not enforce this in the
246main library code.
247
248#### Additional (fast) lookups
249
238Moreover, as an additional heuristic, in case of a 0 read we also look 250Moreover, as an additional heuristic, in case of a 0 read we also look
239up another pruning value in a table that takes into account only the 251up another pruning value in a table that takes into account only the
240position of the edges. This table is small (around 1MB), so repeated 252position of the edges. This table is small (around 1MB), so repeated

Generated with cgit - Back to sebastiano.tronto.net