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