Effect of the partition on the iteration efficiency/speed

main.rs

use std::time::Instant;

#[derive(Clone, Copy, Debug)]
struct GameConfig<const NUM_OF_SHIPS: usize> {
    ship_lengths: [u8; NUM_OF_SHIPS],
    board_width: u8,
    board_height: u8,
}

impl<const NUM_OF_SHIPS: usize> GameConfig<NUM_OF_SHIPS> {
    pub fn new(board_width: u8, board_height: u8, ship_lengths: [u8; NUM_OF_SHIPS]) -> Self {
        GameConfig {
            board_width,
            board_height,
            ship_lengths,
        }
    }
}

// Bitboard with exactly one bit set at cords (x, y) on board of size (w, h)
fn bitboard_xy(x: u8, y: u8, w: u8, h: u8) -> u128 {
    assert!(x < w && y < h);
    1 << (x + y * w)
}

// Vector of all bitboards for piece of length l on board of size (w, h)
fn bitboards_for_piece(l: u8, w: u8, h: u8) -> Vec<u128> {
    assert!(w * h < 128);
    let mut r = Vec::with_capacity(2 * (w * h) as usize);
    for x in 0..w {
        for y in 0..h {
            if x + l <= w {
                r.push((x..(x + l)).fold(0, |acc, p| acc | bitboard_xy(p, y, w, h)));
            }
            if y + l <= h {
                r.push((y..(y + l)).fold(0, |acc, p| acc | bitboard_xy(x, p, w, h)));
            }
        }
    }
    r
}

#[inline(never)]
pub fn join_boards(bitboards_a: &Vec<u128>, bitboards_b: &Vec<u128>) -> Vec<u128> {
    let mut res: Vec<u128> = Vec::with_capacity(bitboards_a.len() * bitboards_b.len());
    for a in bitboards_a {
        for b in bitboards_b {
            let g = a | b;
            // No overlap allowed
            if a & b == 0 {
                res.push(g)
            }
        }
    }
    res
}
  
struct BattleshipIteratorV2<const NUM_OF_SHIPS: usize> {
    pub part_a: Vec<u8>,
    pub part_b: Vec<u8>,
    pub boards_a: Vec<u128>,
    pub boards_b: Vec<u128>,
}

impl<const NUM_OF_SHIPS: usize> BattleshipIteratorV2<NUM_OF_SHIPS> {
    // The i-th bit in the partition_id corresponds to whether the i-th ship should be in the first or second partition
    pub fn new(cfg: GameConfig<NUM_OF_SHIPS>, partition_id: u64) -> Self {
        assert!(NUM_OF_SHIPS < 64);
        let mut part_a = Vec::new();
        let mut part_b = Vec::new();
        for i in 0..NUM_OF_SHIPS {
            let part = if (partition_id & (1 << i)) == 0 {
                &mut part_a
            } else {
                &mut part_b
            };
            part.push(cfg.ship_lengths[i]);
        }
        assert!(!part_a.is_empty() && !part_b.is_empty());

        let to_boards_fn = |part: &Vec<u8>| {
            part.iter()
                .map(|l| bitboards_for_piece(*l, cfg.board_width, cfg.board_height))
                .reduce(|a, b| join_boards(&a, &b))
                .unwrap()
        };

        BattleshipIteratorV2 {
            boards_a: to_boards_fn(&part_a),
            boards_b: to_boards_fn(&part_b),
            part_a,
            part_b
        }
    }
}

impl<const NUM_OF_SHIPS: usize> Iterator for BattleshipIteratorV2<NUM_OF_SHIPS> {
    type Item = u128;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        unimplemented!("Too much overhead. Use fold.")
    }

    #[inline]
    fn fold<B, F>(mut self, init: B, mut f: F) -> B
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> B,
    {
        let mut acc = init;
        for &b0 in &self.boards_a {
            for &b1 in &self.boards_b {
                if b0 & b1 == 0 {
                    acc = f(acc, b0 | b1)
                }
            }
        }
        acc
    }
}

fn main() -> anyhow::Result<()> {
    let game_cfg = GameConfig::new(10, 10, [5, 4, 3, 3, 2]);
    for partition_id in 0_u64..0b100000 {
        if partition_id.count_ones() == 0 || partition_id.count_ones() == 5 {
            continue;
        }
        let now = Instant::now();
        let iter = BattleshipIteratorV2::new(game_cfg, partition_id);
        let part_a = iter.part_a.clone();
        let part_b = iter.part_b.clone();
        let boards_a_len = iter.boards_a.len();
        let boards_b_len = iter.boards_b.len();
        let steps = boards_a_len * boards_b_len;
        let usage = (boards_a_len + boards_b_len) * size_of::<u128>();
        let ctr = iter.count();
        println!(
            "part_a={:?} part_b={:?} dim={} x {} usage={:.0?}MB efficiency={:.2?} Elapsed: {:.2?} ctr={} partition={:#07b}",
            part_a,
            part_b,
            boards_a_len,
            boards_b_len,
            usage as f64 / 1024f64 / 1024f64,
            30_093_975_536_f64 / steps as f64 * 100f64,

            now.elapsed(),
            ctr,
            partition_id,
        );
    }
    return Ok(());
}
  

