Game of life CR request | Rust Programming Language Community | Page 1

slow heath Jul 20, 2024, 5:05 PM

#

Hi, I've created a simple game of life and I've a few questions.

https://github.com/stachujone5/game-of-life/blob/main/src/main.rs

get_row method - Why can't I return just an owned [bool] and instaed I've to return a reference?

    fn get_row(&self, index: usize) -> &[bool] {
        &self.cells[index * self.size..index * self.size + self.size]
    }

print method - I am getting a &bool inside a map. Can I somehow check if &bool is true? I didn't figure it out so I used to_owned()

.map(|v| if v.to_owned() { " # " } else { " . " })

Are there any major issues in my code when It comes to borrowing and references? I've a hard time understanding it.

GitHub

game-of-life/src/main.rs at main · stachujone5/game-of-life

Conway's game of life written in rust. Contribute to stachujone5/game-of-life development by creating an account on GitHub.

jade wadi Jul 20, 2024, 5:17 PM

#

Why can't I return just an owned [bool] and instaed I've to return a reference?
Because a [bool] is of variable size (the row length), and so it cannot be put in a register or the stack. The owned version that you can do that with is Vec<bool> or Box<[bool]>, which are both sorts of pointers which own [bool]s.

#

I am getting a &bool inside a map. Can I somehow check if &bool is true?
You should dereference it, which can be written any of these ways:

.map(|v| if *v { ...
.map(|&v| if v { ...
.copied().map(|v| if v { ...

#

Now as to review comments …

#

let mut neighbours: Vec<&bool> = Vec::new();

Vec<&bool> is an inefficient and restrictive format. You should keep a Vec<bool> instead, dereferencing as needed when you push things into it.

#

And to help with that...

    fn get_cell(&self, x: usize, y: usize) -> Option<&bool> {

change this to return Option<bool> instead.

#

There's almost no reason ever to use an &bool, or &i32 or &anything_small_and_copy.

#

You'll inevitably get them anyway from things like .iter(), but you should always dereference/copy at the earliest opportunity.

#

The optimizer can get rid of the unnecessary references in many cases, but it often can't if you specify a data structure that has them, like Vec<&bool> or Option<&bool>.

#

get_num_of_alive_neighbors could be expressed much more concisely by looping over a list of offsets. And there's no need to keep the Vec rather than just a sum.

let mut count = 0;
for dx in -1..=1 {
    for dy in -1..=1 {
        if self.get_cell(x + dx, y = dy) == Some(true) {
            count += 1;
        }
    }
}
count

#

create_next_generation can be more efficient if instead of creating a new Vec each time, you keep two Vecs in Board and swap them

#

std::mem::swap() can help with doing that.

#

Board::print() can be more flexible if you write it as a impl fmt::Display for Board, so a board can be printed anywhere not just stdout.

#

That's all my comments — the code is pretty clean other than these things! @slow heath

#

oh, create_next_generation will probably be a tad faster if you loop over y as the outer loop instead of x as the outer loop. that way you're doing one row at a time and thus accessing more adjacent elements in the Vec, which makes better use of CPU cache

slow heath Jul 20, 2024, 5:29 PM

#

Thanks, I'll have to dig more into references and I'll try to simplify some logic. I don't think I will go too much into performance as I am lacking the basics

jade wadi Jul 20, 2024, 5:30 PM

#

Everything you did with references was completely appropriate, except for the cases where you should have dereferenced sooner than you did.

obsidian zephyr Jul 20, 2024, 6:13 PM

#

Not much I can really add. kpreid's comments are all good.

Super minor nitpicks (take with a grain of salt):

Inside impl Board, consider moving get_row() to either immediately above or below get_cell() since they are related to each other.
In get_row(), consider adding some parentheses: &self.cells[(index * self.size)..((index * self.size) + self.size)]. They aren't needed and totally just a personal preference thing. For me, it's a whole lot easier to read when using a combination of a range and multiple variables.

Alternatively, you can combine get_row and get_cell like so:

fn cell(&self, x: usize, y: usize) -> Option<bool> {
    self.cells.get((y * self.size) + self.x)
}
```(This may theoretically be slower in some cases, if you're frequently accessing a "row" in sequential order; but profiling would be needed to know for sure. Might just get optimized out either way.)

slow heath Jul 20, 2024, 6:45 PM

#

obsidian zephyr Not much I can really add. kpreid's comments are all good. Super minor nitpicks...

Thank you 🙂

#

Is get copied appropriate here? Compiler wouldn't let me dereference Option<&bool>

   fn get_row(&self, index: usize) -> &[bool] {
        &self.cells[index * self.size..index * self.size + self.size]
    }

    fn get_cell(&self, x: usize, y: usize) -> Option<bool> {
        let row = self.get_row(y);

        row.get(x).copied()
    }

#

@jade wadi

obsidian zephyr Jul 20, 2024, 6:56 PM

#

Yes

slow heath Jul 20, 2024, 6:56 PM

#

obsidian zephyr Not much I can really add. kpreid's comments are all good. Super minor nitpicks...

I did not combine it because get_row is also used inside print method

#

so It didnt make sense to me

jade wadi Jul 20, 2024, 7:00 PM

#

also here's a trick for making get_row more concise, which applies any time you naturally have start and length instead of two endpoints: slice twice.

&self.cells[(index * self.size)..][..self.size]

#

I just noticed a stylistic or maybe correctness thing: it's inconsistent that get panics on y out of bounds (via get_row) but returns None on x out of bounds

#

either behavior makes sense, but a single operation should generally pick one, rather than half of one and half of the other

slow heath Jul 20, 2024, 7:04 PM

#

well I could make get_row return Option<&[bool]>

obsidian zephyr Jul 20, 2024, 7:21 PM

#

slow heath I did not combine it because get_row is also used inside print method

Fair. Though an alternative would be to use chunks and not use the get_* functions at all.

impl fmt::Display for Board {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.cells.chunks(self.size)
            .map(|row| row
                .into_iter()
                .map(|cell| if *cell { " # " } else { " . " })
                .collect::<String>())
            .map(|row| writeln!(f, "{row}"))
            .collect()
    }
}

slow heath Jul 20, 2024, 7:31 PM

#

jade wadi `get_num_of_alive_neighbors` could be expressed much more concisely by looping o...

btw I cannot add x (usize) to dx (i32)

#

Do I've to use into?

#

Also even if I cast those signed integeres into usize - wont it crash?

#

How could this cast be possible

obsidian zephyr Jul 20, 2024, 7:35 PM

#

Use x.wrapping_add_signed(dx)

#

And probably use isize instead of i32 in this case.

slow heath Jul 20, 2024, 7:50 PM

#

obsidian zephyr Use `x.wrapping_add_signed(dx)`

I am getting attempt to multiply with overflow with this code

#

    fn get_num_of_alive_neighbours(&self, x: usize, y: usize) -> usize {
        let mut count = 0;

        for dx in -1..1 {
            for dy in -1..1 {
                if self.get_cell(x.wrapping_add_signed(dx), y.wrapping_add_signed(dy)) == Some(true)
                {
                    count += 1;
                }
            }
        }

        count
    }

#

  fn get_row(&self, index: usize) -> Option<&[bool]> {
        self.cells
            .get(index * self.size..index * self.size + self.size)
    }

obsidian zephyr Jul 20, 2024, 7:51 PM

#

Which line is producing the error?

slow heath Jul 20, 2024, 7:51 PM

#

.get(index * self.size..index * self.size + self.size)

#

this one

#

but what could be overflowing there if all of these are usize

obsidian zephyr Jul 20, 2024, 7:51 PM

#

Oh right yeah

#

Double casting could work. Otherwise you need to use the checked_* variant and skip when None, like this:

        for dx in -1..1 {
            let Some(x) = x.checked_add_signed(dx) else { continue };
            for dy in -1..1 {
                let Some(y) = y.checked_add_signed(dy) else { continue };
                if self.get_cell(x, y) == Some(true) {
                    count += 1;
                }
            }
        }

slow heath Jul 20, 2024, 7:56 PM

#

Yeah that doesn't crash the program

#

thanks

slow heath Jul 20, 2024, 9:38 PM

#

Fixed all things above and added tests

#

Is there anything else?

#

https://github.com/stachujone5/game-of-life/blob/main/src/main.rs

GitHub

game-of-life/src/main.rs at main · stachujone5/game-of-life

Conway's game of life written in rust. Contribute to stachujone5/game-of-life development by creating an account on GitHub.

#

@obsidian zephyr @jade wadi

jade wadi Jul 20, 2024, 10:47 PM

#

Looks good. Another thing you could do (there's always one more thing…) is to have Board::new() take a &mut dyn rand::Rng instead of calling rand::random(). That way, you can create boards from a seed when you want to, instead of every one being uncontrollably random.

obsidian zephyr Jul 21, 2024, 1:09 AM

#

(there's always one more thing indeed...)

https://github.com/stachujone5/game-of-life/blob/main/src/main.rs#L46 This is a significant enough issue that you really should do what kpreid suggested earlier, at least to practice. Every new generation, you're making a new allocation. For this fairly simple/small program, it may not matter, but for large grids or if you ever expand a cell to contain more than just a bool, this will become quite costly.

To reiterate, create a new field inside Board with the same type as cells, let's call it next for example. Initial state of next doesn't matter. Inside create_next_generation(), remove lines 46 and 60, and use self.next instead of your old new_cells variable. At the end, instead of replacing the current collection, swap the contents of cells and next using std::mem::swap(&mut self.cells, &mut self.next);.

slow heath Jul 21, 2024, 10:30 AM

#

obsidian zephyr (there's always one more thing indeed...) <https://github.com/stachujone5/game-...

I've added it but I am not entirely sure how do you measure this perf. I wouldn't have thought of that ever.
Why exactly is storing a next in Board faster than creating and deallocating memory as before becuase I guess that's what was happening - whe cloned board.cells and then after this method was finished the memory was cleared?

#

When it comes to code - I've created the initial next as a new Vec<bool> filled with false because we do need it to be exactly same length on the initial iteration

obsidian zephyr Jul 21, 2024, 2:02 PM

#

slow heath I've added it but I am not entirely sure how do you measure this perf. I wouldn'...

Allocations can be (relatively) slow and unpredictable (in terms of speed). Reducing frequent allocations is often one of the first things to check for when looking to optimize a program, especially if the allocations are very large.

I'm uncertain how to write a fair performance test for this particular comparison. But the premise is that by keeping two allocations around, and swapping the Vecs, you are never needlessly allocating/initializing/deallocating anything.

When you perform the swap, the only data that is being copied is the length, capacity, and heap pointer of the two Vecs (all of which are on the stack). No initializing, no allocations.

slow heath Jul 21, 2024, 2:07 PM

#

obsidian zephyr Allocations can be (relatively) slow and unpredictable (in terms of speed). Redu...

Alright, thanks for CR guys I think I am done with the changes

#Game of life CR request