amling search program principles discussion / brain dump

amling · Post by **amling** » 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.

Post by **Sokwe** » October 19th, 2025, 1:20 am

amling wrote: October 18th, 2025, 3:24 am 3.77x memory reduction is amazing but I'm not sure we're willing to pay a 7x slowdown for it.

That depends on whether there are any interesting searches that were restricted by memory limits, rather than time. If an interesting search takes only an hour to run out of memory, but could complete with a 3.77x memory reduction, then it might be worthwhile to run such a search even with a 7x slowdown. I doubt I can think of any real examples, since until recently I was restricted to ~5GB of RAM, so most of my searches hit memory limits long before time became an issue.

Most of the examples I was interested in were arbitrary-width searches, such as a side-to-side search for a p1 photon in B2458/S13467 (the last unsolved rule without S0 in the Life-like p1 photon project). Unfortunately, this doesn't work with your simplifying assumption of a fixed board. Perhaps it could be used to determine the minimum staggered height for a period-5 2c/5 spaceship, although I'm not sure how long the "height 9.2" search took, and perhaps this problem is better suited for normal LLSSS on your 1TB RAM machine.

Katrina · Post by **Katrina** » October 26th, 2025, 3:08 pm

Are you planning on adding support for MAP rules any time soon? I'd like to find some discoveries in a few of my favorite MAP rules.

amling · Post by **amling** » October 27th, 2025, 6:35 pm

Sylvani wrote: October 26th, 2025, 3:08 pm Are you planning on adding support for MAP rules any time soon? I'd like to find some discoveries in a few of my favorite MAP rules.

I'm not sure "planning" describes my approach to software development although that's neither here nor there.

My best efforts to search the wiki for "MAP" and figure out what is meant led me to the "Non-isotropic_rule" page which suggests we're talking about the 2^512 rules for arbitrary, deterministic, square grid range 1 rules. This is within the bounds of what the existing LLSSS engine can do but there is no way to specify such a rule with the --rule argument parser which makes this just a small UI change, at least assuming we're both talking about the same thing.

I'm at an awkward moment in (real) life right now which makes it unlikely I will get to this just right now but it's a small change I'm happy to take on later if it will be of use to anyone.

Unfortunately what I found on the wiki is somewhat short of a clear and objective spec so it would be helpful to me if you have example (specifically non-INT) rules and ships, ideally small and with a low period to serve as test cases, both for my understanding of the MAP string format and for the full LLSSS search itself. It's possible some digging in the forums would allow me to provide this myself, but it would be a favor to me to save me that work.

Finally, LLSSS named geometries are fixed for ships traveling certain directions (f2b NNW, s2s W or NW, b2f SSE) and so you may end up having to reorient rules or specify "raw" geometries depending on what you want to search.

amling · Post by **amling** » October 29th, 2025, 7:34 pm

Sylvani wrote: October 26th, 2025, 3:08 pm Are you planning on adding support for MAP rules any time soon? I'd like to find some discoveries in a few of my favorite MAP rules.

I found this post which convinced me my initial guesses about which way certain bit orderings would go are almost certainly correct.

I've sketched a quick parser for when --rule arguments are "MAP" plus 86 letters but I'm sort of missing examples to test it on. That linked post gives a MAP equivalent of B3/S23 which I have verified my code parses into an identical rule table to "B3/S23". The only other MAP string I could find anywhere was "MAPAAD//zAwPz8AAP//MDA/PwAA//8AAP//AAD//wAA//8AAD8/AAD//wAAPz8AAP//wMD//wAA///AwP//AAD//w". I found a pyramidal family of c/2 south partials (had to search with "raw" geometry "raw:1:0:0:0:1:2:0:0:1") and verified they simulate in life viewer as LLSSS expects.

I've pushed the changes to codeberg just now. I would really appreciate it if you could verify them or provide some sort of examples (rules, ships, partials, anything) for more test cases.

As a note about LLSSS internals, this MAP string is almost as general as LLSSS can support without a severe overhaul. The assumptions of 2 states and range 1 are built in very deeply and generalizing either of them would basically require rebuilding the entire program from scratch. Within those assumptions you could imagine there instead being 2^2^10 "rules" describing which 10 cell neighborhoods (9 cells in present plus one cell in future) are permitted. MAP strings require for a given 9 cell present that exactly one of the two possible extensions to 10 cell neighborhood is allowed (for 2^2^9 rules), whereas LLSSS can be configured to allow neither (forbidden 9 cell neighborhood) or both (non-deterministic 9 cell neighborhood).

R2INT · Post by **R2INT** » October 30th, 2025, 1:30 pm

Here is a MAP rule with a (0,1)c/3, a (0,2)c/6, a (0,1)c/4, a (-1,1)c/3, and a (0,-1)c/2: