amling search program principles discussion / brain dump

[May13]

EDIT: Ripped out mmap and pushed `20220523-demo3` branch. Still gonna require modest rust knowledge or a great ability to mimic surrounding code to actually configure to run, even if this branch works out.

"cargo build --release" completed, but program crashes after command from example:

Code: Select all

$ ./target/release/rlife 1.in 0 3 1
20220525 09:29:32 [INFO] Compiling [checks3 1/2] table of 17 + 4 = 21 bits
20220525 09:29:32 [INFO] Compiling [checks3 2/2] table of 17 + 4 = 21 bits
20220525 09:29:32 [INFO] Compile tables took 93.008439ms
20220525 09:29:32 [INFO] Compiling [checks3 1/2] table of 20 + 4 = 24 bits
20220525 09:29:32 [INFO] Compiling [checks3 2/2] table of 20 + 4 = 24 bits
20220525 09:29:33 [INFO] Compile tables took 859.916713ms
20220525 09:29:33 [INFO] Compile check_engine took 953.949ms
20220525 09:29:33 [INFO] Compile left edge took 15.19µs
20220525 09:29:33 [INFO] Compile right edge took 6.158µs
20220525 09:29:33 [INFO] Compile monitor took 0ns
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Os { code: 3, kind: NotFound, message: "No such file or directory" }', src\llsss\env.rs:130:58
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Edit: I commented this block from src\llsss\env.rs:

Code: Select all

//let f = std::fs::File::open("/proc/self/status").unwrap();
//for line in std::io::BufReader::new(f).lines() {
    //let line = line.unwrap();
    //if line.starts_with("VmPeak:") {
        //gol_log(LogLevel::INFO, line);
    //}
//}

And I finally can use llsss!

Code: Select all

20220525 09:47:20 [INFO] End ("LlsssEndsZero"):
20220525 09:47:20 [INFO]  ...........*.** |  .......*..**.*. | .......****.*.*  | .......*..*.*..
20220525 09:47:20 [INFO]  ......***.....* |  ......**.....*. | ......*.**.*.**  | ......*......*.
20220525 09:47:20 [INFO]  ......*........ |  .....**..*....* | ......*..***...  | .....**.......*
20220525 09:47:20 [INFO]  ......*.**..... |  ......*..**.... | ......******...  | ......**...*...
20220525 09:47:20 [INFO]  .......***.*... |  .......*....... | .........*.....  | .......*.*.....
20220525 09:47:20 [INFO]  .........*..... |  .........**.... | ...............  | ..........*....
20220525 09:47:20 [INFO]  ......*.*...... |  ......*........ | .......*..**...  | .......*.......
20220525 09:47:20 [INFO]  ....******....* |  ....***..*....* | .....***......*  | ....****......*
20220525 09:47:20 [INFO]  ...*.....*....* |  ...*.....*...** | ...**...****..*  | ...**....**..**
20220525 09:47:20 [INFO]  ...*..***.....* |  ..**.**.*.*...* | ...*..**.*....*  | ..**..**......*
20220525 09:47:20 [INFO]  ...**.*.*.**... |  ...**.*.*...... | ...*...*.*.....  | ...*.*.*.**....
20220525 09:47:20 [INFO]  ......*.*...... |  ....*.*.*...... | ....**.*.*.....  | ....**.*.*.....
20220525 09:47:20 [INFO]  .....**.*...... |  .....**.**..... | ......**.**....  | .....*.*.**....
20220525 09:47:20 [INFO]  .......**..*... |  ........*...... | .......*.......  | ......**.**....
20220525 09:47:20 [INFO]  .......*...*... |  .......*.***... | ........*..*...  | ........*......
20220525 09:47:20 [INFO]  ........*.*.... |  .......***..... | .......**......  | .......***.....
20220525 09:47:20 [INFO]  ........*...... |  .......*.*..... | .......*..*....  | .......*.*.....
20220525 09:47:20 [INFO]  ......*........ |  ......*.*...... | .........*.....  | .........**....
20220525 09:47:20 [INFO]  ....*****...*.. |  ....****....... | .....*****.....  | ....*******....
20220525 09:47:20 [INFO]  ...*.......*... |  ...*.....*..... | ...**.....*....  | ...**....**....
20220525 09:47:20 [INFO]  ...*..****..... |  ..**.**.**..... | ...*..**...*...  | ..**..**.......
20220525 09:47:20 [INFO]  ...**.*.*...... |  ...**.*.**..... | ...*...*.......  | ...*.*.*.......
20220525 09:47:20 [INFO]  ......*........ |  ....*.*.*...... | ....**.*.*.....  | ....**.........
20220525 09:47:20 [INFO]  .....**.***.... |  .....**...*.... | ......***......  | .....*...**....
20220525 09:47:20 [INFO]  .......****.... |  ............... | .......*..**...  | ......***......
20220525 09:47:20 [INFO]  .......*.*..... |  .......*.**.... | ...............  | ...............
20220525 09:47:20 [INFO]  ............... |  ............... | ...............  | .......*.......
20220525 09:47:20 [INFO]  ............... |  ............... | ......***......  | .....*...*.....
20220525 09:47:20 [INFO]  .....**........ |  ....*****...... | .....*****.....  | ....*..........
20220525 09:47:20 [INFO]  ....**.***..... |  ....*....*..... | ....**.***.....  | ....*....*.....
20220525 09:47:20 [INFO]  .....*****..... |  ....*.......... | .....**........  | ....*****......
20220525 09:47:20 [INFO]  ......***...... |  .....*...*..... | ...............  | ...............
20220525 09:47:20 [INFO]  ............... |  .......*....... | ...............  | ...............
20220525 09:47:20 [INFO]  ............... |  ............... | ...............  | ...............
20220525 09:47:20 [INFO]  ............... |  ............... | ...............  | ...............

[amling]

Edit: I commented this block from src\llsss\env.rs:

Code: Select all

//let f = std::fs::File::open("/proc/self/status").unwrap();
//for line in std::io::BufReader::new(f).lines() {
    //let line = line.unwrap();
    //if line.starts_with("VmPeak:") {
        //gol_log(LogLevel::INFO, line);
    //}
//}

Yeah, I definitely face-palmed when I looked up where the error was. Another linux-ism, this one showing OS estimate of how much memory program is using. Entirely informational.

[May13]

I tried command "./target/release/rlife 2.in 0 4 0". llsss works correctly. Here's one of partials:

Code: Select all

............*.* |  ........*..**.* | ........****.*.  | ........*..*.*.
.......***..... |  .......**.....* | .......*.**.*.*  | .......*......*
.......*....... |  ......**..*.... | .......*..***..  | ......**.......
.......*.**.... |  .......*..**... | .......******..  | .......**...*..
........***.*.. |  ........*...... | ..........*....  | ........*.*....
..........*.... |  ..........**... | ...............  | ...........*...
.......*.*..... |  .......*....... | ........*..**..  | ........*......
.....******.... |  .....***..*.... | ......***......  | .....****......
....*.....*.... |  ....*.....*...* | ....**...****..  | ....**....**..*
....*..***..... |  ...**.**.*.*... | ....*..**.*....  | ...**..**......
....**.*.*.**.. |  ....**.*.*..... | ....*...*.*....  | ....*.*.*.**...
.......*.*..... |  .....*.*.*..... | .....**.*.*....  | .....**.*.*....
......**.*..... |  ......**.**.... | .......**.**...  | ......*.*.**...
........**..... |  .........*..... | ........*......  | .......**.**...
........*...... |  ........*.*.... | ..........*....  | .........**....
..........**... |  ............... | .........*.*...  | ........*..*...
............... |  ........***.... | ........***....  | ...............
.......***..... |  .......**...... | ........**.....  | .......*.......
.......*....... |  ......*........ | .......*.*.....  | ......**.*.....
.......***..... |  ......*..*..... | ....**.*.......  | ...*...**......
...**..**...... |  ..****...*..... | ...****........  | ..*............
..**.***....... |  ..*............ | ..**.*.........  | ..*..**........
...**.**....... |  ..*............ | ...*...........  | ..**.*.........
....*****...... |  ...**....*..... | ....**....**...  | ....*..........
.......*.**.... |  ....*....**.... | .......**......  | ......***.**...
....*.*...*.... |  ...********.... | .......*...*...  | .......**......
...**..*....... |  ..*.*..**...... | ...*...........  | ..***.**.......
..**..**.*..... |  ..*..*.*....... | ..**.*.***.....  | ..*.....*......
...*.*.*....... |  ..**........... | ...**..........  | ..*...*.*......
....*****...... |  ........*...... | ....**.........  | ...****........
.....*.*....... |  ....**......... | ......**.*.....  | ...............
........*...... |  ......***...... | ......***......  | ......*..*.....
.......*....... |  ............... | ........*......  | ......*.*......
............... |  ............... | ......*........  | .....**........
.....*..*...... |  ....***........ | .....***.......  | .....***.......
....**.*....... |  .....*......... | ...............  | ....*..........
...*.*......... |  ...*.**........ | ...**.**.......  | ...**..........
...*........... |  ..**.*......... | ...*...........  | ..**...........
...**.*........ |  ...***.*....... | ...*...........  | ...*...........
....*..**...... |  ....*.*........ | ....**.**......  | ....***........
....*..****.... |  ......*...*.... | .....*.........  | ...*.**.**.....
...***..*..*... |  ...*.****...*.. | ...**....**.*..  | ...*.....***...
...*.*....***.. |  ..**.**.*...*.. | ...**.*..**....  | ..*.....*......
..*..*..***.... |  ..*.....*...... | ...*.*..*.*.*..  | ..**.**.....*..
..*.*****..**.. |  ...*......*.*.. | ..*..*....***..  | ..**....**..*..

RLE:

Code: Select all

x = 19, y = 52, rule = B3/S23
10bob2o3b2o$8b3ob3o$6b2o$6bo2b3obo$6bo2bobo3b3o$7b2o3bobo2bo$9b2obob2o
bo$10bob4o2bo$5b3o5bo2bobo$5bo8bo3bo$5bob2o5bobobo$6b3obo7bo$8bo$5bobo
6bo2bo$3b6o4bo$2bo5bo4bo3bo$2bo2b3o5b4o$2b2obobob2o$5bobo$4b2obo$6b2o$
6bo$8b2o2$5b3o$5bo$5b3o$b2o2b2o$2ob3o$b2ob2o$2b5o$5bob2o$2bobo3bo$b2o
2bo$2o2b2obo$bobobo$2b5o$3bobo$6bo$5bo2$3bo2bo$2b2obo$bobo$bo$b2obo$2b
o2b2o$2bo2b4o$b3o2bo2bo$bobo4b3o$o2bo2b3o$ob5o2b2o!

Due to running out of memory, I tried to extend this partial.
2.in:

Code: Select all

  ....*****...... |  ...**....*..... | ....**....**...  | ....*..........  
  .......*.**.... |  ....*....**.... | .......**......  | ......***.**...  
  ....*.*...*.... |  ...********.... | .......*...*...  | .......**......  
  ...**..*....... |  ..*.*..**...... | ...*...........  | ..***.**.......  
  ..**..**.*..... |  ..*..*.*....... | ..**.*.***.....  | ..*.....*......  
  ...*.*.*....... |  ..**........... | ...**..........  | ..*...*.*......  
  ....*****...... |  ........*...... | ....**.........  | ...****........  
  .....*.*....... |  ....**......... | ......**.*.....  | ...............  
  .....????...... |  .....????...... | .....????......  | .....????......  
  .....????...... |  .....????...... | .....????......  | .....????......  
  .....????...... |  .....????...... | .....????......  | .....????......  
  .....????...... |  .....????...... | .....????......  | .....????......  
  .....????...... |  .....????...... | .....????......  | .....????......  

After running "./target/release/rlife 2.in 0 3 2", llsss found a solution:

Code: Select all

20220525 10:11:06 [INFO] End ("LlsssEndsZero"):
20220525 10:11:06 [INFO]  ....*****.... |  ........*.... | ....**.......  | ...****......
20220525 10:11:06 [INFO]  .....*.*..... |  ....**....... | ......**.*...  | .............
20220525 10:11:06 [INFO]  ........*.... |  ......***.... | ......***....  | ......*..*...
20220525 10:11:06 [INFO]  .......*..... |  ............. | ........*....  | ......*.*....
20220525 10:11:06 [INFO]  ............. |  ............. | ......*......  | .....**......
20220525 10:11:06 [INFO]  .....*..*.... |  ....***...... | .....***.....  | .....***.....
20220525 10:11:06 [INFO]  ....**.*..... |  .....*....... | .............  | ....*........
20220525 10:11:06 [INFO]  ...*.*....... |  ...*.**...... | ...**.**.....  | ...**........
20220525 10:11:06 [INFO]  ...*......... |  ..**.*....... | ...*.........  | ..**.........
20220525 10:11:06 [INFO]  ...**.*...... |  ...**.*...... | ...*.........  | ...*.*.......
20220525 10:11:06 [INFO]  .....**...... |  ....*........ | ....***......  | ....**.......
20220525 10:11:06 [INFO]  ......**..... |  .......*..... | .............  | ......**.....
20220525 10:11:06 [INFO]  ......*..*... |  .....*....... | ......*.*....  | .............
20220525 10:11:06 [INFO]  ......***.... |  .....**.*.... | .....*.......  | .....****....
20220525 10:11:06 [INFO]  ......*...... |  .....**.*.... | ....*..*.*...  | ...*..*......
20220525 10:11:06 [INFO]  ...**...*.... |  ..***...**... | ...***.......  | ..*....**....
20220525 10:11:06 [INFO]  ..**...***... |  ..*..*.***... | ..**.***.....  | ..*..........
20220525 10:11:06 [INFO]  ...**.*...... |  ..*...*.*.... | ...*.*....*..  | ..**.*.*.....
20220525 10:11:06 [INFO]  ....***...... |  ...**.**..... | ....*..*.....  | ....**.*.....
20220525 10:11:06 [INFO]  ......*...... |  ......*...... | ......**.....  | ......***....
20220525 10:11:06 [INFO]  .......**.*.. |  .......***... | ........*.*..  | .......*.*...
20220525 10:11:06 [INFO]  .........*... |  ........**... | ..........*..  | .........*...
20220525 10:11:06 [INFO]  ....**....... |  ...*..*...... | .............  | .............
20220525 10:11:06 [INFO]  ...****...... |  ..*.......... | ...**........  | ..****.......
20220525 10:11:06 [INFO]  ..**.**...... |  ..*...*...... | ..**.**......  | ..*...*......
20220525 10:11:06 [INFO]  ...**........ |  ..****....... | ...****......  | ..*..........
20220525 10:11:06 [INFO]  ............. |  ............. | ....**.......  | ...*..*......
20220525 10:11:06 [INFO]  ............. |  ............. | .............  | .............
20220525 10:11:06 [INFO]  ............. |  ............. | .............  | .............

RLE:

Code: Select all

x = 19, y = 62, rule = B3/S23
10bob2o3b2o$8b3ob3o$6b2o$6bo2b3obo$6bo2bobo3b3o$7b2o3bobo2bo$9b2obob2o
bo$10bob4o2bo$5b3o5bo2bobo$5bo8bo3bo$5bob2o5bobobo$6b3obo7bo$8bo$5bobo
6bo2bo$3b6o4bo$2bo5bo4bo3bo$2bo2b3o5b4o$2b2obobob2o$5bobo$4b2obo$6b2o$
6bo$8b2o2$5b3o$5bo$5b3o$b2o2b2o$2ob3o$b2ob2o$2b5o$5bob2o$2bobo3bo$b2o
2bo$2o2b2obo$bobobo$2b5o$3bobo$6bo$5bo2$3bo2bo$2b2obo$bobo$bo$b2obo$3b
2o$4b2o$4bo2bo$4b3o$4bo$b2o3bo$2o3b3o$b2obo$2b3o$4bo$5b2obo$7bo$2b2o$b
4o$2ob2o$b2o!

This solution is less optimal than in example, but it gives some knowledge about using this program.
amling, thanks for solving problems with running on Cygwin!
Edit: another solution (0 4 1, after adding extra column to left side in all phases):

Code: Select all

x = 20, y = 70, rule = B3/S23
11bob2o3b2o$9b3ob3o$7b2o$7bo2b3obo$7bo2bobo3b3o$8b2o3bobo2bo$10b2obob
2obo$11bob4o2bo$6b3o5bo2bobo$6bo8bo3bo$6bob2o5bobobo$7b3obo7bo$9bo$6bo
bo6bo2bo$4b6o4bo$3bo5bo4bo3bo$3bo2b3o5b4o$3b2obobob2o$6bobo$5b2obo$7b
2o$7bo$9b2o2$6b3o$6bo$6b3o$2b2o2b2o$b2ob3o$2b2ob2o$3b5o$6bob2o$3bobo3b
o$2b2o2bo$b2o2b2obo$2bobobo$3b5o$4bobo$7bo$6bo2$4bo2bo$3b2obo$2bobo$2b
o$2b2obo$4b2o$5b2o$5bo$5b2o$3bo$2bo3b2o$b2obo$2o3b3o$b2o2bobo$4bo$4bo
2$2b2o$bo4bo$bo2b3o$b6o$4b3o$4b2o2$4bobo$2bo4bo$bo$bo5bo$b6o!

Edit 2: how to search for c/4 instead of 2c/4? I tried to modify vv:

Code: Select all

