Skip to main content
Code Review

Return to Answer

added 2514 characters in body
Source Link
DobromirM
DobromirM
  • 1.1k
  • 5
  • 15

Performance:

After benchmarking the performance of the original implementation from the author and my new implementation, it is clear that the original modulus approach yields significantly slower performance on top of being more unreadable.

Experiment 1 parameters:
Grid - 100x100
Starting sate - Randomly generated (but same between the two methods)
Game steps - 1000

Experiment 1 average execution time:
Original implementation: 381.86 ms
New implementation: 162.13 ms

Experiment 2 parameters:
Grid - 10x10
Starting sate - Randomly generated (but same between the two methods)
Game steps - 10000

Experiment 2 average execution time:
Original implementation: 33.209 ms
New implementation: 14.175 ms

Additional information:

The library used for the benchmarking is criterion. And the raw data can be seen bellow.

game-of-life new impl, (100x100), random state, 1000 steps                                                                            
                        time:   [158.70 ms 162.13 ms 166.53 ms]
Found 7 outliers among 100 measurements (7.00%)
  2 (2.00%) high mild
  5 (5.00%) high severe

---------------------------------------------------------------------
game-of-life original impl, (100x100), random state, 1000 steps                                                                            
                        time:   [381.63 ms 381.86 ms 382.13 ms]
Found 6 outliers among 100 measurements (6.00%)
  2 (2.00%) low mild
  2 (2.00%) high mild
  2 (2.00%) high severe

--------------------------------------------------------------------
game-of-life new impl, (10x10), random state, 10000 steps                                                                            
                        time:   [13.847 ms 14.175 ms 14.580 ms]
Found 10 outliers among 100 measurements (10.00%)
  2 (2.00%) high mild
  8 (8.00%) high severe

---------------------------------------------------------------------
game-of-life original impl, (10x10), random state, 10000 steps                                                                            
                        time:   [33.176 ms 33.209 ms 33.247 ms]
Found 9 outliers among 100 measurements (9.00%)
  2 (2.00%) low mild
  4 (4.00%) high mild
  3 (3.00%) high severe

Performance:

After benchmarking the performance of the original implementation from the author and my new implementation, it is clear that the original modulus approach yields significantly slower performance on top of being more unreadable.

Experiment 1 parameters:
Grid - 100x100
Starting sate - Randomly generated (but same between the two methods)
Game steps - 1000

Experiment 1 average execution time:
Original implementation: 381.86 ms
New implementation: 162.13 ms

Experiment 2 parameters:
Grid - 10x10
Starting sate - Randomly generated (but same between the two methods)
Game steps - 10000

Experiment 2 average execution time:
Original implementation: 33.209 ms
New implementation: 14.175 ms

Additional information:

The library used for the benchmarking is criterion. And the raw data can be seen bellow.

game-of-life new impl, (100x100), random state, 1000 steps                                                                            
                        time:   [158.70 ms 162.13 ms 166.53 ms]
Found 7 outliers among 100 measurements (7.00%)
  2 (2.00%) high mild
  5 (5.00%) high severe

---------------------------------------------------------------------
game-of-life original impl, (100x100), random state, 1000 steps                                                                            
                        time:   [381.63 ms 381.86 ms 382.13 ms]
Found 6 outliers among 100 measurements (6.00%)
  2 (2.00%) low mild
  2 (2.00%) high mild
  2 (2.00%) high severe

--------------------------------------------------------------------
game-of-life new impl, (10x10), random state, 10000 steps                                                                            
                        time:   [13.847 ms 14.175 ms 14.580 ms]
Found 10 outliers among 100 measurements (10.00%)
  2 (2.00%) high mild
  8 (8.00%) high severe

---------------------------------------------------------------------
game-of-life original impl, (10x10), random state, 10000 steps                                                                            
                        time:   [33.176 ms 33.209 ms 33.247 ms]
Found 9 outliers among 100 measurements (9.00%)
  2 (2.00%) low mild
  4 (4.00%) high mild
  3 (3.00%) high severe
Source Link
DobromirM
DobromirM
  • 1.1k
  • 5
  • 15

Your solution looks good! I would suggest the following improvements in order to make it more readable:

Use type aliases to improve the readability:

type State = [[bool; WIDTH]; HEIGHT];

Extract the coordinate wrapping logic into its own type to make it easier to understand:

#[derive(Debug, Copy, Clone)]
struct Coord {
    value: usize,
    max: usize,
}

impl Coord {
    fn new(value: usize, max: usize) -> Self {
        Coord {
            value,
            max,
        }
    }

    fn increment(&mut self) {
        self.value += 1;

        if self.value >= self.max {
            self.value = 0;
        }
    }

    fn decrement(&mut self) {
        self.value = self.value.checked_sub(1).unwrap_or(self.max - 1);
    }
}

Create a Cell and NeighborsIter structures that encapsulate the logic of iterating over all neigbhours of a given cell:

#[derive(Debug, Copy, Clone)]
struct Cell {
    x: Coord,
    y: Coord,
}

impl Cell {
    fn new(x: usize, y: usize) -> Self {
        Cell {
            x: Coord::new(x, HEIGHT),
            y: Coord::new(y, WIDTH),
        }
    }

