Re: amling search program principles discussion / brain dump
Posted: October 18th, 2025, 3:24 am
I sketched a wild cut of the code where I changed all the main datastructures entirely. I moved all of the spine store, the bcols, and jcols to a new "bit tree" datastructure, optimized somewhat more for memory efficiency with the assumption of few writes.
I'm going to elide the details about root labels and geometry and just talk about the typical cases (default build, normal geometry, pretend all fixed board roots are identical, etc.) from here on in.
As things are right now the spine store stores streams of bits which are expanded one at a time. These are thought of as filling in a stack of "tiles" in W order. How it does this storage doesn't super matter as it's never come up performance-wise. bcols are stored as a pair of u32 indices into the spine store. jcols are stored as a pair of u32 indices into the bcols on either side (and the shared middle spine store pointer matches). This pair of u32s for each jcol entry is quite expensive and even the pair of u32s in the bcols is not great.
As an example, consider the 2c5-wing.in searches from far above. Expanded 0/4/2 with the existing code at the peak moment of memory the internal view is 3.22 GB. The jcols are 2.13 GB, the bcols are 580 MB, the spine store is 99 MB, and various other structures that are part of the expansion algorithm make up the rest. As searches get bigger this disparity of jcols over bcols and bcols over spine store widens but even in this, a middling search, bcols are still relevant.
The new "bit tree" structure is somewhat like the old spine store in that it's sort of storing streams of bits, but this time it's stored much more compressed. A bit tree knows its bit width W (1 for spine store, 2 for bcol, 3 for jcol) and thinks of itself as storing a stream of W-grams of bits. It stores these as a stack of generations. Each generation is a bit vector with a total of 2^W bits corresponding to each nonzero bit in the parent generation (indicating the presence/absence of the 2^W possible extensions). Each generation also has some extra index jiggerpokery to help translate quickly between absolute bit indices in that generation (which you'd use to look up in this generation's bit vector), and nonzero bit indices in that generation (which you'd use to find absolute indices of children in the next generation). This does mean keeping a lot of generations around (one per "w pos" per bit tree), but they are so very dense that it works out to be pretty efficient. With this the spine store and bcols aren't really doing as much as they used to (bcols are just projections of jcols and spine store is just a union of the projections of everything), but they're still used (via indices into themselves) to coordinate other sorts of data stored in other code.
The new code, for the same 2c5-wing.in expanded 0/4/2, reaches only an internal view of 874.91 MB which is an enormous, enormous savings from 3.22 GB (3.77x!). It's even possible this would give us another crack at "hollow" jcols where the jcols are removed entirely and we do CA joins between adjacent bcols (whose tree forms are somewhat more amenable to this than the old bcol format). At that 874.91 MB moment it's 478.51 MB jcols, 79 MB bcols, 5.07 MB spine store, and the rest is taken up by expansion algorithm stuff. If we did hollow jcols I'd expect to save the 478.51 MB directly but also 273.01 MB of the expansion structures maybe putting us at just 123.39 MB (this is the same search that took 35 GB so long ago before the one bit at a time changes).
Unfortunately this may all be premature as I'm not sure I can get the performance up to snuff. This 0/4/2 search with old code is ~187s. The first cut of the new stuff I had run took 1900s, about 10x (10x also consistent for the 0/3/2 search). I did some work to clean up the worst offenders and to try to fix it parallelizing poorly, but even after about a half of a day of effort I've only got it down to maybe 7x slower and unfortunately that time is all over (i.e. the parallel tree walk algorithm which is the common denominator between everything is almost certainly the problem and I have spent nearly the entire time on trying to optimize it). 3.77x memory reduction is amazing but I'm not sure we're willing to pay a 7x slowdown for it.
Also unfortunately, this is on a wacky proof of concept branch where I've deleted like 95% of the code/features to make the rewrite as simple as possible (keeping just fixed board searches, firstest partials to see what's happening, and almost nothing else). I'm not sure this is something I can reasonably abstract out so it can co-exist with the current code as it touches every main data structure in the program.
I guess I'm gonna sleep on it and see if I can't think of some other trick to pull off to either make this perform better or integrate with the main codebase.
I'm going to elide the details about root labels and geometry and just talk about the typical cases (default build, normal geometry, pretend all fixed board roots are identical, etc.) from here on in.
As things are right now the spine store stores streams of bits which are expanded one at a time. These are thought of as filling in a stack of "tiles" in W order. How it does this storage doesn't super matter as it's never come up performance-wise. bcols are stored as a pair of u32 indices into the spine store. jcols are stored as a pair of u32 indices into the bcols on either side (and the shared middle spine store pointer matches). This pair of u32s for each jcol entry is quite expensive and even the pair of u32s in the bcols is not great.
As an example, consider the 2c5-wing.in searches from far above. Expanded 0/4/2 with the existing code at the peak moment of memory the internal view is 3.22 GB. The jcols are 2.13 GB, the bcols are 580 MB, the spine store is 99 MB, and various other structures that are part of the expansion algorithm make up the rest. As searches get bigger this disparity of jcols over bcols and bcols over spine store widens but even in this, a middling search, bcols are still relevant.
The new "bit tree" structure is somewhat like the old spine store in that it's sort of storing streams of bits, but this time it's stored much more compressed. A bit tree knows its bit width W (1 for spine store, 2 for bcol, 3 for jcol) and thinks of itself as storing a stream of W-grams of bits. It stores these as a stack of generations. Each generation is a bit vector with a total of 2^W bits corresponding to each nonzero bit in the parent generation (indicating the presence/absence of the 2^W possible extensions). Each generation also has some extra index jiggerpokery to help translate quickly between absolute bit indices in that generation (which you'd use to look up in this generation's bit vector), and nonzero bit indices in that generation (which you'd use to find absolute indices of children in the next generation). This does mean keeping a lot of generations around (one per "w pos" per bit tree), but they are so very dense that it works out to be pretty efficient. With this the spine store and bcols aren't really doing as much as they used to (bcols are just projections of jcols and spine store is just a union of the projections of everything), but they're still used (via indices into themselves) to coordinate other sorts of data stored in other code.
The new code, for the same 2c5-wing.in expanded 0/4/2, reaches only an internal view of 874.91 MB which is an enormous, enormous savings from 3.22 GB (3.77x!). It's even possible this would give us another crack at "hollow" jcols where the jcols are removed entirely and we do CA joins between adjacent bcols (whose tree forms are somewhat more amenable to this than the old bcol format). At that 874.91 MB moment it's 478.51 MB jcols, 79 MB bcols, 5.07 MB spine store, and the rest is taken up by expansion algorithm stuff. If we did hollow jcols I'd expect to save the 478.51 MB directly but also 273.01 MB of the expansion structures maybe putting us at just 123.39 MB (this is the same search that took 35 GB so long ago before the one bit at a time changes).
Unfortunately this may all be premature as I'm not sure I can get the performance up to snuff. This 0/4/2 search with old code is ~187s. The first cut of the new stuff I had run took 1900s, about 10x (10x also consistent for the 0/3/2 search). I did some work to clean up the worst offenders and to try to fix it parallelizing poorly, but even after about a half of a day of effort I've only got it down to maybe 7x slower and unfortunately that time is all over (i.e. the parallel tree walk algorithm which is the common denominator between everything is almost certainly the problem and I have spent nearly the entire time on trying to optimize it). 3.77x memory reduction is amazing but I'm not sure we're willing to pay a 7x slowdown for it.
Also unfortunately, this is on a wacky proof of concept branch where I've deleted like 95% of the code/features to make the rewrite as simple as possible (keeping just fixed board searches, firstest partials to see what's happening, and almost nothing else). I'm not sure this is something I can reasonably abstract out so it can co-exist with the current code as it touches every main data structure in the program.
I guess I'm gonna sleep on it and see if I can't think of some other trick to pull off to either make this perform better or integrate with the main codebase.