fn main_llsss() {
    let mut args = env_args();

    let picture_lines = args.read_file_lines();
    let top_pad = args.parse();
    let left_pad = args.parse();
    let right_pad = args.parse();

    let vu = (1, 0, 0);
    let vv = (0, -1, 4);
    let vw = (0, 0, 1);

4.in

Code: Select all

 ............................ | ............................ | ............................ | ............................ 
 ................*........... | ............................ | ............................ | ............................ 
 ............................ | ............................ | ............................ | ..............***........... 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 

program can't recognise this file:

Code: Select all

$ ./target/release/rlife 4.in 0 0 0
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `1`,
 right: `4`', src\llsss\env.rs:211:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

[amling]

Edit 2: how to search for c/4 instead of 2c/4? I tried to modify vv:

Code: Select all

    let vu = (1, 0, 0);
    let vv = (0, -1, 4);
    let vw = (0, 0, 1);

You want to search for c/4 front-to-back? `vv = (0, -1, 4)` plus `vw = (0, 0, 1)` seems to suggest as much. Due to language issues I was unable to avoid the duplication of the UVW determinant absolute value. It computes that determinant itself at runtime but I need to know it at compile time and rust compile-time math sucks so it's duplicated in `TILE_BITS` which it looks like you should set to 1. Some day rust's const feature will be more than like 2% implemented and I'll be able to move the determinant computation to compile time properly.

EDIT: I'm a little confused by your suggested input file whose alignment of the spark seems to suggest you want to search c/4 left side-to-side. For that I'd expect `vu = (1, 0, 0)`, `vv = (-1, 0, 4)`, `vw = (0, 1, 0)`, `TILE_BITS = 4` for which that input file does work (although I'm not super optimistic about results given how aggressive that framing of the side spark is).

[amling]

Some questions I had answered elsewhere, but should copy here for public record:

How to set up 2c/4 or c/2 f2b search? (UVW + geometry of input file)

2c/4 f2b I'd use vu=(1, 0, 0), vv = (0, -2, 4), vw = (0, 0, 1), TILE_BITS = 2. Input file geometry similar to 2c/4 s2s (third and fourth generations shifted, in this case "up" one), so shaped like:

Code: Select all

      |      | XXXX | XXXX 
 XXXX | XXXX | XXXX | XXXX 
 XXXX | XXXX |      |      

c/2 f2b I'd use vu=(1, 0, 0), vv = (0, -1, 2), vw = (0, 0, 1), TILE_BITS = 1. Input file I believe will have two generations aligned, so shaped like:

Code: Select all

 XXXX | XXXX 
 XXXX | XXXX 

How to do symmetric searches? (odd, even, gutter, glide-reflect)

`left_edge` and `right_edge` can be configured to something else, e.g. `LlssssEdgeEven` or the like. They have to be configured with rust type system nonsense regarding their compiled table structures though which is sort of messy. Also input picture gets a little more confusing since presumably you won't read whatever left/right edge part of it you're configuring that way. You could also maybe configure just the `next` edge to be `LlsssEdgeEven` and thus the picture would be read normally? This is all a bit new and I have not exactly hammered out best practices for these as they were invented long before this "input picture" business was a thing.

EDIT: That `next` suggestion doesn't quite make sense. It would work, but it is a different behavior. The question is for input like:

Code: Select all

AAAAAAA
AAAAAAA
BB???..
BB???..
BB???..

What happens with Bs? Either way As are loaded as initial state. With `left_edge` itself set to even Bs are ignored and that space isfilled with whatever matching (even) columns. With `left_edge`'s `next` set to even the Bs are kept and fixed as they are, but if the search runs off the bottom of the picture then below them is filled with even columns.

Both are behaviors you could conceivably want, but if you're just trying to extend an existing slice (like the As) you probably want the former (you have no obvious choice of B to fill in in fact, and when I was running these searches I would leave exclamation points to make sure it wasn't using that part of the picture).

Is it possible to change rule? Looks like it's possible to search in B2/S. I'm interested in rules B3/S35 and B36/S36.

Much of that seeds work predates LLSSS, but LGOL and LLSSS share the same rule implementation in `check_compat2` in `src/lgol/graph.rs`. You can see any of the branches with "seeds" in the name (some of which did get pushed to github) to see the version I had written for that.

[amling]

I've rebuilt the demo branch:

(1) `d872d35ab1da` to [automatically] disable the rctl socket code on windows (instead it does ... nothing).
(2) `24cb05a8fdc4` to skip reading `/proc` for memory information on windows
(3) `47e97be0054b` to rearrange the mmap code to be together and thus easy to pull.
(4) `61b5e38e44ad` to actually disable it.

(1)-(3) were overall not too bad for the main codebase and are included in the master branch on github.

(4) is included in a rebased-up `20220525-demo4` branch and should be easy enough for whoever is using windows to kick along and not get constantly conflict bombed.

[May13]

I can search for B3/S35. Here's code from graph.rs:

Code: Select all

/*pub fn check_compat2(living: u32, known: u32, c: bool, f: bool) -> bool {
    let dead = known - living;
    match c {
        true => match f {
            // need 2 or 3
            true => (living <= 3 && dead <= 6),
            // need 0, 1, or 4+
            false => (living <= 1 || dead <= 4),
        },
        false => match f {
            // need 3
            true => (living <= 3 && dead <= 5),
            false => (living <= 2 || dead <= 4),
        },
    }
}*/
pub fn check_compat2(living: u32, known: u32, c: bool, f: bool) -> bool {
    let dead = known - living;
    match c {
        true => match f {
            // need 3 or 5
            true => ((living <= 3 && dead <= 5) || (living <= 5 && dead <= 3)),
            // need 0, 1, 2, 4, or 6+
            false => (living <= 2 || dead <= 2 || (living <= 4 && dead <= 4)),
        },
        false => match f {
            // need 3
            true => (living <= 3 && dead <= 5),
            false => (living <= 2 || dead <= 4),
        },
    }
}

Using this modification, I found a 2c/4 wickstretcher.
Partial from llsss:

Code: Select all

x = 12, y = 38, rule = B3/S35
3bo$b2obob2obobo$2o3bo2bobo$b4o$4bobo$5bobo$5bo$4b4o$b4obo$2o$b2o2b2ob
o$3b2o2bo$4b2obo$6b2o$6b3o$6b2o$5bo2bo$3b2ob2o$2b2o$3b5o$5bo3bo$5b2o$b
2o4b3o$2o2b4o$b2ob2obo$3bo2b2o$9bo$6bo$b3o2b2o$2o3bo$b2o4bobo$3bo3bobo
$4bobo$4b3o$2bob2o$bo2b2o$2o4b2o$bo5bo!

Completed using other program (JavaLifeSearch):

Code: Select all

x = 32, y = 18, rule = B3/S35
22bo6bo$21b3o4b3o$13bo7bobo4bobo$12b3o5bo2bo4bo2bo$12bobo4b2o2b2o2b2ob
o$3bo7bo3bo3bobo2b3o2bo$2b3o7bobob3o2bob2o2bo2bo$2bobo6b2obob5o3bobo3b
o$2bo2bo2b3o4bobo3bo7bo$3bo3b2obo19bo$7bo2bo17b2o$6b2o22bo$5bo$4b2o$bo
3bo$3o$obo$obo!

Edit: what's wrong with this implementation of B36/S36?

Code: Select all

pub fn check_compat2(living: u32, known: u32, c: bool, f: bool) -> bool {
    let dead = known - living;
    match c {
        true => match f {
            // need 3 or 6
            true => ((living <= 3 && dead <= 5) || (living <= 6 && dead <= 2)),
            // need 0, 1, 2, 4, 5, 7, 8
            false => (living <= 2 || dead <= 1 || (living <= 4 && dead <= 3)),
        },
        false => match f {
            // need 3 or 6
            true => ((living <= 3 && dead <= 5) || (living <= 6 && dead <= 2)),
            // need 0, 1, 2, 4, 5, 7, 8
            false => (living <= 2 || dead <= 1 || (living <= 4 && dead <= 3)),
        },
    }
}

I can't find any reasonable c/2 partials, even though an actual c/2 spaceship exists:

Code: Select all

x = 25, y = 143, rule = B36/S36
10b2o$9bobob3o$9b2o2bobo$8bo3bobo2bo$8b2o2bobo$9bo4b2o$11bo2bo4b4o$9b
3o3b2o$8b2o5bob2o2bo$8bobo5b2o$9bo9b2o$7b2obo10b2o$7b2o6b2o3b2obo$12bo
8b3o$4b2o2b2o2b2obo2bo$3bobob3obo2bob3o2bo$3b2o2bo5bo3b2o$2bo3bo2bob3o
4bo2bob2o$2b2o2bo8b2ob2o3bo$3bo8b2obo5b3o$5bo6b2o2bo2b3o$3b3ob2o5bo6bo
$4bo8bobo4b3o$2b3o3b2o5bo3bo3bo$2b2o2b3obob2o6b2o$6b2o7b4o2bo$3bob4ob
2o10bo$2bo3bo3bo4bo2bo$2b3o3bo2bobo2bo$2bobo10bobo$2b2o4b3obo2bo$3b2o
10bo2bo$6bobob2o3b2o2bo$3bob2o9bo2bo$2b2o2bo2bo2bo2bobo$3bobo2b2o5b2o$
6bobob2o3bo3bo$3b2o11bobo$4bo2bo2bobo5b2o$2b3o2b2o6b2o4b3o$2b2o2bo2bob
o2bo5b4o$8bobo2b2o6b3o$3bobobo4bo4bo4bobo$7bo5b2obo$3b2o3b2o2bo3bo$3b
2obo5b5obo$5bo2bobobob3o4bo$4bobo2bo8b2o$4b2o4bo3bo5bobo$5b2o5bobo4bo$
8b3o2b2obo2b2o$5bob3o2bo7b2o2bo$4b2o2b2o2bobo2bob3o$4bo2b2o3bo10b2o$5b
2o4bobob3obo$5bobo2b3o$6bobo4b2o2b3o$8bobo7bo$3b2ob2ob2obo2b2o$2b2o3bo
bo$b5o3bobo$3obob2obo$b2o6b2o$4b3o2b2obo$2b4o6bo$3bob2o3bo2b2o$b3o3b2o
b2o$b2o3bo2bo2bo$9bo2b4o$2bob3o3bo$bo8b3o$b3o7bo$bo8b3o$2bob3o3bo$9bo
2b4o$b2o3bo2bo2bo$b3o3b2ob2o$3bob2o3bo2b2o$2b4o6bo$4b3o2b2obo$b2o6b2o$
3obob2obo$b5o3bobo$2b2o3bobo$3b2ob2ob2obo2b2o$8bobo7bo$6bobo4b2o2b3o$
5bobo2b3o$5b2o4bobob3obo$4bo2b2o3bo10b2o$4b2o2b2o2bobo2bob3o$5bob3o2bo
7b2o2bo$8b3o2b2obo2b2o$5b2o5bobo4bo$4b2o4bo3bo5bobo$4bobo2bo8b2o$5bo2b
obobob3o4bo$3b2obo5b5obo$3b2o3b2o2bo3bo$7bo5b2obo$3bobobo4bo4bo4bobo$
8bobo2b2o6b3o$2b2o2bo2bobo2bo5b4o$2b3o2b2o6b2o4b3o$4bo2bo2bobo5b2o$3b
2o11bobo$6bobob2o3bo3bo$3bobo2b2o5b2o$2b2o2bo2bo2bo2bobo$3bob2o9bo2bo$
6bobob2o3b2o2bo$3b2o10bo2bo$2b2o4b3obo2bo$2bobo10bobo$2b3o3bo2bobo2bo$
2bo3bo3bo4bo2bo$3bob4ob2o10bo$6b2o7b4o2bo$2b2o2b3obob2o6b2o$2b3o3b2o5b
o3bo3bo$4bo8bobo4b3o$3b3ob2o5bo6bo$5bo6b2o2bo2b3o$3bo8b2obo5b3o$2b2o2b
o8b2ob2o3bo$2bo3bo2bob3o4bo2bob2o$3b2o2bo5bo3b2o$3bobob3obo2bob3o2bo$
4b2o2b2o2b2obo2bo$12bo8b3o$7b2o6b2o3b2obo$7b2obo10b2o$9bo9b2o$8bobo5b
2o$8b2o5bob2o2bo$9b3o3b2o$11bo2bo4b4o$9bo4b2o$8b2o2bobo$8bo3bobo2bo$9b
2o2bobo$9bobob3o$10b2o!

[amling]

Edit: what's wrong with this implementation of B36/S36?

Code: Select all

pub fn check_compat2(living: u32, known: u32, c: bool, f: bool) -> bool {
    let dead = known - living;
    match c {
        true => match f {
            // need 3 or 6
            true => ((living <= 3 && dead <= 5) || (living <= 6 && dead <= 2)),
            // need 0, 1, 2, 4, 5, 7, 8
            false => (living <= 2 || dead <= 1 || (living <= 4 && dead <= 3)),
        },
        false => match f {
            // need 3 or 6
            true => ((living <= 3 && dead <= 5) || (living <= 6 && dead <= 2)),
            // need 0, 1, 2, 4, 5, 7, 8
            false => (living <= 2 || dead <= 1 || (living <= 4 && dead <= 3)),
        },
    }
}

Mmm, suspect "(living <= 4 && dead <= 3)" wrong. E.g. it can never be true once the entire neighborhood is known (live + dead = 8 then). If I'm following correctly that's supposed to correspond to 4 and 5 which I think should be "(living <= 5 && dead <= 4)". Sorry that this way of specifying rules is a bug factory at best. I don't do much in the way of searching other rules so I'm almost never in there.

Maybe it would be clearer with "min_living = living; max_living = living + 8 - known" and then working in terms of the min/max range of how many cells could end up living? Clearest of course would be put the rule string somewhere and make the computer do the hard work but something something performance, this is called in performance-sensitive places.

[May13]

Edit: what's wrong with this implementation of B36/S36?

Code: Select all

snip

Mmm, suspect "(living <= 4 && dead <= 3)" wrong. E.g. it can never be true once the entire neighborhood is known (live + dead = 8 then). If I'm following correctly that's supposed to correspond to 4 and 5 which I think should be "(living <= 5 && dead <= 4)". Sorry that this way of specifying rules is a bug factory at best. I don't do much in the way of searching other rules so I'm almost never in there.

Maybe it would be clearer with "min_living = living; max_living = living + 8 - known" and then working in terms of the min/max range of how many cells could end up living? Clearest of course would be put the rule string somewhere and make the computer do the hard work but something something performance, this is called in performance-sensitive places.

Yes, this works.
I did not expect the program to find this c/2 spaceship so fast! (I spent about a hour to find symmetric version using LSSS)

Code: Select all

x = 57, y = 28, rule = B36/S36
25bo$19b2o3b3o$14b2obob2obob4o$6b2o3b2ob2o4b3o3b3o14b2o$4b2ob2ob2obo3b
o4b2ob2obo8b4ob2ob2ob4o$3bobo4bobobo6b3o2bo8bobo2bo5b2obob2o$3b2o4b2o
8bobobo2bo2b2ob3o3b3o3bo3bob4o$6b2o9bobo2b2ob2ob2ob2o3bob2obo2b2o4b3o$
b2ob5o6b2o3bo3bo5bo3bobob2ob2o4bo6bo$b2o3bobo5bobo5bo5bobo10b3o4b2o3b
3o$bob2obo7b2o2bobo3bo3b3o3bobo3bo8bobo4bo$4bo3bobo6b2obobo7b3obo12bo
5bo$4bo5bobob2ob2obo10bobobo6bo2b2o2bo2bobo$4b2o4bobo6b2o14bob2o3bobob
o$2b3o5bo2bob3o16b2ob2obo5b2ob2obo$b2o2b2o2bobo3bo4bo13bo4b3o2bo5b3o$o
3bob2obobo8b2o15bob2o4bo4b3o$4b2ob2o6bobo2bo13bobo5b2o2b2o4bo$8bo8bob
2o12bo2b2o2bob3obo$6bo2bo7bo14b2o5b2o4bo$8bo21b2obobo2b3o2bo$7bobo7bob
o6b5o2b2o3bo3bo$7bo2b2o5bo4b5o4b2o6b2obo$10b2obobo2b4o2bo2b2obo3bo7bo$
9b2o4bo2bobo3bo9bo$12bobo4bobobo8bo$11b2o5bo3bo$11b2o5bob2o!

Edit:
Search is unusually fast for this width:

Code: Select all

x = 74, y = 44, rule = B36/S36
33b2o$21b4o2b4ob2ob2ob3o2b4o$20b2obobobo2bo5b2obobobo2bob4o$19b4obo3b
3o3bo3bobo3b3o2bo2b3ob4o$20b3o3bob2obobo4bo2b4o4bo4b2obob2ob4o2b4o$19b
o5b2o2b2obo5b3o3bob3o2bo4bo5bo2bobobob2o$15b8o4bo8b2obob2obobo2b2o3b2o
3bob4o3bob4o$7b4ob3o2bo10bo3bobobo2b2o2bobo2b2o2b2ob2o4bob2obo3b3o$6b
2obob2o4b5o5b2o9bo3b3ob2o2bobo3bob2o2bobo8bo$5b4obo4bo3b2o9bobo2bo2bo
3bo5bo4bo3b2o3bobo$6b3o4bo5bobobob2o2b2o2bob2o4bo3b2obo7bo2b2o5b6obo$
5bo5bo7bo2bobobob2obo2bob2o2b2o13bo3b2obo2b2obob2o$9b2o7b2obo2bobob2ob
obo8bo5b3o3b2ob2o3b2o2b2o3b2o$5bobobo14bo5bobob3o4bo4bo3b2ob2o3bo2bo3b
o5bo$3b2o6bob2o5bo7bo2bob2ob3obo4b3o5bo4bo4bob2o2bo2bo$2bobo4bo3b2ob4o
bo6bo6bo4bo3bo4b2o2bo4bob2o2bo2b2o2b2o$2b2o2bo2bobo3bo2bo3b3o11bo3bo6b
o3bob2o4b2o5b2obobo$5bo3bo2bo2b3o2bo2b2obobo4bobob3o6bo2bob3o4b3o7bob
3o$3b2o3bob3o2bo10bo2b3o3b2obo7bo5bobobobo9bo2bo$11bobobo3bob2o2b3obo
2bobo3b2o6bo4bo2bo2bo7b2ob5o$8bo3bo5b3o7b2o4b2ob2o16bo2bo4b2ob4o$6bob
3obo2b2obob2o5b2o6bo7b2o12bo4bobo5bo$4bob3o4bo5bo2b2ob5o2bobob5ob2ob2o
9b2o4b2o7b2o$2b2o3b2o8b6o2b3o2bo3b2o4bo4bobo8b3o6b2obo2bobo$bobo4bo10b
obo2bo2bo3bobo2bobo2b2o3b2o8bob3ob3o4bo2b2o$b2o2bo15b2o2bobo2b2o5bobo
6bo9b5ob3o5bo$4b2o13bobo3bo2b3obobobo7bo3bo3b2ob4obobo3bo4b2o$bo2bo14b
3o3bo3b3obobo2bo5bo2b3ob2obo2bo6b4o$bob2o14b2o2bo4b2o3b3ob2o7bo4bo13bo
2b4o$2bo2bob4o2b3ob2o10bo2b2o2bo10bobob2o16bob2o$7bo2bobobob2o2bobo5bo
3b3o14b2o15b3o$b2o2bob3o3bobo4b3obo3b2o4bob3o6bobo2bo12b3o6bo$3o6b4o2b
3ob2o2b3obobo8bobob3o2bobo12b2obo6b2o$b2obob2obo3b2o3bo4bobo2b2o2bob2o
2b4obobo15b5o2bo3bo$bo4bo3bobo3bo2b2o3b2obob2obo2bo6bo4b2o12bobo3b2ob
3o$4bo4bo2bo5bo4bo5bo2bobo4bo2bobob2o15bo5b2o$7bo11b2ob2o2b3o5bo3b2o2b
3o2bo11bobobo$9bobo8bob2o2bo2b2obo3b2o4bobo9b4obo2bo2bo$11bo11b2ob2o2b
2o2b2o4bo11b2o2bo2bo2bo3b4o$29b2o5bo6bob2ob5o3bo6bobobob2o$23b3ob3o9b
2ob3ob3o4bobo8b2o2b4o$25bo5bo2b3ob2o4bobo3bobobo5b3o2bo3bobo$26b2o2b3o
bo5bo8bo5bo3bobo3bo3bo$23b3ob3o4b2obob3o9b3o4bob4ob7o!

Edit 2: I also tried c/3 orthogonal, but asymmetric searches are too difficult:

Code: Select all

x = 138, y = 24, rule = B36/S36
25b3o56b3o$24bobob3ob4o2b3o42bobob3ob4ob2o$23bobo3bobobo2b2ob2o41bobo
3bobobo2bob2ob3o3b4o3b2o$23b2o3b3obo3b2ob5ob4ob2o30b2o3b3obo3b8o2bob2o
bo2b2o8bob2o$23bo4b4obo2bo5bobobo2bob2o29bo4b4obo2b4obo2bobob2obobo3bo
b3o4b2o$34bo3b2o2b2obo2b2ob3obo25b2o10bo3bo4b2obo5bo4bobobob2o3bo$21b
2o3b2o5b2o3b2o4bobo7bo26bo3b2o5b2o2b2ob2o3bo2bo8b2o3b2o5b2o$20b2o2b2ob
2o6b4o5bob2o2b4obobo23bob3o2bo5b2o2bobo2bo5b3o4bo11bo$15b2ob2o2bob2o3b
o2b3o2bob2o11b3ob3obo21bo4bobobob2o4b2obo2b2ob2o2bo8b2o6bo$13b3obobo
13bo3bobo3bobob3o5bo2bo21bo3bobobobo8bo6bo2bo4b3o$12bo5bo2bobo2bo2b2ob
2o2bob4o2bo3bobo4bo4b2o20bo4bobo2b4o2b3o7bo2bobo2bo6b4ob3o$11b2o12bo5b
o2bobob2o4b6o4bo3b3ob2o16bo2bo6bobo6b3obo2bo4b2o3bo15b2o$9b2obo3bo3bo
2bob3obo7bo3bo2bo7bo7b2obo16bo2b3obo4bo2bob3obo4b2ob3o2bo2b2o2bo2bo2bo
bo2b2o$10bobo2b3o3b2obob2o3b2ob3o2bo2bo4b2o5b2o3b4obo18bobo2b5obobo4b
2ob2obobo7bob2o13bo$9bo5bo5bobo7bo2b3o2bo11b2ob2o2b4ob2o16bo2b2o3bo3bo
8bo2b2o4b2o2bo5bo2b2o4bob4o$8bobob2ob4o2bo3bobobo2bo5b2o7bo8b2obob3o
18b2o3b2obo2bo2bo2bobo4bo4bobobo6b3o7b2o$12bo3bo2b3o2b2o2bo2b3obo5bo3b
2o7b2o2b2o4b2o18bobobobobo5b2ob2o2bob3obobobo2bob3o8b3o$8bo2b2o6b2obo
2b3o8bo8bo2bo10bo22b3o4b3o3bo4bobob2obo6b2ob2obo2bob4o2bobo$7b2obobo4b
o6bo5bo3bo2bobob2obobo6b2o5b2o3bo15b3o2bo2bo2bob3o2bo6b2o3bo5bo3b2o2bo
bobo2bo$6b2obobob3o2bo2bo3bo2b2obob5o4b2o2bobobob2o7bob2o16bo3bo3bob2o
3b2obobo5bob3obob2o4b2o3bob4o2bo$6bo2bobo2bo4b2o3b2ob2o5bobo3bo6bo2b2o
3b4o21bobobob3obo4b2ob2o2b4o2bo3b3o2bob4o2b4o2bob2o2bo$4b2o2b2ob3o2bo
2b2ob2o4bobo2bo4bobobo2bo2bobob2o6b3o2bo$b2obo3b2ob2o2bo4b3o3bo2b4obob
o2bo2b4o2bobobo2b2o4bo3b2o$2obo2bo2bo2bobob2o3b2o2b3o3bob5o3bo7bob4o2b
6o2b3o!

Symmetric spaceships are known, but I haven't tried symmetric search yet:

Code: Select all

x = 145, y = 91, rule = B36/S36
22bo14bo64bo14bo$21b5o8b5o62b5o8b5o$20bo3b5o2b5o3bo60bo3b5o2b5o3bo$19b
obo2b2obob2obob2o2bobo58bobo2b2obob2obob2o2bobo$18b2o3b2obo6bob2o3b2o
56b2o3b2obo6bob2o3b2o$28bo2bo76bo2bo$19b4o3b2ob2ob2o3b4o58b4o3b2ob2ob
2o3b4o$19bobo2bo10bo2bobo58bobo2bo10bo2bobo$13b5o7bobob2obobo7b5o46b5o
7bobob2obobo7b5o$13b2o2b3o2bo14bo2b3o2b2o46b2o2b3o2bo14bo2b3o2b2o$12b
3o3b3o2b2ob2o4b2ob2o2b3o3b3o44b3o3b3o2b2ob2o4b2ob2o2b3o3b3o$11b2obo4bo
bo16bobo4bob2o42b2obo4bobo16bobo4bob2o$9b2ob3o2b3o5b10o5b3o2b3ob2o38b
2ob3o2b3o5b10o5b3o2b3ob2o$7b3o5b2o26b2o5b3o34b3o5b2o26b2o5b3o$4b3o4b6o
2bo3b2o10b2o3bo2b6o4b3o28b3o4b6o2bo3b2o10b2o3bo2b6o4b3o$2b2ob2o8bobo
10b4o10bobo8b2ob2o24b2ob2o8bobo10b4o10bobo8b2ob2o$bobo2bob3o2bob2o2b2o
b2o12b2ob2o2b2obo2b3obo2bobo22bobo2bob3o2bob2o2b2ob2o12b2ob2o2b2obo2b
3obo2bobo$obobo4b2ob5o3b3o6b2o6b3o3b5ob2o4bobobo20bobobo4b2ob5o3b3o6b
2o6b3o3b5ob2o4bobobo$3bo2b2o6b3ob2ob2o14b2ob2ob3o6b2o2bo26bo2b2o6b3ob
2ob2o14b2ob2ob3o6b2o2bo$2b2o8bobobob2obo5b2o2b2o5bob2obobobo8b2o24b2o
8bobobob2obo5b2o2b2o5bob2obobobo8b2o$7b2o6bob3ob3o3bob2obo3b3ob3obo6b
2o34b2obo4bob3ob3o3bob2obo3b3ob3obo4bob2o$4b3o6bobo3bo6b2ob2ob2o6bo3bo
bo6b3o27b2o3bo4bobo3bo6b2ob2ob2o6bo3bobo4bo3b2o$3bob2ob2o2bo4b2o2bo4b
2ob2ob2o4bo2b2o4bo2b2ob2obo26bo3bo3bo4b2obo2b2o2b2ob2ob2o2b2o2bob2o4bo
3bo3bo$5bo6bobo4b3o6bo2bo6b3o4bobo6bo27bo4b2o2b2ob2ob2o9bo2bo9b2ob2ob
2o2b2o4bo$3b2o4b2o4b3o2b3o4b6o4b3o2b3o4b2o4b2o25b2o3b2o2bo7b3obo2bo6bo
2bob3o7bo2b2o3b2o$3bobo2bo3bobo4b2obo2b2o6b2o2bob2o4bobo3bo2bobo25bo
10bo6bo2bo12bo2bo6bo10bo$8b2o3b2o7bob2o2bo2bo2b2obo7b2o3b2o30b3ob2o11b
o3bob2o6b2obo3bo11b2ob3o$3b2obo3bob3o4bob3o2b3o2b3o2b3obo4b3obo3bob2o
22b3o2bo13bobobo3bo6bo3bobobo13bo2b3o$7b3o8b3o7bo2bo7b3o8b3o26b2o2bobo
17bob3o4b3obo17bobo2b2o$2b2o4bo2bo5b2obo4bo8bo4bob2o5bo2bo4b2o22bobob
3o12bo3b2o3bo2bo3b2o3bo12b3obobo$2bobo12bo3b2o2b2o6b2o2b2o3bo12bobo19b
4o3bo14b2obo6b2o6bob2o14bo3b4o$bo2b5o9b2o20b2o9b5o2bo18bo5b2obo7b7ob4o
8b4ob7o7bob2o5bo$3bo3b2o10bo6bo6bo6bo10b2o3bo20b2ob3o2bo7bo2bo5bo2bo2b
o2bo2bo2bo5bo2bo7bo2b3ob2o$6bo2bo7b2o22b2o7bo2bo23bo6b3o5b2obo2b3o4b2o
6b2o4b3o2bob2o5b3o6bo$3b3ob2o10b2o4b2obo2bob2o4b2o10b2ob3o28bo4bobo2bo
3bo4bo3b4o3bo4bo3bo2bobo4bo$2b2o5bo8bo4b2o3bo2bo3b2o4bo8bo5b2o17b2o7bo
4bo3bo8b2o3bo4bo3b2o8bo3bo4bo7b2o$2b2o3b2o14bo12bo14b2o3b2o30b2ob2obo
4b2o2bo2b2ob2ob2o2bo2b2o4bob2ob2o$5bo2b2ob4o2b2o5b4o4b4o5b2o2b4ob2o2bo
20bo9b3o2bo2bo8bo14bo8bo2bo2b3o9bo$3bobo4bobob3o10bo4bo10b3obobo4bobo
28bo3bob2o8bo5b2o2b2o5bo8b2obo3bo$5bo4bo7b2ob3o3bo4bo3b3ob2o7bo4bo21b
3o5b2o2bobo2bo5b3o16b3o5bo2bobo2b2o5b3o$5bobo2bob2obobo2bo18bo2bobob2o
bo2bobo22bo5bo3bobo2bo3b4obob4obo2bob4obob4o3bo2bobo3bo5bo$5b3obo3bobo
3bo3b4o6b4o3bo3bobo3bob3o21b3o4b2obo2bobo2b3o4bo16bo4b3o2bobo2bob2o4b
3o$3bo2bo4b4o2bo3bo16bo3bo2b4o4bo2bo18b2ob2o2bo7bo2b2obobo5bo4b2o4bo5b
obob2o2bo7bo2b2ob2o$4bo2b2o5bo2bo6b3o6b3o6bo2bo5b2o2bo19b2o4bo3b3o4bo
4bo3bobo12bobo3bo4bo4b3o3bo4b2o$3bo6bobo5b3o4bobo4bobo4b3o5bobo6bo20bo
3b3o2bobo2b2obo4bobo5b2o2b2o5bobo4bob2o2bobo2b3o3bo$2b3o3bo5b2o3bo6bo
6bo6bo3b2o5bo3b3o19b5o3bo5bo4bob2o20b2obo4bo5bo3b5o$10b2o4bo2b2o6b2o2b
2o6b2o2bo4b2o33bobo6bo2bobo2bobo2b2obo2bob2o2bobo2bobo2bo6bobo$2bo2b2o
b2obo2b2obo10bo2bo10bob2o2bob2ob2o2bo20b2o2bo2bo4b2obo3b2ob2o2b2obo4bo
b2o2b2ob2o3bob2o4bo2bo2b2o$4b3o4bo16bo2bo16bo4b3o22b2obo8bobo5b3o2bob
3o4b3obo2b3o5bobo8bob2o$8b3obobo12bob2obo12bobob3o28bobo3b4obo13b2o6b
2o13bob4o3bobo$5b2o5bobo13b4o13bobo5b2o36bo5b2ob2o3bobo4bobo3b2ob2o5bo
$8bo5b3o9b2ob2ob2o9b3o5bo26bobobo5bo3bo3bo8b3o4b3o8bo3bo3bo5bobobo$6b
2o5bo12bo6bo12bo5b2o25b4o11bob3o5bobo6bobo5b3obo11b4o$5b2obo2b2o3bob6o
bo2bo2bo2bob6obo3b2o2bob2o22b4obo8b5o8bo2b6o2bo8b5o8bob4o$6bo3b2o2bo
30bo2b2o3bo25b3o2bo7b4o7bo3bo4bo3bo7b4o7bo2b3o$6b2ob3o5bob3o2bo10bo2b
3obo5b3ob2o26bob2o18bo2bo3b2o3bo2bo18b2obo$9b2ob2o6bo18bo6b2ob2o29b2o
2b2o7bobo6b3o2bo4bo2b3o6bobo7b2o2b2o$8bobo7bo2bob3o8b3obo2bo7bobo27bob
2obo10b2o3bo2b2o10b2o2bo3b2o10bob2obo$8b3o2bo3b3o4bob2o4b2obo4b3o3bo2b
3o25bob2o3b2ob3ob2o11bo2b2o2b2o2bo11b2ob3ob2o3b2obo$10bo4bob3o2b2o2bo
6bo2b2o2b3obo4bo32bo7b2obo2bobob3obo10bob3obobo2bob2o7bo$8bob3ob3o2bo
20bo2b3ob3obo25b2o6bobo4bobo2bo4bo2b3ob2ob3o2bo4bo2bobo4bobo6b2o$6b2o
2bobobob3o22b3obobobo2b2o23bo4b3o4bobo2bo4b2o3bo10bo3b2o4bo2bobo4b3o4b
o$8bob2o4bo2bo20bo2bo4b2obo30b2o2bo4bo6bo5b3o6b3o5bo6bo4bo2b2o$10b2o4b
ob2o20b2obo4b2o27b2obo6b2obo2bobo2b2obo16bob2o2bobo2bob2o6bob2o$10b3o
2b2o26b2o2b3o27b2o3b2o4bo3bobo9b2o8b2o9bobo3bo4b2o3b2o$12bo34bo28b4o8b
3o5bo3bob2o2bob4obo2b2obo3bo5b3o8b4o$81b2o6bo2bo34bo2bo6b2o$79bo11b3ob
2o5bo2b2o2b2o2b2o2bo5b2ob3o11bo$79b2o11bo4bo7bo8bo7bo4bo11b2o$77bo14b
3ob2o5bo4bo2bo4bo5b2ob3o14bo$77b2o17bo2bo20bo2bo17b2o$76bobo12bo2bobo
2bo8b4o8bo2bobo2bo12bobo$79bo12b2o5bo8b4o8bo5b2o12bo$77b3o9b2o5b2o10bo
2bo10b2o5b2o9b3o$79b2o6b2obo2bo2bo11bo2bo11bo2bo2bob2o6b2o$80bo5bobo5b
obo9bo6bo9bobo5bobo5bo$81bo3bobobo2b2o4b4o4bo2b2o2bo4b4o4b2o2bobobo3bo
$78b3o7bo6b2o3bo18bo3b2o6bo7b3o$78bobo4bo8b2o2bo2b2o2b2o6b2o2b2o2bo2b
2o8bo4bobo$78bo23bo14bo23bo$78bo2bo2b2o10bo5bo4bo4bo4bo5bo10b2o2bo2bo$
79b2o16b4o2bo3bo4bo3bo2b4o16b2o$79bo2bo3bo17b4o4b4o17bo3bo2bo$86b2o9bo
2b2o3b3o4b3o3b2o2bo9b2o$83b3o3bo8bo5bobo6bobo5bo8bo3b3o$88bo7b2obo5bo
8bo5bob2o7bo$83bo3bobo7bo24bo7bobo3bo$84b3obo42bob3o$83bo5bo40bo5bo$
85bob2o42b2obo$85bo48bo!

[Sokwe]

Memory/CPU trade-off. The BFS search is pretty good at knowing how much memory it is using and falling back to filtering down by DFS so it can continue. LLSSS has a "bridge" mode where it will start DFSing across a row to avoid having to reify the unfiltered center columns but it is fundamentally limited in that the state after each row is what it would be either way so once that hits memory it's doomed.

Set a memory limit. Optional, but w/o it bigger searches will happily fill memory and depending on your OS and configuration you might not like what happens (thrash in swap, get oomkilled, etc.). This is 4GB which is more than enough to find this arm.

Code: Select all

$ ulimit -v 4194304
$

I've been trying to extend wings of the 2c/5 wickstretcher partial results, but they keep using too much memory and getting killed. For example, I run the following input file 2c5-wing.in

Code: Select all

  ...........**...*........ |  ...........**...**....... |  ...........**...**....... | ......*.....****...*.....  | ...........*****.........  
  ...........**....*....... |  ..........*..*....*...... |  ..........*..**.**....... | ..........**...*..*......  | ..........**....*........  
  .........*..*...***...... |  .........*..**.*......... |  .........**.**.*......... | .........*...**.*........  | .........*....*.*........  
  .........***..**.**...... |  .........*....**......... |  ........***....*......... | .........*.....*.........  | ........***..*...*.......  
  ..........***.*...**..... |  .........*....*.......... |  .........**.............. | .........*..*..***.......  | .............*...*.......  
  ...........**.*...**..... |  ..........*.*.**..**..... |  ...........*..**.*.*..... | ............*.***..*.....  | ...........**.....*......  
  ..............*.......... |  ............*.*..***..... |  .........**.*.*....*..... | ..........*..*.**..*.....  | ..........**.*....*......  
  ..........*.*.*.*.*...... |  .........**.*.*.**....... |  .........**.*............ | .........*.*.*..**.......  | .........*.*.*...........  
  .........**.**.**........ |  .........*..*...**....... |  ........*...*..***....... | .........*.**.*.***......  | .........*.*..***.*......  
  ..........**..*.......... |  .........****............ |  ........**....*..*....... | ..........*..*....*......  | .........**........*.....  
  .......*......***........ |  ......**...*.****........ |  ......***..*.****........ | .......*..*..**.***......  | .............**..........  
  ......**....*....*....... |  ......**.....*...*....... |  .....*.*.....*...*....... | ......*...........**.....  | .....***....*..**........  
  .....*.....*..****....... |  .....*.....*...*.*....... |  .....*..*...*.*..**...... | .....**.....***..***.....  | .....*.....*****.........  
  ......**..*.....*........ |  ......***.*..*...*....... |  .....*....**.....*....... | ......**..**.*.****......  | .....***..**.......*.....  
  ......?????????????...... |  ......?????????????...... |  ......?????????????...... | ......?????????????......  | ......?????????????......  

with

Code: Select all

./target/release/rlife 2c5-wing.in 0 4 2

and it eventually gets killed after running out of memory (I have ~28 GB or RAM available). Is there a way to get such large-width searches to complete without using too much memory?

Also, is there an easy way to save the search state during the search so that it can be stopped and restarted at a later time?

[amling]

... and it eventually gets killed after running out of memory (I have ~28 GB or RAM available). Is there a way to get such large-width searches to complete without using too much memory?

There are many things, each more prototypical and less polished than the last. As you quoted, there is bridge mode, but it's a mess. Set environment variable `LLSSS_BRIDGE_LEN` to whatever you want. Default behavior is `LLSSS_BRIDGE_LEN=0`. Unfortunately no way to change during a search and the higher the number the slower it is, even for rows it's not actually needed. Also, as noted, it cannot save you if the in-between-row state is too big for memory, no matter how high you set it and how slow you make it.

I had also considered looking into storing state on disk since we're mmapping anyway, but never got around to it.

Also, is there an easy way to save the search state during the search so that it can be stopped and restarted at a later time?

"Easy", maybe not. There is environment variable `LLSSS_STATE_FILE`. If set it will load from that file at startup and save to that file after each row. So far with bridging I have generally been running with state and bridge length 0, waiting until it dies, restarting with bridge length 1 (and picks up at last checkpoint), waiting until it dies, etc.

I am not super sure how to make this better as the program itself cannot really tell when it's going to die in order to decide to up bridging. Its estimate of its own memory use is not very good if you compare the numbers it prints on `Memory:` lines with `VmPeak:` values. I had considered maybe some sort of orchestration wrapper to run the program repeatedly with higher bridging as I had been doing. In the end I did nothing since I haven't been using bridging very much, it's just so very slow.

If you're running fairly recent code (~2 days ago) and you can run rctl (e.g. you're not on windows where I gutted it), you can invoke `checkpt` or `checkpt_to`, something like `cargo run -p ars_rctl_cli -- --ep llsss invoke checkpt` in the `ars` subdirectory. That assumes you're running only one search at a time, you may need to add `--cwd (wherever)` or `--pid (whatever)` or such before `--ep` to disambiguate if you're running multiple. It may take a while to do anything since it can only checkpoint in between rows.

