Faster Search: Bitmask Constraint Propagation

In the previous post, I replaced map-backed live domains with []uint64 bitsets. That makes checking and flipping individual domain values cheap, which is great, except the original propagation loop was still polling Supported() on every single remaining value one at a time.

When a word has 15,000 candidates, calling Supported() 15,000 times just to cross off a single candidate is a lot of wasted work. In this post I’ll flip that around: letting constraints push prunings directly in bulk, and using precomputed bitmasks (bit patterns stored in uint64 slices) to filter thousands of candidates at once.

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:

  1. Packing live domains into bitsets (this post).
  2. Bitmask constraint propagation instead of checking values one by one.
  3. Flattening search state from Go maps into dense slices, and speeding up backjumping along the way.

Testing

Testing is almost universal in software development, yet it’s common to treat it like a chore, or an after thought. Sure, test-driven development (TDD) is a means to influence what the public interface should look like by having the developer pretend the class already exists, and then implementing it to make the tests pass… but how often is TDD applied? And how often is it applied consistently? What’s the magic test-coverage percentage that you (or your lead) are satisfied with, and why that number, in particular? What the heck is “shifting left”, and how religiously shoud you stick to the test pyramid? Can automated testing happen in production?

All Different Variants

In the earlier posts I’ve described some of the basic ideas behind CSPs:

  • how the problems are represented using variables and constraints,
  • how the solver searches for a solution by building up the search tree,
  • how heuristics guide the search, and
  • how constraint propagation helps eliminate parts of the search space that will not contain solutions.

In this post I will look at how modeling the problem itself can have a significant influence on how quickly the solver is able to find a solution. In particular, I’ll talk about different ways of implementing the all-different constraint, and look at the various implementations’ performance characteristics.