More progress on the Finite Projective Plane (incidence matrix) generation from last week. There already exists an algorithm to generate boards of order p+1 where p is prime. It is stateless, so with CUDA we can generate huge boards in seconds since all you need is the x, y position and board size. 258x258 under 3s!

However, p+1 isn’t the only sequence. It seems by our observations that the fermat numbers also generate valid boards, using our “naïve” algorithm.

Unfortunately 3x3, 5x5, and 17x17 might not contain all the nuggets of generality to find a nice algorithm like the p+1, so we’re gonna generate the next up: 257x257. We’ve been improving the naïve algorithm since it is too slow. (The resulting image would be 65793x65793)

• Rather than allocating the 2d boolean grid, we represent where the true elements would be using row and column indexes. This is okay because of the constraint which limits how many true elements can be in a row/column
  • benefit 1 — less memory usage: “O(2n)” vs O(n²) ((for 257x257: 129MiB vs 4GiB))
  • benefit 2 — faster column-major lookups (flamegraph spent a lot of time sitting in iterators)
  • overall speedup: about 2.7x
• Speed up index lookup with binary search
  • The index list is sorted by nature. To exhaustively check a dot is valid, it checks n² spots in 2 lists of size n. Slightly more expensive than the grid given the 2 index lists. Rather than slice::contains, use slice::binary_search(...).is_ok()
  • overall speedup: about 2.1x

Next steps:

• Assume a square grid and exploit its diagonal symmetry to treat row lookups as column lookups
• Use multi threading to gain a partial speedup
  • Essentially if row 1 is 50% completed, row 2 can be up to 50% completed.
  • I think you get different speeds depending whether the threads and symmetry folds are both row/column major or one is row-major and the other is column-major. My gut says both need to be aligned because there’s less waiting involved.