EDIT:

...and it eventually gets killed after running out of memory (I have ~28 GB or RAM available).

Just to make sure, you're running the `MmapVec` version as opposed to the mmap-stripped for-windows version? Should be `cs: PhantomData::<MmapVec<SL>>,` in `main_llsss`. My observation was that `Vec<SL>` did very badly on memory and the ratio between the program's internal estimate of memory and the OS's was even wider than it is with `MmapVec<SL>`.

EDIT2:

Even with `MmapVec` that search took ~35G over here. I really gotta look into that disk-backed mmap business...

[amling]

... and it eventually gets killed after running out of memory (I have ~28 GB or RAM available). Is there a way to get such large-width searches to complete without using too much memory?

Even with `MmapVec` that search took ~35G over here.

I've reworked how the internals are stored in a way that saves memory in most cases. I am now (as of e.g. `96ed2e79df7e`) able to complete the proposed search in 13.5m minutes with VmPeak of 26.2G.

[amling]

... and it eventually gets killed after running out of memory (I have ~28 GB or RAM available). Is there a way to get such large-width searches to complete without using too much memory?

Even with `MmapVec` that search took ~35G over here.

I've reworked how the internals are stored in a way that saves memory in most cases. I am now (as of e.g. `96ed2e79df7e`) able to complete the proposed search in 13.5m minutes with VmPeak of 26.2G.

