Faster Search: Live Domains as Bitsets

For a long time my CSP solver was “fast enough”, mostly because I threw 9x9 Sudokus and relatively tame crosswords at it. Recently I started pushing the crossword builder harder: larger word lists, full arc consistency, and searching for higher-scoring word fills instead of stopping at the first valid grid. My poor free-tier GCE VM was not thrilled.
Profiling made the bottleneck obvious. The solver was spending more time hashing Go maps, allocating temporary state, and checking words one by one than actually exploring the search tree. Over a series of posts, I’ll walk through the recent changes that fixed that:
- Packing live domains into bitsets (this post).
- Bitmask constraint propagation instead of checking values one by one.
- Flattening search state from Go maps into dense slices, and speeding up backjumping along the way.
Maps, maps everywhere
When I first wrote the solver in Go, I leaned on Go’s built-in maps everywhere to keep the code easy to read. Need a variable’s live domain? map[int]bool. Need the set of variables awaiting propagation? map[*Variable]bool. Need to remember what propagation pruned at this search node so search can undo it on backtrack? You guessed it - another map.
For a 9x9 Sudoku, a variable’s domain has 9 values, so map overhead is small enough not to care. For a crossword, a single word in the puzzle can easily have 15,000 candidates (the exact number depends on the word’s length and the dictionary). Multiply that by hundreds of thousands of search steps and things get ugly fast:
- Whenever a word was placed, constraint propagation looped over related variables and called
Supported()on every remaining word in their live domains, one word at a time (“how about ‘aardvark’? nope. ‘abacus’? nope…”). Even crossing off a single duplicate word in sparse all-different meant checking 15,000 candidates just to eliminate one. - Stepping deeper into the search tree allocated fresh maps to record pruned values, and every prune or restore acquired a mutex so the websocket UI could safely read progress.
- When a 15,000-word domain finally wiped out, backjumping merged thousands of small maps to figure out which earlier decisions were responsible.
Most of the speedup came from two closely related representations: a bitset (storing a set of integers as individual bits inside 64-bit uint64 integers, where bit i is 1 if value i is present) and a bitmask (a precomputed bit pattern used to test or filter 64 values at once with bitwise operations like AND and OR).
Everything else builds on the domain representation, so let’s start there.
Turning live domains into bits
Each variable’s static domain is an integer range [From, To]. Instead of storing live values in a map, liveDomain now packs 64 values into each 64-bit bucket, offset by the start of the range:
type liveDomain struct {
spec DomainSpec
bitset []uint64
liveCount int
v *Variable
}
Checking whether a value is live, pruning it, or restoring it becomes a single bit operation on that bucket, updating the live count only when that bit actually flips.
Scanning bits in hardware
Packing domains into 64-bit buckets also lets me use Go’s math/bits package, which compiles down to single CPU instructions:
- Finding the first live value scans for the first non-zero bucket and uses
TrailingZeros64to locate its lowest set bit. - Iterating over live values takes a
visitcallback (which returns false to stop early), skips empty 64-value buckets in a single check, and steps directly from one set bit to the next in non-empty buckets:for bitsToVisit != 0 { bitOffset := bits.TrailingZeros64(bitsToVisit) if !visit(bucketStartVal + bitOffset) { return false } bitsToVisit &= bitsToVisit - 1 // clear lowest set bit } - Picking a random live value for the random value heuristic used to require walking values one by one. Now it hops over whole buckets using
OnesCount64to count how many live values are in each bucket, stopping at the one that contains the target index. Across 15,000 words, that takes around 235 bit-counts instead of thousands of loop iterations.
Subtle bits (pun intended)
Simple enough on paper, right? Sorta. Getting bitset domains right had a few non-obvious wrinkles:
- When a domain’s size isn’t a multiple of 64, the unused high bits in the final bucket must be zeroed out on initialization. Leaving them set to 1 inflates bit counts and tricks inverted mask checks into visiting out-of-range values past the end of the domain.
- When search assigns a variable, it’s tempting to just zero out all the other bits in its bitset. Easy peasy, right? … except on backtrack, undoing that assignment would have no idea which bits were wiped out by the assignment versus pruned ten levels higher up the tree, unless I recorded thousands of extra undo entries on every assignment. Instead, the variable tracks whether it is assigned (and to what value) in separate fields on top of the frozen bitset, keeping both assigning and clearing constant-time.
- An already-assigned variable can still have its value pruned, for example when an objective function tightens its cost bound right after an assignment. A separate boolean flag records whether the assigned value itself was pruned so the variable reports 0 live values left (a wipeout) without touching the bitset, and restores cleanly on backtrack.
- Pruning values while iterating over a domain is safe without copying the slice: ranging over the bucket slice copies each 64-bit bucket by value before visiting its bits, so clearing bits in the underlying slice inside the callback doesn’t disturb the bucket currently being scanned.
With live domains packed into contiguous uint64 slices, constraints can now filter thousands of candidates at once instead of polling them one by one. I’ll look at how that works next in bitmask constraint propagation.