amling search program principles discussion / brain dump

[amling]

Is generating a partial only every N w-pos a viable option?

I'm not at a computer this exact moment so I can't necessarily get the details right, but pre-partials are just steps and can be restricted with DL stuff. --pre-partials sets your choice, but you of course need to replace the entire default list with whatever you pass to --pre-partials. Something like replacing "unique" with "unique.gate(^^ $e.w_pos % 5 == 0)" should do it. Season 5 to taste. Sorry if I've gotten the details wrong from memory on my cell here, but hopefully you'll be able to work it out.

[LuveelVoom]

I was messing around with having an LLM look at obscure options in LLSSS's source and stumbled into this flag for recentering-wao:

Code: Select all

--wao-tile-error-mask MAX

This seems to make searches much (2-3x) faster. What's the trick here? Where's the downside?

Update:

Code: Select all

./rlife llsss-recentering-wao --rule 'B3/S135' c6k-1 @bg 11 | tee out.txt

1050s, max pre-reify mem 11gb

Code: Select all

./rlife llsss-recentering-wao --rule 'B3/S135' --wao-tile-error-mask MAX c6k-1 @bg 11 | tee out.txt

153s, max pre-reify mem 2.2gb

What???

Aha, the last thinnest partials are not identical. Is the downside that you lose a lot of results?

[amling]

Code: Select all

--wao-tile-error-mask MAX

... Is the downside that you lose a lot of results?

Yes and no. The discussion leading up to its existence is here. It does reduce where the first error is allowed to happen in a way that is difficult to characterize completely. For some starts the same theoretical space of patterns is findable (eventually under large enough mid_steps), and for some it is not, and for this reason it is not more broadly documented/recommended. I believe if you are running with "@bg" start it is always "correct" to use it (i.e. same space of patterns in general although not necessarily the same at each fixed value of mid_steps) and in many geometries advisable (i.e. will found approximately same width partials in less memory). c6k-1 is such a geometry although, again, characterizing exactly where it's relevant (without deferring to geom-info's calculations) is complicated.

My general bottom line I would say is if you are running a WAO search and can't run it as far as you want, come provide your entire command here and I will tell you if it's appropriate. I just can't see responsibly handing the decision off.

[LuveelVoom]

and in many geometries advisable (i.e. will found approximately same width partials in less memory). c6k-1 is such a geometry although, again, characterizing exactly where it's relevant (without deferring to geom-info's calculations) is complicated.

Is it easy to refer to these calculations? If not, could a representative set of commands be run to obtain some sort of approximate statement on when it's sometimes useful?

[LuveelVoom]

Hmm, LLSSS doesn't seem to be scaling very well with thread count. Try running a search with N threads and then 2N and you'll see it doesn't get ~2x faster (at least for me on apple silicon). Is this intended?

[amling]

and in many geometries advisable (i.e. will found approximately same width partials in less memory). c6k-1 is such a geometry although, again, characterizing exactly where it's relevant (without deferring to geom-info's calculations) is complicated.

Is it easy to refer to these calculations? If not, could a representative set of commands be run to obtain some sort of approximate statement on when it's sometimes useful?

Uh, I can tell you that it's exactly whether or not the "WAO maximal tile masks" in "geom-info" is "full", i.e. both values are 2^adet - 1. Consider e.g. 3c12-f2b:

Code: Select all

$ rlife grid-tool geom-info 3c12-f2b
Geometry: 3c12-f2b
   U: Vec3(1, 0, 0)
   V: Vec3(0, -3, 12)
   W: Vec3(0, 0, 1)
   Neighborhood sizes:
      U: 3
      W: 9
   Unique positions (3):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, -1, 4) => Vec3Uvw(0, 1, 0)
      #2: Vec3(0, -2, 8) => Vec3Uvw(0, 2, 0)
   WAO maximal tile masks: WaoTileMasks(7 = 0b111, 7 = 0b111)