I reworked the search order, so rather than expanding a tile at a time it expands one bit at a time. For geometries where tiles are single bits (e.g. gcd-free f2b searches like c/N or 2c/5) this is no change, but for others (any gcd like 2c/4, any oscillator, any s2s) it can make a big difference. E.g. this 2c/5 s2s search goes from trying to expand 5 bits at a time to expanding one bit at a time. This lets it meet in the middle of the board and filter down the edges much earlier. It will have to do more rounds of expansion, but hopefully they will be somewhat smaller.

I'm having a tough time benchmarking it since I have other searches running, but so far it seems a little bit slower (maybe ~12%) and a lot more efficient in memory. The above 2c/5 sideways search but cut down to 3 left pad (instead of 4) goes from ~8.8G to ~3.25G and 3:47 to 4:15. The memory change is exact but the runtime may be somewhat dependent on level of conflict with other searches running at the same time. More detailed benchmarking perhaps TBD later.

Unfortunately this rewrite breaks every single bit of feature (every edge, every monitor, every ends) and so there is a lot of rewriting to do before I can really do anything resembling publishing it. Stay tuned.

[Sokwe]

I reworked the search order, so rather than expanding a tile at a time it expands one bit at a time. For geometries where tiles are single bits (e.g. gcd-free f2b searches like c/N or 2c/5) this is no change, but for others (any gcd like 2c/4, any oscillator, any s2s) it can make a big difference. E.g. this 2c/5 s2s search goes from trying to expand 5 bits at a time to expanding one bit at a time. This lets it meet in the middle of the board and filter down the edges much earlier. It will have to do more rounds of expansion, but hopefully they will be somewhat smaller.

