These are my reading notes for TAOCP Vol. 4, a brief extension of my reflections after reading the book, accompanied by the code I wrote to deepen my understanding.
Section 7.1.1 examines two specialized functions: Horn (see code) and Krom (see code). Due to their unique structures, the satisfiability of both functions can be determined using linear-time algorithms. A closer analysis reveals the inherent beauty of these approaches; by utilizing elegant data structures—such as linked lists for pending variable assertions and strongly connected component (SCC) graphs for 2-SAT relationships—the deduction proceeds through a series of graceful logical steps, leveraging precise information to reach a definitive conclusion.
Optimization
The implementation for the Krom function is structured in two distinct stages:
first, it invokes Algorithm T (Section 7.4.1.2) to identify all strongly
connected components; this is followed by an efficient verification
procedure—as outlined in Exercise 54—to determine satisfiability. A key
optimization involves checking whether a variable and its complement coexist
within the same component. Specifically, within step T8 (see
T8),
as each new strongly connected component is identified, the initial node is
recorded as \(u_1\) (per Exercise 54, page 86), allowing for an in-place
validation of all nodes within that specific component.
On Section 7.2.2 (Page 30 of Vol 4B), Algorithm B (the C++ code with
goto can be found
here)
introduces a simple yet powerful backtracking scheme. It is built on
properties \((1)\) and \((2)\): namely, that \(P_{l}\) holds whenever
\(P_{l+1}\) holds. This monotonicity allows entire subtrees to be pruned
during the search. A key characteristic of the algorithm is that, at each
level, it systematically iterates over all values in the domain. While this
exhaustive enumeration makes the algorithm conceptually simple and easy to
reason about, it can result in a substantial amount of work during the search
process.
To estimate runtime overhead effectively, memory access can serve as a reliable proxy. For improved code readability, a macro may be implemented to automate the tracking of these access counts.
#ifdef COUNTER
#define MEM_READ(p, i) (counter++, p[i])
#else
#define MEM_READ(p, i) p[i]
#endif
Similarly, a macro can be defined to track memory write operations, ensuring consistent monitoring across the codebase.
Optimization
Optimizing the implementation to use registers (see
code)
instead of auxiliary data structures, such as the A,
B, and C arrays, is an interesting direction that I
explored. In theory, the memory access count, for \(N=16\) queens problem,
should reduce from 34 billion mems to 9 billion mems; however, I did not find
it to be sufficiently fast: 40 seconds for memory version vs 33 seconds
register version (tested on Apple Silicon M4 Max with clang++17
and CXXFLAGS=-DNDEBUG -O3 -march=native -flto). My hypothesis is
that all data already resides within cache lines, making the cost of memory
reads and writes negligible.
In addition to C++, I implemented the register-based bit-vector version in
Go
and
Rust.
For Rust, I explored unsafe implementations, disabled bounds checking, and
enabled aggressive inlining and native optimizations. The measured wall-clock
runtimes are 33 seconds for C++, 47 seconds for Go, and 44 seconds for Rust.
Implementing the algorithm in Rust presented unique challenges due to the
language's lack of a goto statement. This necessitated a shift
toward a structured programming model, leveraging recursive function calls in
conjunction with iterative loops. In the original version, the X
array functions as a set of lightweight stack frames, effectively managing
state in a manner analogous to recursive function calls.
Walker's Backtrack Initially, it was surprising that Walker's method (Algorithm 7.2.2W, The Art of Computer Programming, Vol. 4A) would be recommended, given its higher memory access count. On the surface, both algorithms traverse same number of nodes in the branching tree. In fact, basic backtracking—leveraging register-stored states as seen in Algorithm B*—appears more efficient due to its significantly lower memory overhead.
However, post-optimization benchmarks reveal a stark contrast: Walker's Backtrack completed the task in 4.7 seconds, while Basic Backtrack required 33 seconds. Deep profiling explains this disparity: although node counts are comparable, Algorithm 7.2.2W employs aggressive pruning heuristics. This allows it to trigger backtrack branches only 400 million times, compared to the staggering 16.8 trillion backtrack operations executed by the basic backtrack 7.2.2B* algorithm.
| Profiling | Basic Backtrack | Walker's Backtrack |
|---|---|---|
| # of Mems | 2'282'380'604 | 6'952'497'635 |
| # of Nodes | 1'141'190'302 | 1'141'190'302 |
| # of Mems per Node | 2 | 6.09 |
| # of \(B_3^*\rightarrow B_4^*\) or \(W_3\rightarrow W_4\) | 16'881'494'354 | 400'742'864 |
| Wall time | 33 seconds | 4.7 seconds |
Furthermore, by meticulously aligning my optimization strategy with the memory access counts reported in TAOCP, I was able to significantly reduce memory overhead. By refactoring the logic to carry state within registers across label jumps and implementing strategic early-exit conditions, I eliminated a substantial volume of redundant memory accesses. These refinements proved so effective that the resulting execution speeds actually surpassed the benchmark results documented in the text.
The efficiency gains stem from minimizing redundant data movement. Instead of a monolithic 'load-then-check' approach, the optimized logic performs a lightweight check of the backtrack conditions using minimal state. This early-jump mechanism (see the simple early-jump here) bypasses the heavy memory-load cycle whenever a branch can be pruned, allowing the implementation to outperform standard benchmarks by avoiding the primary bottleneck of state-restoration overhead.
In Section 7.2.2.1 (Volume 4B, page 69), Algorithm X (see code) establishes the fundamental structure of the Dancing Links algorithm. This technique serves as a versatile framework, providing an efficient approach to solving a wide array of combinatorial problems. This implementation is driven by two primary insights:
Applying the Dancing Links algorithm to a practical example, such as Sudoku (see example code), is a highly rewarding exercise. It provides a clear demonstration of how to map complex problem constraints into the discrete items and options required by the framework.
Based on these observations, several potential improvements emerge:
X3
adopts this logic, there remains significant room for further optimization.
In Section 7.2.2.2, boolean Satisfiability (SAT) is studied. It is a well-established and rigorously studied framework. While mathematically intensive, it is a compelling field of study because it serves as a universal interface between high-level applications and algorithmic problem-solving. This abstraction allows innovations in the underlying solver to benefit a diverse range of applications simultaneously.
Example: Dependency Resolution Problem Let's see an interesting problem first (see source). The databases for all packages are as follows:
| Package | Versions |
|---|---|
app | 0 |
sql | 0, 1, 2 |
threads | 0, 1, 2 |
http | 0, 1, 2, 3, 4 |
stdlib | 0, 1, 2, 3, 4 |
And we want to install app:0, which has dependencies
sql, threads, http, and
stdlib. Each dependency, as a package, might have its own
dependencies; and dependencies are different for different versions.
For this case study, we also assume the dependency is recorded with a minimum version and a maximum version. For example,
min,max
app:0
- sql 0, 2
- threads 1, 1
means app:0 needs two dependencies sql and
threads. Any version \(0, 1, 2\) of sql is OK, but
only version \(1\) of threads is allowed for app:0.
With that, the entire dependency tree is as follows
min,max min,max
app:0 threads:1
- sql 2, 2 - stdlib 2, 4
- threads 2, 2 threads:2
- http 3, 4 - stdlib 3, 4
- stdlib 4, 4 http:0
sql:0 - stdlib 0, 3
sql:1 http:1
- stdlib 1, 4 - stdlib 0, 3
- threads 1, 1 http:2
sql:2 - stdlib 1, 4
- stdlib 2, 4 http:3
- threads 1, 2 - stdlib 2, 4
threads:0 http:4
- stdlib 2, 4 - stdlib 3, 4
With all the problem setup now, we could map the problem into SAT (full code can be found here):
http
(min:3, max:4), we can write a disjunction of all allowed
versions, i.e.,
\[\hbox{http}_3 \vee \hbox{http}_4\]
Then the fact either of them is installed (true) means the
disjunction is true.
http, we
express the dependency as
\[\hbox{app}_0 \rightarrow \hbox{http}_3 \vee \hbox{http}_4\]
which is equivalent to
\[\overline{\hbox{app}_0} \vee \hbox{http}_3 \vee \hbox{http}_4.\]
sql with three versions \(0, 1, 2\), only one version is
allowed to be installed, which can be expressed as
\[
\overline{\hbox{sql}_0 \wedge \hbox{sql}_1} \wedge
\overline{\hbox{sql}_0 \wedge \hbox{sql}_2} \wedge
\overline{\hbox{sql}_1 \wedge \hbox{sql}_2}
\]
which is same as
\[
(\overline{\hbox{sql}_0} \vee \overline{\hbox{sql}_1}) \wedge
(\overline{\hbox{sql}_0} \vee \overline{\hbox{sql}_2}) \wedge
(\overline{\hbox{sql}_1} \vee \overline{\hbox{sql}_2})
\]
Satisfiability by Watching Algorithm B (see code) is a particularly elegant optimization within this domain. In a clause consisting of a disjunction of literals, only one variable needs to be "watched" to monitor whether the clause is satisfied or at risk of becoming a conflict. This approach makes backtracking highly efficient, as the solver only needs to visit clauses containing the specific variable being unassigned, rather than scanning all clauses. Furthermore, if a watched literal becomes false, the solver can cheaply update the watch to another non-false literal. By leveraging the inherent structure of Conjunctive Normal Form (CNF), this mechanism significantly reduces the overhead of undo operations during search.
There is a distinct beauty in Algorithm 7.4.1.2T; it avoids the
heavy-handedness of global scans in favor of a singular, elegant pass. By
allowing the LOW value to cascade through the graph's hierarchy,
the algorithm listens to the local state of each vertex to pinpoint the exact
moment a component is born. It exemplifies the brilliance of an algorithm that
makes 'smart' decisions not through complexity, but through the perfect
placement of simple information.
Iterative DFS Upon closer inspection, Algorithm T follows an iterative Depth-First Search (DFS) structure characterized by precise stack management and explicit control flow jumps. This design ensures that all memory allocations, stores, and loads remain transparent. However, these advantages come with a trade-off: the algorithm requires rigorous engineering to maintain critical invariants. I have documented these invariants extensively within the codebase (see code) to ensure clarity and maintainability.
Recursive DFS In contrast, it is more common to conceptualize and implement this process using recursive function calls, as seen in the standard Wikipedia implementation (see pseudocode here). However, this approach carries the risk of stack overflow when processing large graphs and tends to obscure the inherent overhead of frequent function calls.