$

adet = 3 (3 tile positions), both masks in MAX mask are 2^3 - 1 = 7, i.e. full, so it has no effect (reduction). Contrast that with e.g. c3d-down:

Code: Select all

$ rlife grid-tool geom-info c3d-down
Geometry: c3d-down
   U: Vec3(1, 0, 0)
   V: Vec3(-1, -1, 3)
   W: Vec3(0, 1, 0)
   Neighborhood sizes:
      U: 3
      W: 3
   Unique positions (3):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, 0, 1) => Vec3Uvw(1, 1, 1)
      #2: Vec3(0, 0, 2) => Vec3Uvw(2, 2, 2)
   WAO maximal tile masks: WaoTileMasks(4 = 0b100, 4 = 0b100)
$

adet = 3 again, but the masks are not full so it would have an effect.

I could not resist thinking through the first steps of the math and the question, flipped so we're asking "is MAX useless?", is I believe exactly "are all tile spots U=0 and W=0?" (i.e. a single line "in the V direction"). I suspect the only way typical geometries will fulfill this ("MAX is useless") is if they are KcN-f2b/KcN-b2f (including pN which is this with K=0) or are adet=det(UVW)=1 some other way, e.g. something very weird like c1d-down or c1-s2s.

[amling]

Hmm, LLSSS doesn't seem to be scaling very well with thread count. Try running a search with N threads and then 2N and you'll see it doesn't get ~2x faster (at least for me on apple silicon). Is this intended?

I don't generally "run a search with XXX threads" as I'm almost always interested in running my searches as fast as possible (entire box). "Intended"? Hard to say. Features run the gamut on how well they're able to take advantage of multiple cores and there are definitely going to be unavoidable limits and without any idea of what's happening in your case I cannot say if you're getting hit by such or getting hit by stupid/lazy/unoptimized-for-multithreading code. Generally my dev work is on my 16 core laptop, but any real benchmarking and searching is on boxes with 40+ cores.

I guess reproducing this is set RAYON_NUM_THREADS or some such? Could you please at least provide an exact search example to reduce any wild goose chasery on my side? Better would be timing data from the logs for two otherwise-identical searches (this is the stuff after "Finish: search proper" at the bottom), ideally the biggest such search(es) you're willing to wait out. Even betterer than that would be to figure out which measured frames matter (are big) and are not getting mostly halved, but that is a lot of log/number crunching, there might be several answers, etc.

[NNlk05]

Uh, I assume that's tongue in cheek and it is not efficient? Do you know what the mechanism of compression is? There was a question earlier about how zram/zswap do earlier and if you have any data about it, I think the thread is interested.

It's certainly not efficient (although there's not anything you can do that would help that (other than lowering the memory usage of LLSSS), since it's a component of my system), LLSSS massively slowed down as soon as it started cutting into compressed memory. I will look into how it compresses it and update this post. (M4 Macbook Pro, if that helps, running Sequoia 15.1).

Edit: Apparently, it finds RAM which hasn't been used recently and compresses it with this algorithm, which is apparently very fast.

Here are my results on a Linux box with 8GiB of RAM:

Code: Select all

$ zramctl
NAME       ALGORITHM DISKSIZE  DATA  COMPR  TOTAL STREAMS MOUNTPOINT
/dev/zram5 zstd         31.1G  6.2M  95.9K   184K       4 /zram
/dev/zram4 zstd          7.8G  1.2G 257.6M 265.8M       4 [SWAP]
/dev/zram3 zstd          7.8G  4.5G 923.7M 949.8M       4 [SWAP]
/dev/zram2 zstd          7.8G  5.6G   1.1G   1.1G       4 [SWAP]
/dev/zram1 zstd          7.8G  3.8G 788.7M   811M       4 [SWAP]

This search reached VmPeak 20.27 GB (I did not snapshot at this point, however), I'm surprised how did I pull this off.