I'm having a tough time benchmarking it since I have other searches running, but so far it seems a little bit slower (maybe ~12%) and a lot more efficient in memory. The above 2c/5 sideways search but cut down to 3 left pad (instead of 4) goes from ~8.8G to ~3.25G and 3:47 to 4:15. The memory change is exact but the runtime may be somewhat dependent on level of conflict with other searches running at the same time. More detailed benchmarking perhaps TBD later.

Unfortunately this rewrite breaks every single bit of feature (every edge, every monitor, every ends) and so there is a lot of rewriting to do before I can really do anything resembling publishing it. Stay tuned.

Sounds interesting! I might start looking for that 2c/5 wickstretcher again. If this modification is slower there may be a benefit to still keeping the faster, more memory intensive version around as well.

[amling]

More detailed benchmarking perhaps TBD later.

I got a break in the other searches and stopped to benchmark this better.

Running the full search from above (left pad 4) with both current and new code on today's laptop went from 26.2G to 7.0G and 758.76s to 776.49s (+2.34%). I am not entirely surprised bigger searches benefit more comparatively on memory and I am also not surprised that benefit is presumably reducing the time penalty.

Right now my branch has two copies of the core search engine and various features either do or do not work with the new version. Going forward I neither want to keep both engines nor have to implement each new feature twice. My long term plan is probably to axe the old one and rename the new one over it, but for now I think they will have to coexist since I don't want to stop and port each feature to the new engine.

[amling]

More detailed benchmarking perhaps TBD later.

I've been running some 3c/6 searches for other reasons and thought they'd make a good benchmark as well. I've run (and now rerun with the new code) widths up to 18. 14-17 all show a pretty clear pattern:

Width 14: 130.54s to 160.79s (+23.18%), 4.02G to 2.44G (-39.46%)
Width 15: 349.53s to 431.98s (+23.59%), 7.86G to 3.93G (-49.98%)
Width 16: 864.73s to 1101.83s (+27.42%), 17.83G to 7.44G (-58.28%)
Width 17: 2249.18s to 2824.81s (+25.59%), 38.47G to 15.05G (-60.89%)

Width 18 is a little more complicated. The old code couldn't complete it in 60G and it took hours upon hours to drag through saving state files and bridging to finally finish at LLSSS_BRIDGE_LEN=3. That last bridging 3 run alone was 3.79h. The new code maxed out at only 32.14G and completed it in a single unbridged run of 1.94h.

Looking at the timing stats, a lot of the increase is in LlsssFilterWCycleAvoiding which makes sense. It's expensive and now has to run more often (once per bit rather than once per tile). I include it in this search (as well as searches from any sort of "cycle" that want to avoid just repeating the cycle forever), but not, for example, in searches trying to complete a typical random slice (like the 2c/5 s2s "wing" search we were discussing earlier).

It's unfortunate that this overall change is a meaningful CPU hit for [some] searches that [currently] fit in memory, but I think postponing that memory ceiling is worth it. Many of my searches don't even have LlsssFilterWCycleAvoiding and virtually all of my search projects end when they fill memory and I give up on running any further because bridging is so painful to manage and so slow.

[Sokwe]

Looking at the timing stats, a lot of the increase is in LlsssFilterWCycleAvoiding which makes sense. It's expensive and now has to run more often (once per bit rather than once per tile). I include it in this search (as well as searches from any sort of "cycle" that want to avoid just repeating the cycle forever), but not, for example, in searches trying to complete a typical random slice (like the 2c/5 s2s "wing" search we were discussing earlier).

While using this filter is good for benchmarking, does a width-18 asymmetric 3c/6 search actually have cycles? If not, it might be illustrative to compare the search with and without the cycle filter.

I would like to see a completion of width 19 and 20 3c/6 searches (I expect no spaceships based on Andrew J. Wade's searches), but judging by the increase in memory usage, the width-20 search at least will be out of reach.

Just to clarify, are search results that return zero ships sufficient to prove that no ship exists at that width (barring unknown bugs)?

It's unfortunate that this overall change is a meaningful CPU hit for [some] searches that [currently] fit in memory, but I think postponing that memory ceiling is worth it. Many of my searches don't even have LlsssFilterWCycleAvoiding and virtually all of my search projects end when they fill memory and I give up on running any further because bridging is so painful to manage and so slow.

I agree that the version with the lower memory footprint is preferable to the faster version. An earlier commit can always be used if I need the extra speed.

[amling]

While using this filter is good for benchmarking, does a width-18 asymmetric 3c/6 search actually have cycles? If not, it might be illustrative to compare the search with and without the cycle filter.

Yes, but not in the human common-sense way you're probably thinking. The all-zeros grid I start it with can cycle forever if nothing stops it. Previously I had a read-only hack that would detect when all living spines (a spine is a single W column of cells) started with an extra W row of zeros and stop the search, but it was hugely wasteful (as it means the search is left more or less duplicated at each W height). The newer cycle-avoiding filter will edit an ongoing search to drop all spines that cannot be connected to a spine which looks "useful" (doesn't start with an extra W row of zeros).

Just to clarify, are search results that return zero ships sufficient to prove that no ship exists at that width (barring unknown bugs)?

Yes, although there are tens of thousands of lines of hairy rust code I wrote in a vacuum and of course many levels and types of bugs. I am especially nervous about the cycle-avoiding filter being used to stop searches but my hardest thinking upon it concludes that it will not miss anything.