    fn into_neighbors_iter(self) -> NeighborsIter {
        NeighborsIter::new(self)
    }
}


struct NeighborsIter {
    state: usize,
    cell: Cell,
}

impl NeighborsIter {
    fn new(init: Cell) -> Self {
        Self {
            state: 0,
            cell: init,
        }
    }
}

impl Iterator for NeighborsIter {
    type Item = Cell;

    fn next(&mut self) -> Option<Self::Item> {
        match self.state {
            0 => {
                self.cell.x.decrement();
                self.cell.y.decrement()
            }
            1 => { self.cell.y.increment() }
            2 => { self.cell.y.increment() }
            3 => { self.cell.x.increment() }
            4 => { self.cell.x.increment() }
            5 => { self.cell.y.decrement() }
            6 => { self.cell.y.decrement() }
            7 => { self.cell.x.decrement() }
            _ => { return None; }
        }
        self.state += 1;
        Some(self.cell)
    }
}

Separate the counting of live neigbhors into its own function:

fn count_neighbors(&self, cell: Cell) -> u8 {
    let mut neighbours: u8 = 0;

    for cell in cell.into_neighbors_iter() {
        if self.state[cell.x.value][cell.y.value] {
            neighbours += 1;
        }
    }
    neighbours
}

Create a Board struct and move the next_step function into it as a method:

#[derive(Debug)]
struct Board {
    state: State
}

impl Board {
    pub fn new() -> Self {
        Board {
            state: [[false; WIDTH]; HEIGHT]
        }
    }

    pub fn from(state: State) -> Self {
        Board {
            state
        }
    }

    pub fn next_step(self) -> Board {
        let mut next_state = [[false; WIDTH]; HEIGHT];

        for row in 0..HEIGHT {
            for col in 0..WIDTH {
                match self.count_neighbors(Cell::new(row, col)) {
                    3 => next_state[row][col] = true,
                    2 if self.state[row][col] => next_state[row][col] = true,
                    _ => {}
                }
            }
        }
        Board {
            state: next_state
        }
    }

    fn count_neighbors(&self, cell: Cell) -> u8 {
        let mut neighbours: u8 = 0;

        for cell in cell.into_neighbors_iter() {
            if self.state[cell.x.value][cell.y.value] {
                neighbours += 1;
            }
        }
        neighbours
    }
}

Final Code:

const WIDTH: usize = 10;
const HEIGHT: usize = 10;

type State = [[bool; WIDTH]; HEIGHT];


#[derive(Debug, Copy, Clone)]
struct Coord {
    value: usize,
    max: usize,
}

impl Coord {
    fn new(value: usize, max: usize) -> Self {
        Coord {
            value,
            max,
        }
    }

    fn increment(&mut self) {
        self.value += 1;

        if self.value >= self.max {
            self.value = 0;
        }
    }

    fn decrement(&mut self) {
        self.value = self.value.checked_sub(1).unwrap_or(self.max - 1);
    }
}

#[derive(Debug, Copy, Clone)]
struct Cell {
    x: Coord,
    y: Coord,
}

impl Cell {
    fn new(x: usize, y: usize) -> Self {
        Cell {
            x: Coord::new(x, HEIGHT),
            y: Coord::new(y, WIDTH),
        }
    }

    fn into_neighbors_iter(self) -> NeighborsIter {
        NeighborsIter::new(self)
    }
}


struct NeighborsIter {
    state: usize,
    cell: Cell,
}

impl NeighborsIter {
    fn new(init: Cell) -> Self {
        Self {
            state: 0,
            cell: init,
        }
    }
}

impl Iterator for NeighborsIter {
    type Item = Cell;

    fn next(&mut self) -> Option<Self::Item> {
        match self.state {
            0 => {
                self.cell.x.decrement();
                self.cell.y.decrement()
            }
            1 => { self.cell.y.increment() }
            2 => { self.cell.y.increment() }
            3 => { self.cell.x.increment() }
            4 => { self.cell.x.increment() }
            5 => { self.cell.y.decrement() }
            6 => { self.cell.y.decrement() }
            7 => { self.cell.x.decrement() }
            _ => { return None; }
        }
        self.state += 1;
        Some(self.cell)
    }
}

#[derive(Debug)]
struct Board {
    state: State
}

impl Board {
    pub fn new() -> Self {
        Board {
            state: [[false; WIDTH]; HEIGHT]
        }
    }

    pub fn from(state: State) -> Self {
        Board {
            state
        }
    }

    pub fn next_step(self) -> Board {
        let mut next_state = [[false; WIDTH]; HEIGHT];

        for row in 0..HEIGHT {
            for col in 0..WIDTH {
                match self.count_neighbors(Cell::new(row, col)) {
                    3 => next_state[row][col] = true,
                    2 if self.state[row][col] => next_state[row][col] = true,
                    _ => {}
                }
            }
        }
        Board {
            state: next_state
        }
    }

    fn count_neighbors(&self, cell: Cell) -> u8 {
        let mut neighbours: u8 = 0;

        for cell in cell.into_neighbors_iter() {
            if self.state[cell.x.value][cell.y.value] {
                neighbours += 1;
            }
        }
        neighbours
    }
}