amling search program principles discussion / brain dump

[amling]

I reran the p3 statorless maxpop 140 search under MDSE V2 as another test/benchmark. Both found all four orientations as expected and produced identical column sizes the entire way.

Last time I believe this had taken ~20 hours and reached VmPeak ~300 GB, although that may have been on a different machine. This time it (MDSE V1) took ~22h and reached VmPeak 328.26 GB while MDSE V2 took ~46h and reached VmPeak 87.40 GB.

87.40 GB is just barely in the range for what I think of as more "normal" computers, e.g. for most (if not all) of the last decade my main personal laptop has had at least 64 GB and I think this search would be doable in 64 GB plus swap, at least if you really wanted it. The internal estimates of memory at that VmPeak were:

Code: Select all

Memory: total 81.15 GB (ss 75.46 MB, bcol 2.64 GB, col 20.34 GB, left_edge 1.61 KB, right_edge 1.61 KB, ss_views 750.45 MB, left_edge_long 8 B, right_edge_long 8 B, closure_left_bcol_long 1.32 GB, closure_right_bcol_long 1.32 GB, left2_bcol_long 1.32 GB, right_bcol_long 1.32 GB, right2_bcol_long 1.32 GB, middle_col_long 12.69 GB, left2_col_long 12.69 GB, right_col_long 12.69 GB, right2_col_long 12.69 GB)

More than half of it is in those last 4x12.69 GB xxx_col_long (middle_col_long through right2_col_long) which is indeed a tough part of expansion. If we were willing to change mid_steps semantics slightly we could have a middle_bcol_long (bcol instead of [j]col) which would save one of the four. I struggle to imagine how to save more than that other than of course MDSE V3. In a hypothetical MDSE V3 we imagine we would save col (20.34 GB) plus all four of those xxx_col_long (4x12.69 GB) and thus might hope to save 75.1 GB, or almost all of it. MDSE V3 is certainly my next big aspiration.

22h -> 46h is a much better ratio than I might have expected from previous benchmarking. For both runs the vast majority of time was in maxpop r2l/l2r_weights which was ~2.4x slower. Next biggest on the V2 side is default pre-partial build_path which was ~3.7x. It falls off pretty rapidly after that. Both of those are just parallel walks over [j]cols so I don't understand why they got such different ratios. I'm not entirely sure what to make of all of it, other than to hope that some of better ratio is due to search bigness rather than just search structure and that maybe other big MDSE V2 searches will do better than in the benchmarking I had before this.

[NNlk05]

Is zram effective against LLSSS? It works pretty well with qfind, in my experience.

[amling]

Is zram effective against LLSSS? It works pretty well with qfind, in my experience.

I had never even heard of this "zram" before. I don't know enough about qfind's memory representation to extract much meaning from that, although it's interesting to hear.

LLSSS's memory is mostly in "jcols" and outside of that mostly in "bcols".

Under default configuration (MDSE V1 w/o older "jcols V2"), both are just giant blocks of u32 indices into other structures. I would assume they are more or less unpatterned other than remaining within the range of legal values. That is some redundancy as the range of legal values is not generally [0, 2^32), but it's not clear to me if it's enough to be a real win.

EDIT: Thinking more on this I realize that jcols have a little pattern: every other u32 is a "left" index and those are stored ascending and likely have a wealth of adjacent repeats. Every other other u32 is a "right" index and these are stored ascending for a fixed left index which may or may not add up to anything. I think the bottom line here is still "maybe", although it's a little more optimistic.

Under the older "jcols V2", jcols are stored pretty efficiently once they overflow u32s (lower 32 bits in a block of u32s and higher bits generally packed quite carefully in a separate place). As jcols are most of memory I would be very pessimistic about searches that hit that u32 limit benefitting from zram.

Under MDSE V2 it's all BitTrees instead which I suspect are gonna be extremely random-looking and I would be similarly pessimistic.

Of course speculation is no substitute for data. My interest is certainly piqued and I would love to hear how it goes if anyone tries it, but I have enough on my plate that I'm not gonna rush off and do it.