I would like to see a completion of width 19 and 20 3c/6 searches (I expect no spaceships based on Andrew J. Wade's searches), but judging by the increase in memory usage, the width-20 search at least will be out of reach.

I retain some hope: based on how it was going I'd extrapolate somewhere in the 64G range for width 19 (this laptop has 64G and there is always bridging) and 128G for width 20. There exist computers with that much memory and bridging may even be able to swing it in 64G. I will likely start the width 19 search before going to bed tonight and perhaps see you on another thread soon.

[amling]

I retain some hope: based on how it was going I'd extrapolate somewhere in the 64G range for width 19 (this laptop has 64G and there is always bridging) and 128G for width 20. There exist computers with that much memory and bridging may even be able to swing it in 64G. I will likely start the width 19 search before going to bed tonight and perhaps see you on another thread soon.

I may have hoped too hard. Width 19 did finish overnight but it ended up doing some bridging. I had set it up to save state files and blindly fail forward to deeper bridging until it completes. It ended up with ~2.5h in bridging 0-2 combined and then ~7.4h in the final bridging 3 run. It could probably be done faster if the bridging 3 run were stopped and restarted at lower bridging once it passed the critical point, but I was sleeping.

Longest, "firstest" partial 38 (nonzero) rows:

Code: Select all

                        |                         |                         |                         | ....................... | .......................
                        |                         | ....................... | ....................... | ....................... | .......................
....................... | ....................... | ....................... | ....................... | ..............*........ | .............***.......
....................... | ....................... | ..............*........ | .............***....... | .............***....... | ........*...*...*......
..............*........ | .............***....... | .............***....... | ........*...*...*...... | .......***..***.**..... | .......***.*....**.....
.............***....... | ........*...*...*...... | .......***..***.**..... | .......***.*....**..... | ......*..***.*..*...... | ......**...*.**.*.*....
.......***..***.**..... | .......***.*....**..... | ......*..***.*..*...... | ......**...*.**.*.*.... | .....*...*.*....*.**... | .....**..*.*....*.**...
......*..***.*..*...... | ......**...*.**.*.*.... | .....*...*.*....*.**... | .....**..*.*....*.**... | .....*.....*..*.*.**... | ......*....*...*....*..
.....*...*.*....*.**... | .....**..*.*....*.**... | .....*.....*..*.*.**... | ......*....*...*....*.. | .......*..*........*... | .....**................
.....*.....*..*.*.**... | ......*....*...*....*.. | .......*..*........*... | .....**................ | ....*.*............**.. | ...**.*.*..........**..
.......*..*........*... | .....**................ | ....*.*............**.. | ...**.*.*..........**.. | ...**.**.*............. | ...*.....**............
....*.*............**.. | ...**.*.*..........**.. | ...**.**.*............. | ...*.....**............ | ...*.***.**............ | .....*.*.*.............
...**.**.*............. | ...*.....**............ | ...*.***.**............ | .....*.*.*............. | ..**.....*.*........... | ..**.*.*.*.**..........
...*.***.**............ | .....*.*.*............. | ..**.....*.*........... | ..**.*.*.*.**.......... | .....*.*.*.**.......... | ....*.*.*..*...........
..**.....*.*........... | ..**.*.*.*.**.......... | .....*.*.*.**.......... | .....*.*.*.**.......... | .....*.....*.*......... | .....*..**...*.........
...*.*.*.*.**.......... | .....**.*..**.......... | ..**.*****...*......... | ..**.*.......*......... | ..**.*..*.**..*........ | .....*....***..........
...**.*....*........... | ...*.....*.**.......... | ...*.*.***...*......... | ...*.*...*..***........ | .....**................ | ....****.*.*...........
....******............. | ...**...*.***.......... | ...*.*.......*......... | ..**.*...*..***........ | ......*..*.*........... | ...**.**..*............
.......*...**.......... | ....**....***.......... | ...***.**....*......... | ..**...**...**......... | ..***...*..*........... | ...*....***............
...*...***..*.......... | .......**.*.*.......... | ...*.***....*.......... | ............**......... | .......**.....*........ | ...*...**..............
...*.......*........... | ...**..*****........... | ..***..*....*.......... | .......*...***......... | .......*......*........ | .......*.*.............
..**..*...*............ | ..**......**........... | ..***.*.....*.......... | ..*.*.*.*..***......... | ...**...*.*............ | ...*..*.*.**...........
.......*..*............ | ......**..**........... | ......***...*.......... | ...*.****..**.......... | ...****.****.*......... | ...*..***.***..........
......*..**............ | ......**.***........... | .........*.*........... | .........*............. | .....*.......*......... | .......*.***.**........
......*.....*.......... | .....***............... | .....*.**.***.......... | ......*.***.**......... | ......*.....**......... | ......*.....*..........
......*......*......... | ............**......... | .....*......*.*........ | ......*****.**......... | .....**......**........ | .......*...*..*........
.........*...*......... | ......*.*...***........ | ........*..*...*....... | ......*.*..*...*....... | .....**....**.......... | ....*......*****.......
......***...*.*........ | .......**...*.**....... | ......***..**.**....... | ......*.*.*.....*...... | .....*....*....**...... | .....**...*.*..........
...........*..**....... | .....*.....*........... | .....*.*...*****....... | ....*.....**...*....... | ..........**........... | .........*....*........
.....**...*...**....... | .....**...*..*..*...... | ....***..*............. | ....*.*.*.*............ | ....*.....**..***...... | ...***...******.*......
.....*....*.*..*....... | .....*...***.*..*...... | ....*....*...*.***..... | ...**.*.*.....**.*..... | ...**.*.*....**.*...... | ...***.**.**...........
......*..*....**....... | ....*.*....**...*...... | ....*..*.....*..**..... | ......*.*...**...*..... | ........**..****.**.... | ...***..**.*.....**....
...*.**.....****....... | .....***....*..**...... | ...***.*....*..*....... | ...******...*...**..... | ....*...*..**.*..*..... | ........*..*...***.....
..*....*.....*...*..... | ..**...*...*....***.... | ..*.....*..*......*.... | ......**....*.***...... | ....*....*.*.*....*.... | ....**..**.*.*....**...
...*.**....**....**.... | ..***.**...**...***.... | ....*.*......*.**..*... | .......**.*.....*.**... | .....*..*.*.....*.**... | ...*.*....***.*........
...*...*...*....*..*... | ...*...**.**.**....*... | ........***...***.*.... | ...**.*.*.**....*.*.... | ...**.....*..*.*..**... | ....*.....**...*...*...
....**..**...******.... | ...*.**.*...**..*...... | ..**.**.**.****...**... | ....*****..****........ | ..........*...**.*..... | ...*.....***...*.*.....
...*.*.......**...**... | ...*.*............**... | .....*............**... | ...*...**...***..*..*.. | ...*.*...*.*...*..**... | ..**......**.*.....*...
...**.........***...... | .....*..........*.**... | ....**.*.......*..**... | ...*...*.*....*...**... | ..***.......*.**.***... | ..*******....*...*.....
..***....*....*.*.*.... | ..*...***....**.*...... | ...**.*****..**........ | ...*..**...*..*..*..... | ......***.....**..*.... | ....*.*..**...**..**...
.....****..*..*.*.*.... | ..*.**...***..*...**... | ....*....***.....**.*.. | ...............*....... |                         |                        
..*...***..***.....*... | ....**..*...**.*..***.. | ....**.*...**.**....... |                         |                         |                        

or single phase:

Code: Select all

x = 19, y = 38, rule = B3/S23
12bo$11b3o$5b3o2b3ob2o$4bo2b3obo2bo$3bo3bobo4bob2o$3bo5bo2bobob2o$5bo
2bo8bo$2bobo12b2o$b2ob2obo$bob3ob2o$2o5bobo$bobobobob2o$b2obo4bo$2b6o$
5bo3b2o$bo3b3o2bo$bo7bo$2o2bo3bo$5bo2bo$4bo2b2o$4bo5bo$4bo6bo$7bo3bo$
4b3o3bobo$9bo2b2o$3b2o3bo3b2o$3bo4bobo2bo$4bo2bo4b2o$bob2o5b4o$o4bo5bo
3bo$bob2o4b2o4b2o$bo3bo3bo4bo2bo$2b2o2b2o3b6o$bobo7b2o3b2o$b2o9b3o$3o
4bo4bobobo$3b4o2bo2bobobo$o3b3o2b3o5bo!

EDIT: Which thread should this get more officially put on? The last I saw (width 18) was on "3c/7 othogonal and 2c/9 diagonal spaceships" which seems ... unlikely to be right.

[Sokwe]

Which thread should this get more officially put on?

It should go in the spaceship discussion thread. You can simply edit this information into your latest post there. Please also note (if true) that this should (barring unknown bugs) prove that no width-19 3c/6 ships exist.

[amling]

(this is about the one-bit-at-a-time changes and the original 2c/5 wing search above)

Running the full search from above (left pad 4) with both current and new code on today's laptop went from 26.2G to 7.0G and 758.76s to 776.49s (+2.34%). I am not entirely surprised bigger searches benefit more comparatively on memory and I am also not surprised that benefit is presumably reducing the time penalty.

The one-bit-at-a-time change also changes the calculus on how best to store the next row. Previously each "bcol" entry could be up to 2^(2 * tile_bits) entries in the expanded bcol and each "col" entry could be up to 2^(3 * tile_bits). For tile_bits of 2 or 4 or worse this could be quite a few so we stored them as themselves, but only if they were present. Now expanding a bit at a time that's only 2^2 and 2^3 which is a lot more bounded and so storing everything as giant bitvectors has the potential to do quite well.

For "bcols" before we'd store 8 bytes per new entry but now we're gonna store 4 bits per old entry. Similarly "cols" go from 8 bytes per new entry to 8 bits per old entry. At the most memory-intense part of the search things are expanding and so there are actually more new entries than old entries making the disparity greater. Once a row of expansion is done we do still have to translate it to the full format, but at that point we've met in the middle and filtered out a great deal of crap.

I was worried this would do worse on CPU since it has to spend a bunch of time translating between the bitvector indices and what the actual eventual fully-reified format is, but in the end it did not. It's actually winning by a rather serious margin, even with over half the entire search time concentrated in just "translate bitvector col to real col".

Benchmarking the 2c/5 s2s search from above (`2c5-wing.in`, left pad 4, right pad 2) before and after it is reduced from VmPeak of 6.98G to 4.77G and from runtime of 778.63s to 547.51s.

I still have to clean it up and publish it, but it should be up on github probably later today.

EDIT: Pushed, main change is `16f66acf3408`.

[amling]

Benchmarking the 2c/5 s2s search from above (`2c5-wing.in`, left pad 4, right pad 2) before and after it is reduced from VmPeak of 6.98G to 4.77G and from runtime of 778.63s to 547.51s.

I migrated the bit vector nonsense from the implicit allocator to the fancy mmap-based on which gets that down to 4.54G.

Better than that though, is stripping out all this sorting. Previously for various reasons we kept all bcols sorted which is both expensive on its own and was making the most expensive phase of the entire search (translate bit vector cols to real cols) harder than it needed to be (lots of expensive bisection search in adjacent bcols). No longer sorting bcols rips out a bunch of code and makes everything way faster. Like way, way faster. Like this same search, even under moderate contention with other research computing running in the background took only 350s.

Pushed as of now (`6ce67c323ba9`).

EDIT: 227s uncontested.

[May13]

Unfortunately even if you get past that I have no idea what is going to happen when you reach a `libc::mmap` call (or `mremap`). Will it work? Die immediately? Return successfully but then do something broken and insane later?

Compilation stopped at 10 errors "cannot find ? ? in crate `libc`":

Code: Select all

$ cargo build --release
   Compiling autocfg v1.0.0
   Compiling lazy_static v1.4.0
   Compiling cfg-if v1.0.0
   Compiling proc-macro2 v1.0.9
   Compiling unicode-xid v0.2.0
   Compiling scopeguard v1.1.0
   Compiling libc v0.2.68
   Compiling syn v1.0.17
   Compiling cfg-if v0.1.10
   Compiling maybe-uninit v2.0.0
   Compiling rayon-core v1.9.1
   Compiling serde v1.0.105
   Compiling winapi v0.3.8
   Compiling ryu v1.0.3
   Compiling byteorder v1.3.4
   Compiling either v1.6.1
   Compiling ppv-lite86 v0.2.16
   Compiling bitintr v0.3.0
   Compiling ars_macro v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\macro)
   Compiling itoa v0.4.5
   Compiling ars_sync v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\sync)
   Compiling getrandom v0.2.4
   Compiling crossbeam-utils v0.8.4
   Compiling crossbeam-utils v0.7.2
   Compiling memoffset v0.6.3
   Compiling memoffset v0.5.4
   Compiling num-traits v0.2.11
   Compiling crossbeam-epoch v0.8.2
   Compiling num-integer v0.1.42
   Compiling rayon v1.5.0
   Compiling itertools v0.10.3
   Compiling ars_ds v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\ds)
   Compiling rand_core v0.6.3
   Compiling ars_aa v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\aa)
   Compiling rand_chacha v0.3.1
   Compiling num_cpus v1.13.0
   Compiling quote v1.0.3
   Compiling rand v0.8.4
   Compiling crossbeam-channel v0.5.1
   Compiling crossbeam-epoch v0.9.4
   Compiling crossbeam-queue v0.2.1
   Compiling crossbeam-channel v0.4.2
   Compiling time v0.1.42
   Compiling crossbeam-deque v0.8.0
   Compiling crossbeam-deque v0.7.3
   Compiling chrono v0.4.11
   Compiling crossbeam v0.7.3
   Compiling serde_derive v1.0.105
   Compiling bincode v1.2.1
   Compiling serde_json v1.0.48
   Compiling rlife v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife)