results

# 1 ship in one partition - inner loop is smaller than outer
part_a=[4, 3, 3, 2] part_b=[5] dim=411770168 x 120 usage=6283MB efficiency=60.90 Elapsed: 25.55s ctr=30093975536 partition=0b00001
part_a=[5, 3, 3, 2] part_b=[4] dim=331346640 x 140 usage=5056MB efficiency=64.87 Elapsed: 23.37s ctr=30093975536 partition=0b00010
part_a=[5, 4, 3, 2] part_b=[3] dim=269056552 x 160 usage=4105MB efficiency=69.91 Elapsed: 21.71s ctr=30093975536 partition=0b00100
part_a=[5, 4, 3, 2] part_b=[3] dim=269056552 x 160 usage=4105MB efficiency=69.91 Elapsed: 21.58s ctr=30093975536 partition=0b01000
part_a=[5, 4, 3, 3] part_b=[2] dim=219572928 x 180 usage=3350MB efficiency=76.14 Elapsed: 20.08s ctr=30093975536 partition=0b10000

# 1 ship in one partition - outer loop is smaller than inner
part_a=[5] part_b=[4, 3, 3, 2] dim=120 x 411770168 usage=6283MB efficiency=60.90 Elapsed: 28.12s ctr=30093975536 partition=0b11110
part_a=[4] part_b=[5, 3, 3, 2] dim=140 x 331346640 usage=5056MB efficiency=64.87 Elapsed: 26.59s ctr=30093975536 partition=0b11101
part_a=[3] part_b=[5, 4, 3, 2] dim=160 x 269056552 usage=4105MB efficiency=69.91 Elapsed: 23.29s ctr=30093975536 partition=0b11011
part_a=[3] part_b=[5, 4, 3, 2] dim=160 x 269056552 usage=4105MB efficiency=69.91 Elapsed: 24.10s ctr=30093975536 partition=0b10111
part_a=[2] part_b=[5, 4, 3, 3] dim=180 x 219572928 usage=3350MB efficiency=76.14 Elapsed: 22.63s ctr=30093975536 partition=0b01111

# 2 ships in one partition - inner loop is smaller than outer
part_a=[3, 3, 2] part_b=[5, 4] dim=3848040 x 14400 usage=59MB efficiency=54.31 Elapsed: 26.79s ctr=30093975536 partition=0b00011
part_a=[4, 3, 2] part_b=[5, 3] dim=3237624 x 17040 usage=50MB efficiency=54.55 Elapsed: 26.62s ctr=30093975536 partition=0b00101
part_a=[4, 3, 3] part_b=[5, 2] dim=2735440 x 19840 usage=42MB efficiency=55.45 Elapsed: 26.54s ctr=30093975536 partition=0b10001
part_a=[5, 3, 2] part_b=[4, 3] dim=2667272 x 20336 usage=41MB efficiency=55.48 Elapsed: 26.39s ctr=30093975536 partition=0b01010
part_a=[5, 4, 2] part_b=[3, 3] dim=2216256 x 23768 usage=34MB efficiency=57.13 Elapsed: 25.94s ctr=30093975536 partition=0b01100
part_a=[5, 3, 3] part_b=[4, 2] dim=2239872 x 23532 usage=35MB efficiency=57.09 Elapsed: 25.74s ctr=30093975536 partition=0b10010
part_a=[5, 4, 3] part_b=[3, 2] dim=1850736 x 27336 usage=29MB efficiency=59.48 Elapsed: 24.63s ctr=30093975536 partition=0b11000

# 2 ships in one partition - outer loop is smaller than inner
part_a=[5, 4] part_b=[3, 3, 2] dim=14400 x 3848040 usage=59MB efficiency=54.31 Elapsed: 30.70s ctr=30093975536 partition=0b11100
part_a=[5, 3] part_b=[4, 3, 2] dim=17040 x 3237624 usage=50MB efficiency=54.55 Elapsed: 30.59s ctr=30093975536 partition=0b11010
part_a=[5, 2] part_b=[4, 3, 3] dim=19840 x 2735440 usage=42MB efficiency=55.45 Elapsed: 31.20s ctr=30093975536 partition=0b01110
part_a=[4, 3] part_b=[5, 3, 2] dim=20336 x 2667272 usage=41MB efficiency=55.48 Elapsed: 30.75s ctr=30093975536 partition=0b10101
part_a=[4, 2] part_b=[5, 3, 3] dim=23532 x 2239872 usage=35MB efficiency=57.09 Elapsed: 29.51s ctr=30093975536 partition=0b01101
part_a=[3, 3] part_b=[5, 4, 2] dim=23768 x 2216256 usage=34MB efficiency=57.13 Elapsed: 29.80s ctr=30093975536 partition=0b10011
part_a=[3, 2] part_b=[5, 4, 3] dim=27336 x 1850736 usage=29MB efficiency=59.48 Elapsed: 25.04s ctr=30093975536 partition=0b01011