[NNlk05]

I had never even heard of this "zram" before. I don't know enough about qfind's memory representation to extract much meaning from that, although it's interesting to hear.

https://en.wikipedia.org/wiki/Zram

[amling]

I've sketched "simple_vv" and "simple_vv_diag" geometries, pushed to codeberg just now as of 2d06e9e4aa72. simple_vv is is U=X, W=Y, e.g. "c6k-1" can be written instead as "simple_vv:-1:-2:6", a hypothetical "c6c-1" could be "simple_vv:-1:-3:6", etc. simple_vv_diag is U=X-Y, W=X+Y, e.g. "c6k-1/U=X-Y/W=X+Y" can be written instead as "simple_vv_diag:-1:-2:6".

I'm not entirely sure what, if anything, we should add to the tutorial about this. It's easy enough to add rows to the table labelled "simple_vv[_diag]:VX:VY:VT" with "Spaceship direction" "custom" and "Search direction" either "south" or "southeast". The problem in my mind is what to say about the difference between named geometries and their simple_vv analogues. It's sort of a mess where some are identical to their counterparts (e.g. c6k-1), some are strictly better (e.g. c2-f2b), some are weirdly slightly different in terms of phase order in each row but probably comparable (e.g. 2c2-f2b), and some are a mix of better and phased differently (e.g. 2c4-f2b). I guess the tutorial-level summary is probably something like "probably prefer named geometries above where available"? Maybe we would just put this all in its own section at the bottom with the other complex topics?

[LuveelVoom]

How do I do maxpop searches?

[amling]

How do I do maxpop searches?

The most recent cut of this explanation is here.

EDIT: It occurs to me that that explanation didn't really address --wao-tile-error-mask. The default is safe in the sense that it shouldn't miss anything but in certain geometries it's going to find the same ships in multiple alignments and depending on circumstances this duplication can be avoided. If you aren't able to complete what you want maybe check back in here with more details (rules, speeds, populations), etc. and we can see if there is anything we can do.

[LuveelVoom]

I've noticed that many LLSSS searches tend to get stuck for a really long time on the frontend and then complete the rest of the ship relatively quickly. Two questions:

1. How does one start a search from a partial? This would be useful if one already has a wide frontend and wants to do a narrower search below it.

2. I feel like purely using partials might be too constraining as it would be impossible to backtrack on the end of the frontend (unless the frontend is very clearly defined). (I would have to test this to be sure, though). Is there any possibility of a "pseudo-partial" mode where the search starts out with a frontend but is able to backtrack if needed? Does this already exist?

EDIT:

"@yolo_1gp" might even be tutorial-level, although maybe we come up with a better name first...

Might I suggest "@extend_1gen_partial" or something similar (assuming I'm understanding how it works correctly?)

[amling]

How does one start a search from a partial? This would be useful if one already has a wide frontend and wants to do a narrower search below it.

I think the most recent survey of partial extension tools and techniques is here. Since then I had had some more thoughts and sketched "@yolo_1gp" to try to deal with single generation "partials". Those mad ramblings end here. The short version is probably use '@yolo_1gp("some-file.rle")' as your "start file". It will print out near the top of the search the full multi-generation input grids it has constructed.

I feel like purely using partials might be too constraining as it would be impossible to backtrack on the end of the frontend (unless the frontend is very clearly defined). (I would have to test this to be sure, though). Is there any possibility of a "pseudo-partial" mode where the search starts out with a frontend but is able to backtrack if needed? Does this already exist?

I have nothing so automatic and I think generally feel pretty good about getting by with manually "backtracking" with --top-pad at my own discretion. Fixed board and recentering both generally take --top-pad to extend the search space one W row up. This has always worked with fixed board picture inputs (with question marks) and as of somewhat recently will also work with typical recentering inputs (with no question marks). Should work with either any form of @yolo_1gp.

Please, please, if you do use @yolo_1gp, let me know how it goes. You'll be the first real user and its behaviour is very much up for discussion/improvement.