error[E0425]: cannot find function `mmap` in crate `libc`
  --> src\mmap.rs:28:19
   |
28 |             libc::mmap(
   |                   ^^^^ not found in `libc`

error[E0425]: cannot find value `PROT_READ` in crate `libc`
  --> src\mmap.rs:31:23
   |
31 |                 libc::PROT_READ | libc::PROT_WRITE,
   |                       ^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `PROT_WRITE` in crate `libc`
  --> src\mmap.rs:31:41
   |
31 |                 libc::PROT_READ | libc::PROT_WRITE,
   |                                         ^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_PRIVATE` in crate `libc`
  --> src\mmap.rs:32:23
   |
32 |                 libc::MAP_PRIVATE | libc::MAP_ANON,
   |                       ^^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_ANON` in crate `libc`
  --> src\mmap.rs:32:43
   |
32 |                 libc::MAP_PRIVATE | libc::MAP_ANON,
   |                                           ^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_FAILED` in crate `libc`
  --> src\mmap.rs:37:25
   |
37 |         if ptr == libc::MAP_FAILED {
   |                         ^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find function `mremap` in crate `libc`
  --> src\mmap.rs:59:19
   |
59 |             libc::mremap(
   |                   ^^^^^^ not found in `libc`

error[E0425]: cannot find value `MREMAP_MAYMOVE` in crate `libc`
  --> src\mmap.rs:63:23
   |
63 |                 libc::MREMAP_MAYMOVE,
   |                       ^^^^^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_FAILED` in crate `libc`
  --> src\mmap.rs:66:25
   |
66 |         if ptr == libc::MAP_FAILED {
   |                         ^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find function `munmap` in crate `libc`
   --> src\mmap.rs:102:19
    |
102 |             libc::munmap(self.ptr, len as libc::size_t)
    |                   ^^^^^^ not found in `libc`

For more information about this error, try `rustc --explain E0425`.
error: could not compile `rlife` due to 10 previous errors

Not sure what to tell you, I guess `libc` crate on cygwin has less stuff in it? My ability and willingness to debug cygwin remotely is not super high and I'm not very much not excited to make any real changes to the code to make it portable to such a strange place. Is Microsoft's "WSL" a better linux? Can you dig up a linux box? Can you rent one from EC2?

I guess you could also try ripping out all the mmap code although that is going to be a much more complex edit. I left the pre-mmap versions in, but generally don't use them (they're faster but fragment memory horribly and given how memory-bound this is I always make that trade). You'd want to look at switching `MmapVec<SL>` to `Vec<SL>` where it's configured in `main_llsss` but then also delete all the remaining compiler errors in the now-unused mmap code. Unless you are yourself a programmer with modest to advanced knowledge of rust I can't encourage this path.

EDIT: Ripped out mmap and pushed `20220523-demo3` branch. Still gonna require modest rust knowledge or a great ability to mimic surrounding code to actually configure to run, even if this branch works out.

Now I have Windows 11, so I can use WSL. There are no more problems with compilation.
But I can't get rid of another error:

Code: Select all

thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/llsss/geom.rs:120:25

Example (already discussed before):
Input file

Code: Select all

 ............................ | ............................ | ............................ | ............................ 
 ................*........... | ............................ | ............................ | ............................ 
 ............................ | ............................ | ............................ | ..............***........... 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 

Velocity (c/4o s2s)

Code: Select all

let vu = (1, 0, 0);
    let vv = (-1, 0, 4);
    let vw = (0, 1, 0);
    const TILE_BITS: usize = 4;

Default configuration with different velocity (from github) failed with the same error.

[amling]

Example (already discussed before):
Input file

Code: Select all

 ............................ | ............................ | ............................ | ............................ 
 ................*........... | ............................ | ............................ | ............................ 
 ............................ | ............................ | ............................ | ..............***........... 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 

Velocity (c/4o s2s)

Code: Select all

let vu = (1, 0, 0);
    let vv = (-1, 0, 4);
    let vw = (0, 1, 0);
    const TILE_BITS: usize = 4;

Default configuration with different velocity (from github) failed with the same error.

Oh the shame, I need to write release notes or something. Somewhere in there I changed the initial coordinates of the grid parser so old files will want pipes added on the front to produce the same parsed grid (matches the output format and matches the format I prefer to edit with, with bounding pipes on both sides). For most f2b and b2f configurations it won't matter but s2s configurations the staggering of the generations is finicky and confusing and all the errors messages are awful.

I would expect this to work:

Code: Select all

| ............................ | ............................ | ............................ | ............................ |
| ................*........... | ............................ | ............................ | ............................ |
| ............................ | ............................ | ............................ | ..............***........... |
| ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ |
| ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ |
| ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ |

[May13]

Example (already discussed before):
Input file

Code: Select all

 ............................ | ............................ | ............................ | ............................ 
 ................*........... | ............................ | ............................ | ............................ 
 ............................ | ............................ | ............................ | ..............***........... 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 
 ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ 

Velocity (c/4o s2s)

Code: Select all

let vu = (1, 0, 0);
    let vv = (-1, 0, 4);
    let vw = (0, 1, 0);
    const TILE_BITS: usize = 4;

Default configuration with different velocity (from github) failed with the same error.

Oh the shame, I need to write release notes or something. Somewhere in there I changed the initial coordinates of the grid parser so old files will want pipes added on the front to produce the same parsed grid (matches the output format and matches the format I prefer to edit with, with bounding pipes on both sides). For most f2b and b2f configurations it won't matter but s2s configurations the staggering of the generations is finicky and confusing and all the errors messages are awful.

I would expect this to work:

Code: Select all

| ............................ | ............................ | ............................ | ............................ |
| ................*........... | ............................ | ............................ | ............................ |
| ............................ | ............................ | ............................ | ..............***........... |
| ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ |
| ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ |
| ...............?????........ | ...............?????........ | ...............?????........ | ...............?????........ |

Thank you! This file works. Moreover, I managed to get a nice looking partial c/4o dot sparker:

Code: Select all

x = 17, y = 73, rule = B3/S23
10bo2$7bo4bo$6bo3bo2bo$5bo2b2obo$5bob2o2b3o$4b2o5b3o$6b4ob3o$8bo$2b2o
2b3o2bobo$2bobo2bo3bobo$5bobo4bo$2b3o8b3o$4bob2o5bob2o$3bo8b2ob2o$3b3o
9bo$2bo11bo$2bob2o3bo$2obo5bo$b2o3b3obo$3b2ob2o$3b2ob2ob2o$4bobo$6bobo
$6bobo$6b3o$8bo$5bo3b2o$5b6o$3b2o$3b2o3bo2$3b3obo$3bobobob2o$3bo3b2o$
3bo3bo$3bo2bo$7bo2bo$7bo2bo$6b2o$4b3ob2obo$3b2obo2bobo$5b3obo$7bobo$5b
o3bo$3bo2b3o$3bo$2bo2b3o2b2o$b3obo5bo$2bo2b4o3bo$2b2obo2bo$2bo2b2ob2o$
b2ob3obo$bo3bo3b3o$2b2o3bo4bo$3b2o3b4o$3bob2o3bobo$4b2o$8b2o$5b4o$4bo
4bo$4b3o2bo$2bo$2bo2bob3o$bo3bobobo$2b3obob2obo$6b2obobo$5bo3bob2o$10b
2o$bo2b2o3bo2bo$b2obo3bo$2b2o2bob3obo$bo6bobo!

Edit: Completed!

Code: Select all

x = 76, y = 73, rule = B3/S23
57bo$56b2o$56bob2o3bob2o$25bo7bo5bo14b2obo2b2obo2bo$8b3o12b2obo4b5o2bo
bo12b3o2bobob2obo3bo$22b2o7bo4bo4bo3bob2o9bobo3bo4b3o$8bobo3bo6b3o3b4o
4bo2b2obo5bo2b7o5bo3bobo3bo$12b3o5bo3b3o2b3o2b2o2b2obob3obo2bo3b3o5bob
3obobo2bo$11b2obo3b3o3bob2obobobo6bobo4bob4o3bo9b3ob2o$9bo2bo2b2o3bobo
2bo5b4o7b3o9bo2b2o9bo2bo$8b2o2bobobo2bob3obo2bo3bobo5b3o11bobo15bo2bo$
7b2o12b2o4bo2bo3bo6b2o3bobo14bob2ob4o$16b5o10bo2bo3b2o4bo4bo11b2obo3b
3o2bo$8bob2o2bo3bo2bo10bo5b3ob5o2b2o12bob2ob3obo$4b8o25bo2bobo2b2o16b
2o$4bo3bo2bo49b2obo$4b3ob2o50b3o$6b2o5b2o44bo4b2o$7bo2b2obo50bobo$7bo
57bobo$8bo2bo49b3o$9bobo48b2obo3bo$11bo49bo6bo$10b3o51bob4o$8b3ob2o48b
2obo3bo$7bo54b2o6bo$7bo4b2o47bo6bo$8bob4ob3o50bobo$10b2o2b4o44bo2bo$
11b2o3b2o46b2o2b3o$7b4o2b2o54bo$11bo4bo46bo$9b2ob4o46b8o$14b2o46b3o2b
3o$8bo56b3o$8bob2o48b2o2b2o3bo$59bo4bo4bo$59bobo2bo$8b3o49bo2b2o$7b2ob
2o50b2o$3b3o7b3o$2b3o9b3o43bo3bo$bo15bo42bobob2o$o3bob3ob3obo3bo41bo3b
o$bo3bob2ob2obo3bo42bo3bo$bob3ob2ob2ob3obo43bob2o$3b2obo5bob2o45bobo$
6b3ob3o50bo2b2o$7b2ob2o47b2o2b2ob2o$4b2o7b2o44b2ob2ob2o$3bo4bobo4bo46b
o3bo$59bo3b2obo$6bo5bo46bo$5b2o5b2o49bo3bo$60bo2b3obo$5b2o5b2o46bobo5b
o$4b3o5b3o45bo7bo$3bo3b2ob2o3bo42b2o5bo2bo$3bo4bobo4bo51bo$6bobobobo
45bobo$4bo9bo45bo$3b2o9b2o42bo$3bo11bo40b2ob2o$58bo$2b2o11b2o41bo2bo$
58bo$57bo2bo$57b3o$57bo2$56b2o2$56b3o!