Zenn
Closed63

Rust習作: Conway's Game of Life

Rust
tech
MasakiMasaki

Rustでのプログラミングに慣れるために、習作としてライフゲーム(Conway's Game of Life)を作ってみることにした。

具体的な達成条件として、下記を考えている。条件は進めながら調整するかもしれない。

  • Rustの機能を適切に使う
    • 特に: 所有権、エラー処理、構造体とEnum、コレクション、トレイト、ジェネリック型、イテレータ、クロージャ、スマートポインタ、モジュールやクレート、などをRustの流儀にしたがって使用する (必要なければ無理に使うことはしないが)
  • Cargoの機能を適切に使う
  • テストを整備する
  • ドキュメントを整備する
  • パフォーマンスを測定する。また、それを用いながら実行時間短縮作業を行い、その作業フローを把握する
MasakiMasaki

まず、Conway's Game of Lifeについてざっと調べた。

Game of Lifeとして、下記を行えるようにしたい。

表示と操作は、最初は標準入出力によるシンプルなものから始める。これだけだと味気ないので、WasmとWebブラウザで扱えるとよいだろうか。

MasakiMasaki

開発ツールとして下記を使う。いずれも手元のDebian(bullseye (11.6) for amd64)の環境にインストール済み。

  • rustup 1.25.1
  • rustc 1.66.0
  • cargo 1.66.0
MasakiMasaki

RustとCargoでの標準的な開発スタイルにしたがい、cargo newから開始。

$ cargo new game-of-life
     Created binary (application) `game-of-life` package
$ cd game-of-life

生成された Cargo.toml は、下記のようになっていた。Rustのエディション指定は2021。そのまま使うことにする。

Cargo.toml
[package]
name = "game-of-life"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
MasakiMasaki

ライフゲームの本体を life というモジュールに実装しようとして、さっさくつまづいた。
src/ 内を下記の2ファイル構成にしたが:

src/life.rs
mod life;

pub struct Config {
    pub width: u16,
    pub height: u16,
}

impl Config {
    pub fn new(w: u16, h: u16) -> Config {
        let width = w;
        let height = h;
        Config { width, height }
    }
}
src/main.rs
use life::Config;

fn main() {
    let c = life::Config::new(10, 10);
    println!("Config: (width:{}, height:{})", c.width, c.height);
}

cargo check が通らず、下記のエラーになった。

$ cargo check
    Checking game-of-life v0.1.0 (.../game-of-life)
error[E0432]: unresolved import `life`
 --> src/main.rs:1:5
  |
1 | use life::Config;
  |     ^^^^ use of undeclared crate or module `life`

error[E0433]: failed to resolve: use of undeclared crate or module `life`
 --> src/main.rs:4:13
  |
4 |     let c = life::Config::new(10, 10);
  |             ^^^^ use of undeclared crate or module `life`

Some errors have detailed explanations: E0432, E0433.
For more information about an error, try `rustc --explain E0432`.
error: could not compile `game-of-life` due to 2 previous errors

mod と use の使い方の理解が浅いので、再確認。The Rust Programming Language 日本語版の7章と、Tour of RustのChapter 9を眺め直したが、知りたいのはモジュールやクレートの概要やサンプルではなくmodとuseの正確な定義だったので、The Rust Referenceの該当箇所を読んだ。下記のように理解した。

  • 6.1. Modules
    • mod IDENTIFIER;またはmod IDENTIFIER { ... }と記述すると、現在のモジュール内に IDENTIFIER モジュールが定義される
    • mod IDENTIFIER;と記述した場合は、IDENTIFIER モジュールの本体の記述は別のファイルから読み込まれる。対象のファイルは、モジュールパスにしたがって探索される。例えば下記のとおり
      • ライブラリクレートのrootモジュールのソースコードである src/lib.rs にて mod util; と記述すると、util モジュールの本体は src/util.rs から読み込まれる
      • 同様に、src/util.rs にて mod config; と記述すると、util/config モジュールの本体は src/util/config.rs から読み込まれる
  • 6.3. Use Declarations
    • use Path;やuse Path as IDENTIFIER;などと宣言すると、別のpathにある名前がローカルな名前の別名として扱われるようになる

上記を踏まえて、src/life.rs と src/main.rs を下記のように修正した。

src/life.rs
pub struct Config {
    pub width: u16,
    pub height: u16,
}

impl Config {
    pub fn new(w: u16, h: u16) -> Config {
        let width = w;
        let height = h;
        Config { width, height }
    }
}
src/main.rs
mod life;

fn main() {
    let c = life::Config::new(10, 10);
    println!("Config: (width:{}, height:{})", c.width, c.height);
}

cargo check や cargo run が通るようになった。

$ cargo run  
   Compiling game-of-life v0.1.0 (.../game-of-life)
    Finished dev [unoptimized + debuginfo] target(s) in 0.30s
     Running `target/debug/game-of-life`
Config: (width:10, height:10)
MasakiMasaki

下記のものを実装する。命名はライブゲームの用語にしたがう。

  • Universe: 2次元格子状の盤面
  • Cell: 盤面上の1つ1つの格子である「セル」。セルの状態は、「生」(alive)と「死」(dead)のいずれか

まず、盤面を作って標準出力に表示できるようにする。状態遷移はまだ作らない。
あれこれ試しながら書いて、下記のようにした。

src/life.rs
use std::fmt;

pub use u16 as BoardLengthType;

struct Board<T> {
    width: BoardLengthType,
    grids: Vec<T>,
}

impl<T: Clone + Copy> Board<T> {
    fn new(width: BoardLengthType, height: BoardLengthType, init: T) -> Self {
        let grids = vec![init; (width * height) as usize];
        Self { width, grids }
    }
    fn position_to_index(&self, x: BoardLengthType, y: BoardLengthType) -> usize {
        (y * self.width + x) as usize
    }
    fn width(&self) -> BoardLengthType {
        self.width
    }
    fn height(&self) -> BoardLengthType {
        (self.grids.len() / (self.width as usize)) as BoardLengthType
    }
    fn get_grid(&self, x: BoardLengthType, y: BoardLengthType) -> T {
        let idx = self.position_to_index(x, y);
        self.grids[idx]
    }
    fn set_grid(&mut self, x: BoardLengthType, y: BoardLengthType, v: T) {
        let idx = self.position_to_index(x, y);
        self.grids[idx] = v;
    }
}

#[derive(Clone, Copy, PartialEq)]
pub enum Cell {
    Dead,
    Alive,
}

pub struct Universe {
    board: Board<Cell>,
}

impl Universe {
    pub fn new(width: BoardLengthType, height: BoardLengthType) -> Self {
        Self { board: Board::new(width, height, Cell::Dead) }
    }
    pub fn width(&self) -> BoardLengthType {
        self.board.width()
    }
    pub fn height(&self) -> BoardLengthType {
        self.board.height()
    }
    pub fn get_cell(&self, x: BoardLengthType, y: BoardLengthType) -> Cell {
        self.board.get_grid(x, y)
    }
    pub fn set_cell(&mut self, x: BoardLengthType, y: BoardLengthType, v: Cell) {
        self.board.set_grid(x, y, v);
    }
}

impl fmt::Display for Universe {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for y in 0..self.height() {
            let line = (0..self.width())
                .map(|x| {
                    if self.get_cell(x, y) == Cell::Dead { '.' } else { 'O' }
                })
                .collect::<String>();
            writeln!(f, "{}", line)?;
        }
        Ok(())
    }
}
src/main.rs
mod life;
use life::{Cell, Universe};

fn main() {
    let width = 5;
    let height = 5;
    let mut universe = Universe::new(width, height);
    universe.set_cell(2, 1, Cell::Alive);
    universe.set_cell(3, 2, Cell::Alive);
    universe.set_cell(1, 3, Cell::Alive);
    universe.set_cell(2, 3, Cell::Alive);
    universe.set_cell(3, 3, Cell::Alive);
    print!("{}", universe.to_string());
}

これを実行すると、下記のように標準出力にグライダーが表示される。(パターンはmain関数内にベタ書きではあるが)

$ cargo run
   Compiling game-of-life v0.1.0 (.../game-of-life)
    Finished dev [unoptimized + debuginfo] target(s) in 0.60s
     Running `target/debug/game-of-life`
.....
..O..
...O.
.OOO.
.....

実装に関する覚え書きは下記。

  • 設計意図として
    • 盤面のデータ表現の実装詳細はBoardに、モジュール外に開示する仕様はUniverseに分けた。実装詳細を変更する際にはBoardだけを更新すればよい
  • Rustとして
    • Boardは、格納する値を型引数Tに取るようにした
    • Boardの型引数Tには、トレイト境界としてCloneとCopyを付けた。必要な箇所は:
    • Boardの座標の型も外から与えられるようにしたかったが、トレイト境界の指定が複雑だったため、ひとまず見送った
    • Cellには、トレイト境界としてPartialEqを付けた。等価判定を行う箇所があるため
    • 数値同士の暗黙の型変換は基本的に行われないため(詳細は未確認)、u16とusize同士の型変換は明示する必要がある
    • Universeのto_stringの実装には、イテレータ・map・collectのイディオムを使った (座標値をイテレータにしてもしょうがないという感じはするが)
MasakiMasaki

Universeに状態遷移の機能を追加した。追加したのは下記の3関数で、それ以外のsrc/life.rsには変更なし。

src/life.rs
impl Universe {
    ...
    fn count_neighbour(&self, x: BoardLengthType, y: BoardLengthType) -> usize {
        let decr_round = |v, bound| if v > 0 { v - 1 } else { bound - 1 };
        let incr_round = |v, bound| if v + 1 < bound { v + 1 } else { 0 };
        let width = self.width();
        let height = self.height();
        let west = decr_round(x, width);
        let east = incr_round(x, width);
        let north = decr_round(y, height);
        let south = incr_round(y, height);
        let pos_list = [
            (west, north),
            (x, north),
            (east, north),
            (west, y),
            (east, y),
            (west, south),
            (x, south),
            (east, south)
        ];
        let count = pos_list.iter()
            .map(|&(pos_x, pos_y)| self.get_cell(pos_x, pos_y) )
            .filter(|&v| v == Cell::Alive )
            .count();
        count
    }
    pub fn next(&self) -> Self {
        let next_cell_rule = |current_cell, neighbour_count: usize| -> Cell {
            match (current_cell, neighbour_count) {
                (Cell::Alive, 2) => Cell::Alive,
                (Cell::Alive, 3) => Cell::Alive,
                (Cell::Dead, 3) => Cell::Alive,
                _ => Cell::Dead,
            }
        };
        let width = self.width();
        let height = self.height();
        let mut next_universe = Self::new(width, height);
        for y in 0..height {
            for x in 0..width {
                let cell = self.get_cell(x, y);
                let count = self.count_neighbour(x, y);
                let next_cell = next_cell_rule(cell, count);
                next_universe.set_cell(x, y, next_cell);
            }
        }
        next_universe
    }
    pub fn update(&mut self) {
        *self = self.next();
    }
}

src/main.rsを下記のものへと差し替えて、グライダーを4回状態遷移させるようにした。

src/main.rs
mod life;
use life::{Cell, Universe};

fn main() {
    let width = 6;
    let height = 6;
    let mut universe = Universe::new(width, height);
    for (x, y) in [(2, 1), (3, 2), (1, 3), (2, 3), (3, 3)] {
        universe.set_cell(x, y, Cell::Alive);
    }
    println!("{}", universe.to_string());
    let times = 4;
    for _ in 0..times {
        universe.update();
        println!("{}", universe.to_string());
    }
}

実行結果は下記のとおり。グライダーが右下に進んでおり、正しく動作している。

% cargo run
   Compiling game-of-life v0.1.0 (.../game-of-life)
    Finished dev [unoptimized + debuginfo] target(s) in 0.64s
     Running `target/debug/game-of-life`
......
..O...
...O..
.OOO..
......
......

......
......
.O.O..
..OO..
..O...
......

......
......
...O..
.O.O..
..OO..
......

......
......
..O...
...OO.
..OO..
......

......
......
...O..
....O.
..OOO.
......

実装に関する覚え書きは下記。

MasakiMasaki

ライフゲーム用の2種類のパターンファイルフォーマット: Plaintext(.cells)とRun Length Encoded(.rle)を読み込めるようにしようと思い、下記のようなloadという関数を書き始めた。...となっている箇所は未実装。

src/life.rs
impl Universe {
    pub fn load(path: &std::path::Path) -> Result<Self, Box<dyn std::error::Error>> {
        let ext = path.extension().ok_or_else(|| ...)?;
        match ext {
            "cells" => Self::load_cells(path),
            "rle" => Self::load_rle(path),
            _ => Err(...),
        }
    }
    pub fn load_cells(path: &std::path::Path) -> Result<Self, Box<dyn std::error::Error>> { ... }
    pub fn load_rle(path: &std::path::Path) -> Result<Self, Box<dyn std::error::Error>> { ... }
}

いろいろと調べて、下記までは理解したつもりでいる。

  • load関数の引数には、std::path::Pathを使えばよいと思っている
  • 同じく戻り値には、The Rust Programming Language 日本語版の12章のrun関数からエラーを返すやRust By Example日本語版のエラーをBoxにするを参考にして、Box<dyn std::error::Error>型を使えばよいと思っている。こうすることで、下記を満たせる
    • 戻り値の型がBox<dyn std::error::Error>なので、std::error::Errorトレイトを実装していればどんな型の値でも返せる
    • std::fsのFile::openなどのファイル入出力関数は、エラーをstd::error::Errorトレイトとして返してくれる
    • プログラマが定義したエラーを返したい場合には、std::error::Errorトレイトを実装した型を定義して使えばよい
  • Path::extension()の戻り値などのようなOption型をResult型に変換するには、.ok_or_else(|| ...)を使うとよい
    • ok_or_elseは、Option<T>をResult<T, E>へと変換する
    • ok_orもok_or_elseと同様にOption<T>をResult<T, E>へと変換するが、ok_orはeager(即時評価)、ok_or_elseはlazy(遅延評価)である。エラー発生時にしかエラー生成を実行したくないなら、ok_or_elseのほうを使うとよい

が、プログラマが独自にエラーを定義する定番の方法は、いろいろと変遷があるようだ。下記を眺めているところ。

現在だと、anyhowを使うのが定番らしい。

MasakiMasaki

anyhowを使うため、cargo addにてCargo.tomlにanyhowを追加した。

$ cargo add anyhow
    Updating crates.io index
      Adding anyhow v1.0.68 to dependencies.
             Features:
             + std
             - backtrace
$ cat Cargo.toml 
[package]
name = "game-of-life"
version = "0.1.0"
edition = "2021"

[dependencies]
anyhow = "1.0.68"

load関数を下記のように実装した。ローダー本体であるload_cells関数とload_rle関数は未実装だが、拡張子による場合分けまでは意図どおり動作するようになった。

src/life.rs
use std::path::Path;
use anyhow::{Result, anyhow};

...

impl Universe {
    ...
    pub fn load(path: &Path) -> Result<Self> {
        let ext = path.extension().ok_or_else(|| anyhow!("\"{}\" has no extension", path.display()))?;
        if ext == "cells" {
            Self::load_cells(path)
        } else if ext == "rle" {
            Self::load_rle(path)
        } else {
            Err(anyhow!("\"{}\" has unknown extension", path.display()))
        }
    }
    pub fn load_cells(path: &Path) -> Result<Self> {
        Err(anyhow!("loader for \".cells\" is not implemented yet"))
    }
    pub fn load_rle(path: &Path) -> Result<Self> {
        Err(anyhow!("loader for \".rle\" is not implemented yet"))
    }}

使っているanyhowの機能は下記の2つのみ。

  • use anyhow::Resultとし、無指定で使えるstd::result::Resultではなくanyhow::Resultを使うようにした
  • プログラマとして定義したいエラーは、エラーメッセージを1つ持つエラーだけなので、そのエラー生成箇所すべてにanyhow!を使うようにした

それ以外のメモは下記のとおり。

MasakiMasaki

Plaintext(.cells)用のローダー関数load_cellsを実装した。ソースコードは下記のとおりで、ひとまず動けばよいというレベルのもの。

src/life.rs
use std::fs::read_to_string;
use std::path::Path;
use anyhow::{Result, anyhow};

impl Universe {
    ...
    pub fn load_cells(path: &Path) -> Result<Self> {
        let contents = read_to_string(path)?;
        let mut width = 0;
        let mut height = 0;
        let lines = contents.lines()
            .map(|line| line.trim())
            .filter(|line| match line.chars().nth(0) {
                Some('!') | None => false,
                _ => true,
            })
            .inspect(|line| {
                width = std::cmp::max(width, line.len());
                height += 1;
            })
            .collect::<Vec<_>>();
        if width > BoardLengthType::MAX as usize { return Err(anyhow!("\"{}\" contains too wide line", path.display())) }
        if height > BoardLengthType::MAX as usize { return Err(anyhow!("\"{}\" contains too much lines", path.display())) }
        let width = width as BoardLengthType;
        let height = height as BoardLengthType;
        let mut s = Self::new(width, height);
        for (y, line) in lines.iter().enumerate() {
            for (x, c) in line.chars().enumerate() {
                let cell = match c {
                    '.' => Cell::Dead,
                    'O' => Cell::Alive,
                    _ => return Err(anyhow!("\"{}\" contains wrong character '{}'", path.display(), c)),
                };
                s.set_cell(x as BoardLengthType, y as BoardLengthType, cell);
            }
        }
        Ok(s)
    }
}

src/main.rsを下記のものへと差し替えて、.cellsパターンファイルを与えて実行できるようにした。src/life.rsと同様に、いまいちこなれた記述になっていない感触がある。

src/main.rs
use std::process::ExitCode;
use std::path::Path;
use anyhow::{Result, anyhow};

mod life;
use life::Universe;

fn main() -> ExitCode {
    if let Err(e) = run(std::env::args()) {
        eprintln!("{}", e);
        ExitCode::FAILURE
    } else {
        ExitCode::SUCCESS
    }
}

fn run(mut args: std::env::Args) -> Result<()> {
    let path_str = match args.nth(1) {
        Some(s) => s,
        None => return Err(anyhow!("Not enough arguments")),
    };
    let universe = Universe::load(Path::new(&path_str))?;
    let times = match args.next() {
        Some(s) => match s.parse() {
            Ok(n) => n,
            Err(_) => return Err(anyhow!("2nd argument is not a number")),
        },
        None => 0,
    };
    simulate(universe, times);
    Ok(())
}

fn simulate(mut universe: Universe, times: usize) {
    for i in 0..=times {
        if i != 0 { universe.update(); }
        println!("Time = {}", i);
        println!("{}", universe.to_string());
    }
}

メモは下記のとおり。

  • load_cellsの処理の流れ
    • std::fs::read_to_stringを使い、ファイルの全内容を文字列に格納する
    • ファイル内容を収めた文字列contentsに対する1回目のスキャンで、行ごとの前後の空白の読み飛ばし・コメント行と空行の読み飛ばし・widthとheightの更新を行う
    • 2回目のスキャンで、セルを順に盤面に書き込む
  • 動いてはいるがいまいちな点
    • ファイルの内容全体を収められるだけのメモリを必要とする
    • 最初のファイル読み込みを含めると、ファイル内容を3回スキャンしている
    • inspect内でコンビネータ外の変数を更新している
    • run関数内にmatch・Some・None・Ok・Errなどが明示的に使われている。もう少しスマートに書けそう
  • Rustに関するメモ
    • イテレータ+コンビネータの文脈内では、早期リターンは行えない (おそらくOptionやResultをうまく使えばよい)
    • 手元の環境ではlet-else文を使えるが、Rust 1.65.0(2022-11-03)からのサポートだということなので、使わないでおいた

Gospeのグライダー銃のパターンファイルgosperglidergun.cellsを与えて1ステップ実行すると、下記のようになる。

$ cat gosperglidergun.cells
!Name: Gosper glider gun
!Author: Bill Gosper
!The first known gun and the first known finite pattern with unbounded growth.
!www.conwaylife.com/wiki/index.php?title=Gosper_glider_gun
........................O
......................O.O
............OO......OO............OO
...........O...O....OO............OO
OO........O.....O...OO
OO........O...O.OO....O.O
..........O.....O.......O
...........O...O
............OO
$ cargo run gosperglidergun.cells 2
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/game-of-life gosperglidergun.cells 2`
Time = 0
........................O...........
......................O.O...........
............OO......OO............OO
...........O...O....OO............OO
OO........O.....O...OO..............
OO........O...O.OO....O.O...........
..........O.....O.......O...........
...........O...O....................
............OO......................

Time = 1
.......................O............
.....................O.O............
............O.......O.O...........OO
...........OO......O..O...........O.
.O........OO....OO..O.O.............
OO.......OOO....OO...O.O............
..........OO....OO.....O............
...........OO.......................
............O.......................

Time = 2
......................O.............
.....................O.O............
...........OO.......O.OO..........OO
..........O.O......OO.OO..........OO
OO.......O......OOO.O.OO............
OO.......O..O..O..O..O.O............
.........O......OO....O.............
..........O.O.......................
...........OO.......................

パターンファイルの読み込みはOK。

状態遷移は、ルールどおりに動作はしているものの、上下端・左右端が干渉してしまっている。盤面末端処理がTorus固定で、パターンファイルのサイズをそのまま盤面サイズとしていることによるもの。そのうち何とかしよう。

MasakiMasaki

Rustでファイルの入出力の1行ずつ文字列を読み込みたいを参考に、load_cellsを下記のように更新した。

src/life.rs
use std::path::Path;
use std::fs::File;
use std::io::{BufRead, BufReader};
use anyhow::{Result, anyhow};

impl Universe {
    ...
    pub fn load_cells(path: &Path) -> Result<Self> {
        let mut alive_cells = Vec::new();
        let mut width: BoardLengthType = 0;
        let mut height: BoardLengthType = 0;
        for line in BufReader::new(File::open(path)?).lines() {
            let line = line?;
            let line = line.trim();
            match line.chars().next() {
                Some('!') | None => continue,
                _ => (),
            }
            if height == BoardLengthType::MAX { return Err(anyhow!("\"{}\" contains too much lines", path.display())) }
            let line_width = line.len();
            if line_width > BoardLengthType::MAX as usize { return Err(anyhow!("\"{}\" contains too wide line", path.display())) }
            for (x, c) in line.chars().enumerate() {
                match c {
                    '.' => (),
                    'O' => alive_cells.push((x as BoardLengthType, height)),
                    _ => return Err(anyhow!("\"{}\" contains wrong character '{}'", path.display(), c)),
                }
            }
            width = std::cmp::max(width, line_width as BoardLengthType);
            height += 1;
        }
        let mut s = Self::new(width, height);
        for &(x, y) in alive_cells.iter() {
            s.set_cell(x, y, Cell::Alive);
        }
        Ok(s)
    }
}

この変更により、下記のような処理方法になった。

  • ファイルの読み込みは、std::io::BufReaderによってラインバッファ単位で行われる。ファイルの内容全体を収められるだけのメモリは不要になった
  • ファイル内容のスキャンは1回のみになった
  • ファイル内容全体は保持しないが、代わりにVecで盤面全体のすべての生存セルの座標情報を保持する (こういった保持なしで盤面を作れるようにはなっていない。これをするにはBoardも変更が必要)
  • イテレータ+コンビネータではなくforループを使う。エラーがあれば、その場で早期リターンする
MasakiMasaki

Run Length Encoded(.rle)用のローダー関数load_rleを実装した。

src/life.rs
impl Universe {
    ...
    pub fn load_rle(path: &Path) -> Result<Self> {
        let parse_header = |line: &str| {
            let mut width: Option<BoardLengthType> = None;
            let mut height: Option<BoardLengthType> = None;
            for s in line.split(',') {
                let (name, val_str) = match s.find('=') {
                    Some(separator_pos) => {
                        (s[..separator_pos].trim(), s[(separator_pos + 1)..].trim())
                    },
                    None => return None,
                };
                match name {
                    "x" => width = val_str.parse().ok(),
                    "y" => height = val_str.parse().ok(),
                    "rule" => (),
                    _ => return None,
                }
            }
            match (width, height) {
                (Some(w), Some(h)) => Some((w, h)),
                _ => None,
            }
        };
        let mut header_done = false;
        let mut width: BoardLengthType = 0;
        let mut height: BoardLengthType = 0;
        let mut alive_cells = Vec::new();
        let mut x: BoardLengthType = 0;
        let mut y: BoardLengthType = 0;
        'outer: for line in BufReader::new(File::open(path)?).lines() {
            let line = line?;
            match line.chars().nth(0) {
                Some('#') | None => continue,
                _ => (),
            }
            if !header_done {
                match parse_header(&line) {
                    Some((w, h)) => { width = w; height = h; },
                    None => return Err(anyhow!("The header line of \"{}\" is in wrong format", path.display())),
                }
                header_done = true;
                continue;
            }
            let mut tags = line.as_str();
            loop {
                tags = tags.trim_start();
                let run_count = match tags.chars().nth(0) {
                    Some(c) if c.is_ascii_digit() => {
                        let (num_str, rest) = tags.split_at(tags.find(|c: char| !c.is_ascii_digit()).unwrap_or(tags.len()));
                        let num: BoardLengthType = num_str.parse().unwrap_or_default();
                        if num > width { return Err(anyhow!("run_count in the pattern exceeds width")); }
                        tags = rest;
                        Some(num)
                    },
                    _ => None,
                };
                let tag = match tags.chars().nth(0) {
                    Some(c) => {
                        tags = &tags[1..];
                        c
                    },
                    None => {
                        if run_count.is_none() {
                            break;
                        } else {
                            return Err(anyhow!("the pattern is in wrong format"));
                        }
                    },
                };
                let run_count = run_count.unwrap_or(1);
                match tag {
                    '!' => break 'outer,
                    '$' => {
                        x = 0;
                        y += 1;
                        if y >= height { return Err(anyhow!("number of lines in the pattern exceeds height")); }
                    },
                    'b' | 'o' => {
                        if x > width - run_count { return Err(anyhow!("x coordinate value in the pattern exceeds width")); }
                        if tag == 'o' {
                            for pos in (0..run_count).map(|i| (x + i, y)) { alive_cells.push(pos) }
                        }
                        x += run_count;
                    },
                    _ => return Err(anyhow!("the pattern is in wrong format")),
                }
            }
        }
        Ok(Self::new_with_alive_cells(width, height, alive_cells))
    }
    fn new_with_alive_cells(width: BoardLengthType, height: BoardLengthType, alive_cells: Vec<(BoardLengthType, BoardLengthType)>) -> Self {
        let mut s = Self::new(width, height);
        for &(x, y) in alive_cells.iter() {
            s.set_cell(x, y, Cell::Alive);
        }
        s
    }
}

見てのとおりのベタ書きではあるが、下記のように意図どおり動作した。使用したパターンファイルは、LifeWikiのgosperglidergun.rle。

$ cat gosperglidergun.rle
#N Gosper glider gun
#O Bill Gosper
#C A true period 30 glider gun.
#C The first known gun and the first known finite pattern with unbounded growth.
#C www.conwaylife.com/wiki/index.php?title=Gosper_glider_gun
x = 36, y = 9, rule = B3/S23
24bo11b$22bobo11b$12b2o6b2o12b2o$11bo3bo4b2o12b2o$2o8bo5bo3b2o14b$2o8b
o3bob2o4bobo11b$10bo5bo7bo11b$11bo3bo20b$12b2o!
$ cargo run gosperglidergun.rle
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/game-of-life gosperglidergun.rle`
Time = 0
........................O...........
......................O.O...........
............OO......OO............OO
...........O...O....OO............OO
OO........O.....O...OO..............
OO........O...O.OO....O.O...........
..........O.....O.......O...........
...........O...O....................
............OO......................

メモは下記のとおり。

  • load_rleの処理の流れ
    • 基本の処理は、下記の2重ループにて行う
      • 外側のループでは、ファイルを1行ずつ読み込む
      • 内側のループでは、ファイルの各行の文字を先頭から順に読み取って処理する
      • 書式エラーがあれば早期リターンする
    • 2重ループの外側に下記の状態を可変変数として保持し、それらを更新しながら処理する
      • ヘッダを読み終わったかどうかのフラグ (header_done)
      • 盤面のサイズ (width, height)
      • 現在のセル配置を行っている位置 (x, y)
      • Aliveセルを置くべき位置情報をすべて蓄積したもの (alive_cells)
    • ヘッダを読み取る処理はparse_headerにまとめている
  • 動いてはいるがいまいちな点
    • ヘッダはコメントを除いた最初の行と決まっているのに、ヘッダを読んだかどうかを可変変数で管理している。ヘッダを読んでから残りを読むという構造をコードで表現し、この変数を使わないようにしたい
    • ループ外に多数の可変変数を置いて、ループ内で書き換えながら処理している
  • ほか
    • ちゃんとpanic!を排除できているのか自信がない
    • matchを多用している。もっと簡潔に書ける箇所が多そう
MasakiMasaki

ライフゲームとして動作するようになったので、ソースコード全体の構造を整頓した。

src/ 内は main.rs と life.rs の2ファイル構成だったが、下記の2つの課題があったため:

  • life.rs が大きい
  • main.rs 内のmain関数のコード量がやや多い

src/ 内のソースコードを下記のようにモジュール分割した。

  • main.rs
  • app.rs
  • life.rs
  • life/board.rs
  • life/universe.rs
  • life/load_cells.rs
  • life/load_rle.rs

main.rsは下記のとおりの簡潔なものにした。
ほぼすべての責務を app::run() -> Result<()> に移譲し、エラー表示と実行結果の取り扱いだけを担う。

src/main.rs
mod app;
mod life;
use std::process::ExitCode;

fn main() -> ExitCode {
    if let Err(e) = app::run() {
        eprintln!("{}", e);
        ExitCode::FAILURE
    } else {
        ExitCode::SUCCESS
    }
}

app::run() を含むapp.rsは下記のとおり。
いろいろベタ書きなのはいまいちだが、責務の分離としてはおおよそよいように思っている。

src/app.rs
use crate::life::BoardLengthType;
use crate::life::Universe;
use anyhow::{anyhow, Result};
use std::path::Path;

pub struct Config {
    path_str: String,
    border_width: BoardLengthType,
    step_size: usize,
    times: usize,
}

impl Config {
    fn new(mut args: std::env::Args) -> Result<Self> {
        args.next();
        let Some(path_str) = args.next() else {
            return Err(anyhow!("Not enough arguments"));
        };
        let border_width = match args.next() {
            Some(s) => match s.parse() {
                Ok(n) => n,
                Err(_) => return Err(anyhow!("2nd argument is not a number")),
            },
            None => 0,
        };
        let step_size = match args.next() {
            Some(s) => match s.parse() {
                Ok(n) => n,
                Err(_) => return Err(anyhow!("3rd argument is not a number")),
            },
            None => 0,
        };
        let times = match args.next() {
            Some(s) => match s.parse() {
                Ok(n) => n,
                Err(_) => return Err(anyhow!("4th argument is not a number")),
            },
            None => 0,
        };
        Ok(Self {
            path_str,
            border_width,
            step_size,
            times,
        })
    }
}

pub fn run() -> Result<()> {
    let args = std::env::args();
    let config = Config::new(args)?;
    let path = Path::new(&config.path_str);
    let universe = bordered_universe(Universe::load(path)?, config.border_width);
    simulate(universe, config.step_size, config.times);
    Ok(())
}

fn bordered_universe(base: Universe, border_width: BoardLengthType) -> Universe {
    let mut bordered = Universe::new(base.width() + border_width * 2, base.height() + border_width * 2);
    for y in 0..base.height() {
        for x in 0..base.width() {
            bordered.set_cell(x + border_width, y + border_width, base.get_cell(x, y));
        }
    }
    bordered
}

fn simulate(mut universe: Universe, step_size: usize, times: usize) {
    for i in 0..=times {
        if i != 0 {
            for _ in 0..step_size {
                universe.update();
            }
        }
        println!("Generation = {}", i * step_size);
        println!("{}", universe);
    }
}

life.rsは下記のとおり。src/life/ 内の他の *.rs ファイルをプライベートモジュールとして読み込み、それらのモジュールで定義されたパスをpub useを使ってcrate::lifeに持ち込むことのみ行う。

src/life.rs
mod board;
mod load_cells;
mod load_rle;
mod universe;

pub use board::Board;
pub use board::LengthType as BoardLengthType;
pub use load_cells::load_cells;
pub use load_rle::load_rle;
pub use universe::Cell;
pub use universe::Universe;

src/life/ 内の他の *.rs ファイルは、これまでのものとほとんど同一。

MasakiMasaki

現時点のコマンドライン引数の与え方は次のとおり。

  • 第1引数(必須): パターンファイル名
  • 第2引数(任意): パターンの周囲に設ける余白セル数 (省略時は0)
  • 第3引数(任意): 1回の状態表示で進める世代の数 (省略時は1)
  • 第4引数(任意): 表示する状態の数。ただし初期状態は数に含まない (省略時は0)

動作させると、例えば下記のようになる。

グライダーを第4世代まで1世代ずつ表示。

$ cargo run glider.rle 2 1 4
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/game-of-life glider.rle 2 1 4`
Generation = 0
.......
.......
...O...
....O..
..OOO..
.......
.......

Generation = 1
.......
.......
.......
..O.O..
...OO..
...O...
.......

Generation = 2
.......
.......
.......
....O..
..O.O..
...OO..
.......

Generation = 3
.......
.......
.......
...O...
....OO.
...OO..
.......

Generation = 4
.......
.......
.......
....O..
.....O.
...OOO.
.......

Pi-heptominoが安定に至る第173世代を表示。

$ cargo run piheptomino.rle 23 173 1
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/game-of-life piheptomino.rle 23 173 1`
Generation = 0
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.......................OOO.......................
.......................O.O.......................
.......................O.O.......................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................

Generation = 173
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
........................O........................
........................O........................
........................O........................
.......OO...............................OO.......
.......OO...............................OO.......
...........OO.......................OO...........
...........OO.......................OO...........
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.OOO.........................................OOO.
.................................................
.....O.....................................O.....
.....O.....................................O.....
.....O.....................................O.....
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
........OO.............................OO........
.......O..O........OO.......OO........O..O.......
.......O..O........OO.......OO........O..O.......
........OO.............................OO........
.................................................
.................................................
.................................................
.................................................
.................................................
.................................................
MasakiMasaki

Rust/AnyhowのTipsを参考に、下記の置き換えを行った。

  • return Err(anyhow!("..."));ではなくbail!("...");を使う
  • if !cond { return Err(anyhow!("...")); }ではなくensure!(cond, "...");を使う
MasakiMasaki

clippyのバージョンを0.1.67 (2023-01-24)に上げたら、println!("{}", v)に警告が出るようになった。println!("{v}")に書き換えた。

MasakiMasaki

現時点の実装の実行速度を測定する。

測定にあたり、ある程度周期の長いパターンを探してきた。LifeWikiのOscillatorのページにImportant oscillators by periodという一覧表があったので、周期が100のMold on 30P25(moldon30p25.rle)を選んだ。

測定の前に、第0世代と第100世代が同一パターンになっていることを確認。

% cargo run patterns/moldon30p25.rle 1 100 1
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `target/debug/game-of-life patterns/moldon30p25.rle 1 100 1`
Generation = 0
......................
...................OO.
...................O..
.................O.O..
...........O..O..OO...
...........O..O.......
..........O....O......
..............O.......
...........OO.O.......
......................
......................
......................
......................
.......O.OO...........
.......O..............
......O....O..........
.......O..O......OOO..
...OO..O..O....O.OOO..
..O.O.........O.O.O...
..O...........O..O....
.OO............OO.....
......................
   
Generation = 100
......................
...................OO.
...................O..
.................O.O..
...........O..O..OO...
...........O..O.......
..........O....O......
..............O.......
...........OO.O.......
......................
......................
......................
......................
.......O.OO...........
.......O..............
......O....O..........
.......O..O......OOO..
...OO..O..O....O.OOO..
..O.O.........O.O.O...
..O...........O..O....
.OO............OO.....
......................

リリースプロファイルにてビルド。(Cargo.tomlにはプロファイルの設定を何も書いていない状態。参考: Profiles - The Cargo Book)

$ cargo build --release
   Compiling anyhow v1.0.68
   Compiling game-of-life v0.1.0 (.../game-of-life)
    Finished release [optimized] target(s) in 2.37s

まずはシンプルに、timeコマンドで総実行時間を測定。世代は、第0世代から第1,000,000世代までとした。

$ time cargo run --release patterns/moldon30p25.rle 1 1000000 1
    Finished release [optimized] target(s) in 0.00s
     Running `target/release/game-of-life patterns/moldon30p25.rle 1 1000000 1`
Generation = 0
...

Generation = 1000000
...

cargo run --release patterns/moldon30p25.rle 1 1000000 1  3.84s user 0.00s system 99% cpu 3.842 total

1,000,000世代の状態遷移に要する時間が3.84秒なので、手元の開発環境では、1世代分の状態遷移に要する時間は3.84マイクロ秒とわかった。

MasakiMasaki

続いて、プロファイラを使って実行時間の内訳を眺める。あれこれ様子見したところ、下記の2つが扱いやすそうだった。

  • cargo-flamegraph
    • オリジナルのFlame GraphsをRustに移植したものらしい (詳細は調べていない)
    • プロファイルデータ取得手段として以下のいずれかを必要とする、とのこと。オリジナルの方はもっと選択肢が多いように見える
      • Linuxのperf_event機能
      • macOSのDTrace機能
    • cargoに組み込まれるので、手短に使えることが利点
  • ValgrindのCallgrind
    • Valgrindは、実行可能バイナリを仮想マシン上で実行することで様々な解析を行うツールのフレームワーク。そのうちのCallgrindは、コールグラフを生成するツール
    • Valgrindは実行可能バイナリを与えれば動作するので、Rustプログラムに対しても使える

探している際に下記も見たが、試さなかった。

  • cargo-valgrind
    • Valgrindの名前が入っているが、説明文に "safe Rust codeには不要" "FFIを使うときのためのもの" などとあるので、実行時間内訳の測定に使うものではなさそう
  • cargo-profile
    • flamegraphなどをさらにサブコマンドにまとめたものか?
MasakiMasaki

cargo-flamegraphを使って実行時間内訳を測定した。

手元の環境はLinux Debianなので、perfをインストールした。また、/proc/sys/kernel/perf_event_paranoid が 3 以上だと測定ができないので、2に設定した。

$ sudo apt install linux-perf-5.10
...
$ echo 2 | sudo tee /proc/sys/kernel/perf_event_paranoid

cargo-flamegraph本体をインストール。

$ cargo install flamegraph
...

flamegraphやValgrindで実行時間内訳を見る場合、実行可能バイナリにデバッグ情報を埋め込んでおく必要があるため、下記のようにリリースプロファイルに debug = true を追加。

Cargo.toml
...

[profile.release]
debug = true

cargo flamegraphコマンドにて、対象のプログラムを測定しながら実行。対象プログラムに対してコマンドライン引数を渡す場合には、下記のように -- の後ろに指定する。

$ cargo flamegraph -- ./patterns/moldon30p25.rle 1 1000000 1
automatically selected target game-of-life in package game-of-life as it is the only valid target
   Compiling anyhow v1.0.68
   Compiling game-of-life v0.1.0 (.../game-of-life)
    Finished release [optimized + debuginfo] target(s) in 2.35s
Generation = 0
...

Generation = 1000000
...

[ perf record: Woken up 253 times to write data ]
[ perf record: Captured and wrote 63.343 MB perf.data (3993 samples) ]
writing flamegraph to "flamegraph.svg"
...

実行が完了すると、プロファイル結果としてperf.dataと下記のようなflamegraph.svgが生成される。
perfがperf.dataを生成し、その後にcargo-flamegraphがperf.dataをflamegraph.svgへと変換するようだ。

flamegraph.svgは、Webブラウザなどで表示できる。目的の箇所にマウスオーバーすると、その箇所の詳細情報を表示してくれる。例えば game_of_life::life::board::Board::get_grid にマウスカーソルを合わせると、Function: game_of_life::life::board::Board::get_grid (1,986 samples, 52.07%) と表示され、この関数が実行時間全体の52.07%を占めていることがわかる。

MasakiMasaki

ValgrindのCallgrindを使って実行時間内訳を測定した。

まず、valgrindコマンドをインストールした。

$ apt install valgrind
...

flamegraph同様に、実行時間内訳を見るには実行可能バイナリにデバッグ情報を埋め込んでおく必要がある。下記のようにリリースプロファイルに debug = true を追加。

Cargo.toml
...

[profile.release]
debug = true

リリースプロファイルにてプログラムをビルド。

$ cargo build --release
...

valgrindのcallgrind付きでプログラムを実行。仮想マシン上での実行にはネイティブ実行よりも所要時間がかかるので注意: 今回のケースでは、ネイティブ実行が3.84秒だったのに対して、valgrind付きでは168秒かかった。

$ valgrind --tool=callgrind ./target/release/game-of-life ./patterns/moldon30p25.rle 1 1000000 1
==867042== Callgrind, a call-graph generating cache profiler
==867042== Copyright (C) 2002-2017, and GNU GPL'd, by Josef Weidendorfer et al.
==867042== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
==867042== Command: ./target/release/game-of-life patterns/moldon30p25.rle 1 1000000 1
==867042==
==867042== For interactive control, run 'callgrind_control -h'.
Generation = 0
...

Generation = 1000000
...

==867042==
==867042== Events    : Ir
==867042== Collected : 48193555300
==867042==
==867042== I   refs:      48,193,555,300

実行が完了すると、callgrind.out.867042 などという名前のファイルが生成される。中身を見るには、下記のようにコマンドラインでcallgrind_annotateコマンドを使うか、KCachegrindコマンドで可視化するとよい。

$ callgrind_annotate callgrind.out.867042
--------------------------------------------------------------------------------
Profile data file 'callgrind.out.867042' (creator: callgrind-3.16.1)
--------------------------------------------------------------------------------
I1 cache: 
D1 cache: 
LL cache: 
Timerange: Basic block 0 - 5485619220
Trigger: Program termination
Profiled target:  ./target/release/game-of-life patterns/moldon30p25.rle 1 1000000 1 (PID 867042, part 1)
Events recorded:  Ir
Events shown:     Ir
Event sort order: Ir
Thresholds:       99
Include dirs:     
User annotated:   
Auto-annotation:  on

--------------------------------------------------------------------------------
Ir                      
--------------------------------------------------------------------------------
48,193,555,300 (100.0%)  PROGRAM TOTALS

--------------------------------------------------------------------------------
Ir                       file:function
--------------------------------------------------------------------------------
16,456,000,000 (34.15%)  /rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/core/src/slice/index.rs:game_of_life::life::universe::Universe::update
15,985,000,000 (33.17%)  src/life/board.rs:game_of_life::life::universe::Universe::update
 7,763,000,000 (16.11%)  src/life/universe.rs:game_of_life::life::universe::Universe::update [/home/masaki/work/individual/2023-01-01-rust-game-of-life/game-of-life/target/release/game-of-life]
 3,388,000,000 ( 7.03%)  /rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/core/src/iter/traits/accum.rs:game_of_life::life::universe::Universe::update
 2,949,000,000 ( 6.12%)  /rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/core/src/cmp.rs:game_of_life::life::universe::Universe::update
   717,000,000 ( 1.49%)  /rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/core/src/iter/range.rs:game_of_life::life::universe::Universe::update
   374,000,000 ( 0.78%)  /rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/core/src/num/uint_macros.rs:game_of_life::life::universe::Universe::update
   241,502,145 ( 0.50%)  ./malloc/malloc.c:_int_malloc [/lib/x86_64-linux-gnu/libc-2.31.so]

--------------------------------------------------------------------------------
-- Auto-annotated source: src/life/board.rs
--------------------------------------------------------------------------------
Ir                     

-- line 3 ----------------------------------------
            .           pub struct Board {
            .               width: LengthType,
            .               grids: Vec<bool>,
            .           }
            .           
            .           impl Board {
            .               pub fn new(width: LengthType, height: LengthType) -> Self {
            .                   let init = false;
    3,000,007 ( 0.01%)          let grids = vec![init; (width * height) as usize];
          315 ( 0.00%)  => /rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/alloc/src/vec/mod.rs:alloc::vec::from_elem (1x)
            .                   Self { width, grids }
            .               }
            .               fn position_to_index(&self, x: LengthType, y: LengthType) -> usize {
9,196,003,848 (19.08%)          (y * self.width + x) as usize
            .               }
            .               pub fn width(&self) -> LengthType {
    2,000,044 ( 0.00%)          self.width
            .               }
            .               pub fn height(&self) -> LengthType {
    8,000,026 ( 0.02%)          (self.grids.len() / (self.width as usize)) as LengthType
            .               }
            .               pub fn get_grid(&self, x: LengthType, y: LengthType) -> bool {
          968 ( 0.00%)          let idx = self.position_to_index(x, y);
4,356,004,272 ( 9.04%)          self.grids[idx]
            .               }
            .               pub fn set_grid(&mut self, x: LengthType, y: LengthType, v: bool) {
            .                   let idx = self.position_to_index(x, y);
  484,000,448 ( 1.00%)          self.grids[idx] = v;
            .               }
            .           }

1,936,000,003 ( 4.02%)  <counts for unidentified lines in src/life/board.rs>

--------------------------------------------------------------------------------
-- Auto-annotated source: src/life/universe.rs
--------------------------------------------------------------------------------
...

細かくは見ていないが、flamegraph(今回使った手段はLinux perf)とValgrindそれぞれから得られる数値には差異があることがわかる。Linux performance testing with perf, gprof and Valgrindなどに書いてあるように、両者の測定手段が下記のように異なっているためである。

  • Linux perf
    • ネイティブCPUを使って実行する
    • CPUのハードウェアカウンタを使ってプロファイル情報を収集する
  • Valgrind
    • プログラムを仮想マシン命令に変換してから実行する
    • 仮想マシン上で実行する際にプロファイル情報を収集する

今回の習作では、測定手段としてはどちらでもよいので、所要時間が短く手間が少ないflamegraphを使うことにした。

MasakiMasaki

main関数の戻り値について調べた。参考文献は下記。

main.rsを下記のようにしていたが(app::run()の戻り値はanyhow::Result):

src/main.rs
mod app;
mod life;
use std::process::ExitCode;

fn main() -> ExitCode {
    if let Err(e) = app::run() {
        eprintln!("{}", e);
        ExitCode::FAILURE
    } else {
        ExitCode::SUCCESS
    }
}

下記で十分だった。

src/main.rs
mod app;
mod life;
use anyhow::Result;

fn main() -> Result<()> {
    app::run()
}
MasakiMasaki

テストの整備を始めた。

一般的な意味でのソフトウェアテストについては知っているつもりなので、RustとCargoでの流儀に合わせた実装手順を調べた。参考文献は下記。概要を知るには、Rust by Exampleのほうがわかりやすい。

Rust by Exampleの説明によると、RustおよびCargoでのテストは下記の3つに分類されており、実装手順もおおよそ決まっている。

  • 単体テスト (Unit testing)
  • 結合テスト (Integration testing)
  • ドキュメンテーションテスト (Doc testing)
MasakiMasaki

単体テストは、典型的にはテスト対象のモジュールごとに下記のように書く。(Rust by Example日本語版のユニットテストから引用)

pub fn add(a: i32, b: i32) -> i32 {
    a + b
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_add() {
        assert_eq!(add(1, 2), 3);
    }
}

ルールとガイドは、下記になっているようだ。

  • 単体テストの関数には #[test] を付ける (必須)
    • test属性の付いた関数は、テスト用の関数として扱われる。この関数は、テストモードでしかコンパイルされず、非テストモード用のライブラリやバイナリには組み込まれない
    • 参考: The Rust ReferenceのThe test attribute
  • 単体テストの関数は、テスト対象のモジュール内に mod tests を設けてその内部に格納する (推奨)
    • また、そのtestsモジュールには#[cfg(test)]を付ける(推奨)。cfg(test)属性のついたモジュールは、テスト関数同様にテストモードでしかコンパイルされない
      • testsモジュールが純粋にテスト関数しか含んでいないなら、cfg(test)属性を付けても付けなくても何も変わらない気がするが、テスト関数が使うテスト関数以外の何か(例えば定数定義)などを含むならこの属性は有用

実装済みの各モジュールのソースコードの末尾にmod testsを追加してテスト関数を書けばよいので、いくつか単体テストを実装した。例えば下記。

src/life/board.rs
pub struct Board { ... }

impl Board {
    pub fn new(width: ..., height: ...) -> Self {
        ...
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_new_minimum() {
        let width = 1;
        let height = 1;
        let t = Board::new(width, height);
        assert_eq!(t.width(), width);
        assert_eq!(t.height(), height);
    }
}

なお、テストの実装がテスト関数のみの場合、下記のようにしてもcargo testやcargo runを実行できた。(試しただけで導入はしなかったが)

  • mod testsから#[cfg(test)]を外す
    • cargo checkでuse super::*を使っていないという警告が出る
  • mod testsを取り除いて、#[test]付きの関数をテスト対象モジュールの直下に置く

Boardに対する単体テストを4つ設けた状態でのcargo testの実行結果は下記のとおり。テスト関数は、クレートルートからの相対パス名で表示されるようだ。

$ cargo test 
   Compiling anyhow v1.0.68
   Compiling game-of-life v0.1.0 (.../game-of-life)
    Finished test [unoptimized + debuginfo] target(s) in 1.46s
     Running unittests src/main.rs (target/debug/deps/game_of_life-3e3f029d7ac82410)

running 4 tests
test life::board::tests::test_get_grid ... ok
test life::board::tests::test_new_default ... ok
test life::board::tests::test_new_minimum ... ok
test life::board::tests::test_set_grid ... ok

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
MasakiMasaki

結合テストを設けるには、次のようにする必要があるようだ。

  • 結合テスト対象のクレートをライブラリクレートにする
    • バイナリクレートには結合テストを行えない。よって、パッケージがバイナリクレートのみから構成されている場合は、パッケージ内にライブラリクレートを新設し、テスト対象のものをライブラリクレートに移す必要がある
  • 結合テストのソースコードをtests/ディレクトリ内に置く

上記は、どちらかというとRustではなくCargoによる規則らしい。個別の規則は下記のとおりのようだ。

  • Rustによる規則
  • Cargoによる規則
    • The Rust Programming Language日本語版のパッケージとクレートより:
      • パッケージは1つ以上のクレートを持っている必要がある
      • パッケージが持つライブラリクレートの個数は0個または1個のいずれか (2個は持てない)
      • パッケージが持つバイナリクレートの個数は何個でもよい (ゼロでもよい)
    • The Cargo BookのCargo TargetsのTests
      • testsディレクトリに置かれたファイルは結合テストとして扱われる。これらはそれぞれ独立のクレートとしてコンパイルされる

現在はパッケージに1つのバイナリクレートのみを設けているので、新たにライブラリクレートを設けて大半のものをライブラリクレートへと移動させるところから始める。結合テストはその後。

MasakiMasaki

The Cargo BookのPackage Layoutには、下記のように書いてある。

  • デフォルトのlibrary fileは src/lib.rs
  • デフォルトのexecutable fileは src/main.rs
    • ここでいうexecutable fileは、binary crateのcrate rootのことだろう
  • デフォルト以外のexecutable fileは src/bin/ に入れてよい

単にsrc/lib.rsとsrc/main.rsの両方を使うと、src/内にほかの*.rsファイルが置かれたとき、それがライブラリクレートのものなのかバイナリクレートのものなのか見分けがつかなくなりそうだ。(例: Rust modules confusion when there is main.rs and lib.rs - Stack Overflow)

バイナリクレートを持つパッケージの例としてCargoを眺めたところ、下記のようになっていた。src/内でライブラリクレートとバイナリクレートが明確に分けられており、わかりやすい。

  • src/内の構成
    • cargo/
      • lib.rs
      • core/
        • ...
      • ...
    • bin/
      • cargo/
        • main.rs
        • ...
  • Cargo.tomlでの定義
    • [lib]: name = "cargo"、path = "src/cargo/lib.rs"
    • [[bin]]: name = "cargo"。pathは書かれていない (src/bin/cargo/main.rs が使われるようだ)

上記を参考に、手元のパッケージの構成を下記のようにした。実行可能プログラムを構成するmain.rsとapp.rsだけをバイナリクレートに残し、ほかはすべてライブラリクレートへと移動させた。

  • src/内の構成
    • lib
      • lib.rs
      • board.rs
      • universe.rs
      • ...
    • bin
      • game_of_life
        • main.rs
        • app.rs
  • Cargo.tomlでの定義
    • [lib]: path = "src/lib/lib.rs"。nameは書かない
      • パッケージが持てるライブラリクレートの個数は0または1ということで、nameは省略してもよいようだ (エラーにならなかった)
    • [[bin]]: name = "game_of_life"。pathは書かない

なお、作業途上でバイナリクレートのmain関数をsrc/bin/main.rsに置いてみたことがあったが、あまり都合がよくなかった。このファイルだけで完結するなら問題ないが、そのバイナリクレート内にサブモジュールを設けてsrc/bin/app.rsなどとして置こうとすると、Cargoがsrc/bin/app.rsを別のバイナリクレートのクレートルートとして扱おうとしてエラーになってしまった。

MasakiMasaki

細かい話だが、パッケージ名とクレート名でのハイフン-とアンダーバー_の扱いと慣習について。パッケージ名にハイフン-を用いた場合、ソースコード内のクレート名にはハイフン-を使えないが、どう扱われるのか?

crates.io: Rust Package Registryで見ると、パッケージ名の名称内に使う区切り文字にはハイフン-とアンダーバー_の両方が使える・使われている様子だった。例えば下記が見つかった。

例えばcargo-edit v0.11.8の場合は、下記のようになっていた。

  • Cargo.toml
    • [package]のnameはcargo-edit。ハイフン-を使用
    • [lib]の記述なし
  • バイナリクレート内のソースコード: 例えばsrc/bin/add/cli.rsからライブラリクレートを参照する際には、cargo_editという名前を使っていた。ハイフン-ではなくアンダーバー_になっている

上記の例からすると、Cargoがパッケージ名cargo-editからライブラリクレート名cargo_editへと自動変換しているということだろうか。

MasakiMasaki

お膳立てができたので、下記のような結合テストをtests/glider_test.rsとして追加した。

tests/glider_test.rs
use anyhow::Result;
use game_of_life::Universe;

#[test]
fn glider_test() -> Result<()> {
    let pattern_init = "\
        ......\n\
        ..O...\n\
        ...O..\n\
        .OOO..\n\
        ......\n\
        ......\n\
        ";
    let pattern_final = "\
        ......\n\
        ......\n\
        ...O..\n\
        ....O.\n\
        ..OOO.\n\
        ......\n\
        ";
    let steps = 4;
    let mut t = Universe::load_from_string(pattern_init)?;
    let expected = Universe::load_from_string(pattern_final)?;
    println!("Initial:\n{t}");
    for _ in 0..steps {
        t.update();
    }
    println!("Generation {steps}, Final:\n{t}");
    println!("Expected:\n{expected}");
    assert_eq!(t, expected);
    Ok(())
}

これは、グライダーのパターンを使った下記のようなテストである。

  • 初期状態(の文字列表現)は、pattern_initのとおり。縦6・横6の盤面にグライダーが1つ置かれている
  • 最終状態の期待値は、pattern_finalのとおり。初期状態のグライダーが右に1マス、下に1マスずれている
  • 初期状態から4世代進めたものが最終状態の期待値と一致するかどうかをテストする
  • デバッグ用に、適宜println!を使っている

cargo testの実行結果は下記のとおり。

$ cargo test 
   Compiling anyhow v1.0.68
   Compiling game-of-life v0.1.0 (.../game-of-life)
    Finished test [unoptimized + debuginfo] target(s) in 2.45s
     Running unittests src/lib/lib.rs (target/debug/deps/game_of_life-0236fbb1b213bd56)

running 4 tests
test board::tests::test_get_grid ... ok
test board::tests::test_new_default ... ok
test board::tests::test_new_minimum ... ok
test board::tests::test_set_grid ... ok

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/bin/game_of_life/main.rs (target/debug/deps/game_of_life-139f0e56c4a7728a)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running tests/glider_test.rs (target/debug/deps/glider_test-3598d4461d5cdbbd)

running 1 test
test glider_test ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests game-of-life

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

glider_testだけをデバッグ表示付きで実行する場合は、下記のようにする。

cargo test --test glider_test -- --nocapture
    Finished test [unoptimized + debuginfo] target(s) in 0.00s
     Running tests/glider_test.rs (target/debug/deps/glider_test-3598d4461d5cdbbd)

running 1 test
Initial:
......
..O...
...O..
.OOO..
......
......

Generation 4, Final:
......
......
...O..
....O.
..OOO.
......

Expected:
......
......
...O..
....O.
..OOO.
......

test glider_test ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
MasakiMasaki

ドキュメントの整備を始めた。

ドキュメンテーションについては、以前に一度眺めたが、改めて調べた。参考文献は下記のとおり。

以下のものはいずれも、ドキュメンテーションコメントである。

記法 名称 inner/outer line/block
//! ... inner line doc comment inner line
/*! ... */ inner block doc comment inner block
/// ... outer line doc comment outer line
/** ... */ outer block doc comment outer block

inner doc commentはそのコメント直後の要素に対するドキュメント、outer doc commentはそのコメントを含む要素に対するドキュメントである。

これらのコメント内では、Markdown記法がサポートされる。サポートされる文法詳細はThe rustdoc bookのMarkdownに記載されている。よく使われるMarkdown記法のセクションに下記がある。

  • Examples: 使い方の例を示す
  • Panics: panic! する可能性を説明する
  • Errors: 関数の戻り値の型がResultの場合に、起きうるエラーの種類と発生条件を示す
  • Safety: 関数がunsafeなら、関数がunsafeである理由と、関数が呼び出し元に期待する不変条件などの補足情報を示す

引数と戻り値の書き方については、明確な決まりはなさそう。

cargo doc を実行すると、target/doc 内にドキュメントが生成される(cargoは背後でrustdocを使う)。cargo doc --open を実行すると、同様のドキュメント生成を行った後に、生成されたドキュメントをWebブラウザで開いてくれる。

ドキュメンテーションコメント内のMarkdown記法のコードブロックは、ドキュメンテーションテストとして扱われる。ドキュメンテーションテストは cargo test で実行できる。

MasakiMasaki

手始めに、ドキュメンテーションコメントを何も書かずにcargo docを実行してみた。

$ cargo doc
warning: output filename collision.
The bin target `game_of_life` in package `game-of-life v0.1.0 (.../game-of-life)` has the same output filename as the lib target `game-of-life` in package `game-of-life v0.1.0 (.../game-of-life)`.
Colliding filename is: .../game-of-life/target/doc/game_of_life/index.html
The output filenames should be unique.
This is a known bug where multiple crates with the same name use
the same path; see <https://github.com/rust-lang/cargo/issues/6313>.
If this looks unexpected, it may be a bug in Cargo. Please file a bug report at
https://github.com/rust-lang/cargo/issues/ with as much information as you
can provide.
cargo 1.67.0 (8ecd4f20a 2023-01-10) running on `x86_64-unknown-linux-gnu` target `x86_64-unknown-linux-gnu`
First unit: Unit { pkg: Package { id: PackageId { name: "game-of-life", version: "0.1.0", source: ".../game-of-life" }, ..: ".." }, target: TargetInner { name: "game_of_life", doc: true, ..: with_path(".../game-of-life/src/bin/game_of_life/main.rs", Edition2021) }, profile: Profile { ..: default_dev() }, kind: Host, mode: Doc { deps: true }, features: [], artifact: false, is_std: false, dep_hash: 6735310914438146216 }
Second unit: Unit { pkg: Package { id: PackageId { name: "game-of-life", version: "0.1.0", source: ".../game-of-life" }, ..: ".." }, target: TargetInner { ..: lib_target("game-of-life", ["lib"], ".../game-of-life/src/lib/lib.rs", Edition2021) }, profile: Profile { ..: default_dev() }, kind: Host, mode: Doc { deps: true }, features: [], artifact: false, is_std: false, dep_hash: 11778008241721074752 }
   Compiling anyhow v1.0.68
 Documenting anyhow v1.0.68
    Checking game-of-life v0.1.0 (.../game-of-life)
 Documenting game-of-life v0.1.0 (.../game-of-life)
    Finished dev [unoptimized + debuginfo] target(s) in 2.33s

バイナリクレートとライブラリクレートの名前が両方ともgame_of_lifeなので警告が出ている。
同じくバイナリクレートとライブラリクレートの両方を持っているcargoを参考に、Cargo.tomlの[[bin]]にdoc = falseを書いてリトライした。

$ cargo doc
   Compiling anyhow v1.0.68
 Documenting anyhow v1.0.68
 Documenting game-of-life v0.1.0 (.../game-of-life)
    Finished dev [unoptimized + debuginfo] target(s) in 1.94s

今度は問題なし。

cargo doc --open を実行すると、target/doc/game_of_life/index.html の内容がgame_of_lifeクレートのトップページとしてWebブラウザ上で表示された。まだドキュメンテーションコメントを一切入れていないが、それでもモジュール・構造体・関数・列挙などのpublicな情報がきれいにまとめられていた。これだけでも結構便利。

MasakiMasaki

Board::newという関数にテスト付きでドキュメントを書いてみた。

pub struct Board {
    ...
}

impl Board {
    /// Construct a new `Board` with the specified width and height.
    ///
    /// # Examples
    ///
    /// ```
    /// let board = Board::new(3, 2);
    /// assert_eq!(board.width(), 3);
    /// assert_eq!(board.height(), 2);
    /// ```
    ///
    pub fn new(width: LengthType, height: LengthType) -> Self {
        let init = false;
        let grids = vec![init; (width * height) as usize];
        Self { width, grids }
    }

    ...
}

cargo docの結果は意図どおりになった。生成されたドキュメントのBoard::new関数の説明にConstruct a new Board with the specified width and height.という1行説明が入り、その後にExamplesという章とサンプルコードが配置された。

が、cargo testは失敗した。実行結果は下記のとおり。

% cargo test
   Compiling anyhow v1.0.69
   Compiling game-of-life v0.1.0 (.../game-of-life)
    Finished test [unoptimized + debuginfo] target(s) in 2.16s
     Running unittests src/lib/lib.rs (target/debug/deps/game_of_life-f99a3344a066952b)

running 4 tests
test board::tests::test_get_grid ... ok
test board::tests::test_new_default ... ok
test board::tests::test_new_minimum ... ok
test board::tests::test_set_grid ... ok

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/bin/game_of_life/main.rs (target/debug/deps/game_of_life-a424bef552af6ca8)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running tests/glider_test.rs (target/debug/deps/glider_test-3ced278d0e4d0bcd)

running 1 test
test glider_test ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

   Doc-tests game-of-life

running 1 test
test src/lib/board.rs - board::Board::new (line 16) ... FAILED

failures:

---- src/lib/board.rs - board::Board::new (line 16) stdout ----
error[E0433]: failed to resolve: use of undeclared type `Board`
 --> src/lib/board.rs:17:13
  |
3 | let board = Board::new(3, 2);
  |             ^^^^^ use of undeclared type `Board`
  |
help: consider importing this struct
  |
2 | use game_of_life::Board;
  |

error: aborting due to previous error

For more information about this error, try `rustc --explain E0433`.
Couldn't compile the test.

failures:
    src/lib/board.rs - board::Board::new (line 16)

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.04s

error: doctest failed, to rerun pass `--doc`

use of undeclared type Boardというエラーなので、The rustdoc bookのHiding portions of the exampleなどを参考に、ドキュメンテーションテストの箇所を下記のようにした。

    /// ```
    /// # use game_of_life::Board;
    /// let board = Board::new(3, 2);
    /// assert_eq!(board.width(), 3);
    /// assert_eq!(board.height(), 2);
    /// ```
  • use game_of_life::Board;を追加し、ビルドできるようにした
  • 先頭に#を足して隠した

cargo test --docとし、doc testだけをリトライ。今度は通った。

$ cargo test --doc
   Compiling anyhow v1.0.69
   Compiling game-of-life v0.1.0 (.../game-of-life)
    Finished test [unoptimized + debuginfo] target(s) in 1.31s
   Doc-tests game-of-life

running 1 test
test src/lib/board.rs - board::Board::new (line 16) ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.19s
MasakiMasaki

ドキュメンテーション内にコードを書いてテストできるなら、通常の単体テストを書くよりも、同じコードをドキュメンテーションテストにしたほうがよい気がする。ドキュメントとテストを兼ねられる。
ただ、コードが込み入っていてドキュメント向きでないならそうでもないか。

MasakiMasaki

ドキュメンテーション関係で拾った情報をまとめておく。どれもThe rustdoc bookによるもの。

  • Attributes
    • ドキュメンテーション内のコードブロックに ```no_run ... ``` などと属性をつけることで、コードの扱いを制御できる。例えば下記の属性がある
      • compile_fail: コンパイルが失敗する
      • no_run: コンパイルできるが、実行しない
      • should_panic: コンパイルも実行もできるが、panicする
  • What to include (and exclude)
    • #![warn(missing_docs)]をつけると、ドキュメントのない要素が警告される。#![deny(missing_docs)]ならエラーになる。すべての要素にドキュメントを書くようにしたいなら、モジュールやクレートに指定するとよい
MasakiMasaki

実行速度測定について。
プロファイリング(内訳の測定)の手段は以前に調べたので、今度はベンチマークについて調べる。

ベンチマーク手段に関する記述として、参考にしたものは下記のとおり。

nightly build限定のtest crateか、さもなければCriterion.rsが定番らしい。
前者の最新情報をすぐには特定できなかったので、後者を試すことにする。

MasakiMasaki

Criterion.rsのREADME.mdと、そこにリンクが貼られているGetting Started - Criterion.rs Documentationを参考に作業。

まず、gnuplotをインストールした。

sudo apt install gnuplot

続いて、cargo add --dev criterion を実行。Cargo.tomlに下記が追加された。

Cargo.toml
+[dev-dependencies]
+criterion = "0.4.0"

また、同じくCargo.tomlに下記の記述を追加した。

Cargo.toml
+[[bench]]
+name = "benchmark"
+harness = false

次に、benches/benchmark.rs を新規作成。下記のようにした。なお、前述のCriterion.rsのガイドなどではuse指定の対象にcriterion::black_boxも入っていたが、使っていない様子だったため外した。

benches/benchmark.rs
use criterion::{criterion_group, criterion_main, Criterion};
use game_of_life::Universe;

fn workload(universe: &Universe, steps: u32) {
    let mut universe = universe.clone();
    for _ in 0..steps {
        universe.update();
    }
}

fn do_benchmark(c: &mut Criterion, id: &str, pattern: &str, steps: u32) {
    let universe = Universe::load_from_string(pattern).unwrap();
    c.bench_function(id, |b| b.iter(|| workload(&universe, steps)));
}

fn glider_benchmark(c: &mut Criterion) {
    let id = "glider-1k";
    let pattern = "\
        ......\n\
        ..O...\n\
        ...O..\n\
        .OOO..\n\
        ......\n\
        ......\n\
        ";
    let steps = 1000;
    do_benchmark(c, id, pattern, steps);
}

criterion_group!(benches, glider_benchmark);
criterion_main!(benches);

cargo benchにて実行。下記のようになった。

$ cargo bench
   Compiling autocfg v1.1.0
   Compiling proc-macro2 v1.0.51
   ...
   Compiling game-of-life v0.1.0 (.../game-of-life)
   Compiling criterion v0.4.0
    Finished bench [optimized] target(s) in 51.20s
     Running unittests src/lib/lib.rs (target/release/deps/game_of_life-7a689bc2481cb641)

running 2 tests
test board::tests::test_new_default ... ignored
test board::tests::test_new_minimum ... ignored

test result: ok. 0 passed; 0 failed; 2 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/bin/game_of_life/main.rs (target/release/deps/game_of_life-2f73c2961d951898)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running benches/benchmark.rs (target/release/deps/benchmark-0b22824691f9f4d1)
glider-1k               time:   [288.77 µs 289.90 µs 291.51 µs]
Found 10 outliers among 100 measurements (10.00%)
  3 (3.00%) high mild
  7 (7.00%) high severe

実行と測定はできたようだが、例えばFile Structureに書いてあるような target/criterion/$BENCHMARK_NAME/report/ が出力されなかった。手元での出力ファイルは下記のみ。何か設定が足りていないらしい。

$ find target/criterion
target/criterion
target/criterion/glider-1k
target/criterion/glider-1k/new
target/criterion/glider-1k/new/benchmark.json
target/criterion/glider-1k/new/tukey.json
target/criterion/glider-1k/new/estimates.json
target/criterion/glider-1k/new/sample.json
target/criterion/glider-1k/base
target/criterion/glider-1k/base/benchmark.json
target/criterion/glider-1k/base/tukey.json
target/criterion/glider-1k/base/estimates.json
target/criterion/glider-1k/base/sample.json
MasakiMasaki

下記などを色々眺めた。html_reports featureを有効にすれば、レポートが出てきそう。

その後に見つけたChangeLogに明記されていた。

The Cargo BookのDependency featuresを参考に、Cargo.tomlを下記のように変更した。

Cargo.toml
 [dev-dependencies]
-criterion = "0.4.0"
+criterion = { version = "0.4.0", features = ["html_reports"] }

cargo benchを再実行した。ログはほぼ同一だったが、target/criterion/report/index.html と target/criterion/glider-1k/report/index.html や関連ファイルが生成された。
Webブラウザで表示したグラフは下記のとおり。

criterion

MasakiMasaki

Criterion.rsのREADME.mdには「グラフ生成にはgnuplotを使う」と書いてあるが、Criterion.rs DocumentationのHTML Reportには「gnuplotがあれば使い、なければplottersクレートを使う」と書いてあるので、試しにgnuplotを削除してcargo benchを再実行してみた。

結果、ほぼ同一の見た目のグラフが生成された。実行時のログには下記のようにGnuplot not found, using plotters backendという表示が出ていた。

$ cargo bench
    Finished bench [optimized] target(s) in 0.07s
     Running unittests src/lib/lib.rs (target/release/deps/game_of_life-50ec2c4809e90b16)

running 2 tests
test board::tests::test_new_default ... ignored
test board::tests::test_new_minimum ... ignored

test result: ok. 0 passed; 0 failed; 2 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/bin/game_of_life/main.rs (target/release/deps/game_of_life-c9702b71ec02a1ca)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running benches/benchmark.rs (target/release/deps/benchmark-e57e59cf751a9c61)
Gnuplot not found, using plotters backend
glider-1k               time:   [304.39 µs 311.91 µs 323.75 µs]
                        change: [-24.364% -20.014% -15.711%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 15 outliers among 100 measurements (15.00%)
  4 (4.00%) high mild
  11 (11.00%) high severe

Criterion.rsのためだけにgnuplotをインストールする必要はなさそう。

MasakiMasaki

イテレータの理解が浅いことが気になっていたので、下記を読んでおさらいした。

イテレータおよび関連するものの説明を自分なりの理解で書き下しているところ。後で記事にするか。

MasakiMasaki

pubの開示範囲を細かく指定できることを知った。参考文献はThe Rust Referenceの下記。

下記のバリエーションが使えるとのこと。

  • 無指定: 開示しない
  • pub: 開示
  • pub(in path): pathに対してのみ開示
  • pub(crate): 現在のクレートに対してのみ開示
  • pub(super): 親モジュールに対してのみ開示。pub(in super)と等価
  • pub(self): 現在のモジュールに対してのみ開示。pub(in self)と等価で、つまりはpub(self)を書かないのと同一

pub(self)は何のためにあるんだろうと思ったら、同じ質問がStack Overflowに出ていた。

理由は、下記のRFCに書かれていた。

曰く、「pub(self) itemは単にitemと書くのと等価。それでもpub(self)という一般化がサポートされている主な理由は、マクロ内にpub($arg) itemという記述を用いたときに$argにselfを渡すとpubを取り消す効果が得られるため。それ以外の状況では、これは単に冗長な構文」だそうだ。

MasakiMasaki

パターンファイルを読み込めるかどうかのテストを結合テストに加える際に、Cargo管理下の結合テストに特定のファイルを読み込ませるにはどうすればよいのか調べた。

まず、答えを知りたい質問そのものとして、下記が見つかった。

曰く、環境変数CARGO_MANIFEST_DIRを基点にファイルを指定すればよいとのこと。

CARGO_MANIFEST_DIRの正確な定義と使い方は、The Cargo BookのEnvironment variables Cargo sets for cratesに記載されている。おおよそ下記のとおり。

  • Cargoはいくつかの環境変数をコンパイル時に提示している。例えばlet version = env!("CARGO_PKG_VERSION");などと記述すると、CARGO_PKG_VERSIONの値が得られる
  • CARGO_MANIFEST_DIRは、パッケージのマニフェストを含むディレクトリを示す (CargoのマニフェストとはCargo.tomlのこと)

また、上記で使っているenv!マクロは、コンパイル時の環境変数の値を返すマクロだった。結果は文字列スライスで得られる。
それから、文字列スライス同士をコンパイル時に結合するには、concat!マクロを使えばよいようだ。

以上を踏まえて、下記のようなテストコードを書いた。

#[test]
fn load_from_file_rle_test() -> Result<()> {
    let path_str = concat!(env!("CARGO_MANIFEST_DIR"), "/patterns/glider.rle");
    let path = Path::new(path_str);
    let universe = Universe::load_from_file(path)?;
    ...
}

パッケージのrootディレクトリにpatternsディレクトリを作成し、その中にhttps://conwaylife.com/patterns/glider.rleをダウンロードして置いておけば、ロードのテストができる。

MasakiMasaki

テストの整備がだいぶ進んで、頻繁に手動でcargo testを実行するようになっていたので、cargo-watchを導入した。

最初に見かけたときは使い方がわからなかったのだが、コマンドラインでcargo checkなどとしている端末の1つでcargo watchをフォアグラウンドで実行すればよいだけだった。実行するとcargo watchがプロンプトを奪った状態になるので、その状態で別の箇所のエディタなどを使ってソースコードを編集すればよい。ファイルを保存すると、そのたびにcargo watchが指定されたコマンド: 例えばcargo checkなどを実行してくれる。止めたくなったら、cargo watchをCtrl-Cなどで停止させればよい。

導入手順は下記のとおり。

cargo install cargo-watch

実行手順は、例えば下記のとおり。この指定だと、ソースコードの更新を検出するたびにcargo fmt・cargo check・cargo clippy・cargo testの順で実行してくれる。

cargo watch -x fmt -x check -x clippy -x test
MasakiMasaki

ちょっと息切れしてきた感触があるので、習作の当初の目標を再確認。

  • Rustの学習として
    • Rustの機能を適切に使う
      • 特に: 所有権、エラー処理、構造体とEnum、コレクション、トレイト、ジェネリック型、イテレータ、クロージャ、スマートポインタ、モジュールやクレート、などをRustの流儀にしたがって使用する (必要なければ無理に使うことはしないが)
    • Cargoの機能を適切に使う
    • テストを整備する
    • ドキュメントを整備する
    • パフォーマンスを測定する。また、それを用いながら実行時間短縮作業を行い、その作業フローを把握する
  • Game of Lifeとして
    • 基本ルール(B3/S23)のとおりの状態遷移を扱えるようにする
    • 既存のパターンファイルを読み込めるようにする
    • 仕組みとして、他のLife-like cellular automata: 例えばHighLife(B36/S23)を扱えるようにする
    • Bounded gridsにあるような、複数種類の盤面末端処理を扱えるようにする
    • 表示と操作は、最初は標準入出力によるシンプルなものから始める。これだけだと味気ないので、WasmとWebブラウザで扱えるとよいだろうか

現状はおおよそ下記のとおり。

  • Rustの学習
    • できた気がすること
      • 所有権: 不変参照、可変参照、ムーブの使い分けはおそらくOK。スライスもおそらくOK。ただ、ライフタイムはまだ使ったことがない
      • エラー処理: Option、Result、anyhowを使った基本的なものならOK
      • 構造体とEnum: 基本的なものなら問題なし。網羅的には見ていないところもあるが、後はわからなければリファレンスを見て補えばよさそう
      • クロージャ: 基本的なものなら問題なし
      • イテレータ: 感覚的には問題ない気がする。手に馴染むレベルにするには、数をこなす必要がありそう
      • モジュール・クレート・パッケージ: ライブラリクレートとバイナリクレートの同居ぐらいまでならOK
      • 入出力: 標準入出力と基本的なファイル入出力ぐらいまではOK
      • rustupとCargo: ある程度は触った。問題ない気がする
      • テストとドキュメント: 単体テスト、結合テスト、ドキュメンテーション、ドキュメンテーションテストを一通り扱った。問題ない気がする
      • パフォーマンス測定: プロファイラとベンチマークを扱った。まずはこの程度でよい気がする
    • それほど踏み込んで扱っていないこと
      • トレイト: 既存のトレイトは多少使ったが、自作は未実施
      • ジェネリック型: 使おうとしたが、ジェネリック境界で迷ったのでスキップした
      • スマートポインタ: 機会がないため使わなかった
    • まったく扱わなかったこと
      • 並行性、マクロの作成、unsafe
  • Game of Lifeの実装
    • 実装済み
      • 基本ルールの状態遷移
      • 既存のパターンファイルの読み込み (.cells, .rle)
      • 盤面末端処理: Torusのみ対応
      • 標準出力への表示
    • 未実装
      • 基本以外のルールへの対応
      • Torus以外の盤面末端処理
      • 標準出力以外の表示手段への対応

Game of Lifeとして、基本ルール以外のルールへの対応・Torus以外の盤面末端処理ができていないのは、プログラミングの練習としてイマイチな気がする。追加しよう。
Rustとしての未実施項目は、必要な場面で使わないと身につかなさそうなので、「出番があれば試す」ぐらいの扱いにしておく。

MasakiMasaki

ある関数内ではpanicが発生しないことを保証するにはどうすればいいのか調べた。参考情報として下記が見つかったが、それほど系統だった方法はなさそうだった。

MasakiMasaki

ここまでの一連の作業で開発の流れのイメージがつかめたのと、ルール変更対応などの機能拡張をやりやすくするために構成を大きく組み替えたくなったので、もう一度最初から全体を組み直すことにした。下記のようにする。

  • Game of Lifeのバックエンド機能を持つライブラリクレートを開発する
  • バックエンドなので、表示系は基本的に扱わない。ただし、サンプルとして、コマンドラインで動作するプログラムを同梱する
  • 公開できる作りにする
MasakiMasaki

crates.ioに公開するかどうかはさておき、GitHubでの公開はするつもりなので、crates.ioにクレートを公開できる状態にするには何を満たせばいいのかを少し調べた。参考にしたものは下記。

ライセンスについては、下記を参考にした。「Rustエコシステムとの最大の協調性が必要なクレートはMITとApache-2.0のデュアルライセンスにする必要がある」とのこと。

今回の場合は、MITライセンスとApache-2.0ライセンスによる公開でよい。この場合は、上記の記述からリンクのあるhttps://github.com/rust-lang/rustのLICENSE-MITとLICENSE-APACHEを持ってきてそのまま設置すればよさそう。

また、ライセンスについてCargo.tomlに下記のように追記する必要があるとのこと。参考資料はThe Cargo BookのThe license and license-file fields。

 [package]
 # ...
+license = "MIT OR Apache-2.0"
MasakiMasaki

README.mdについて調べた。

cargo publish する前に埋めておきたい Cargo.toml の項目に関するメモとRustリポジトリのREADME.mdメンテナンスを自動化するの2つを眺めた範囲では、README.mdの扱い方について下記の2つの道具があるようだった。

  • cargo-readmeを使って、ドキュメンテーションコメントからREADME.mdを自動生成する
  • rust-skepticを使って、手書きのREADME.mdなどのMarkdown内のRustコードをテストする

ドキュメンテーションコメントへの一本化をやってみたいので、cargo-readmeを試すことにした。

インストール手順は下記のみ。

cargo install cargo-readme

バイナリクレートあるいはライブラリクレートにドキュメンテーションコメントがつけてある前提で、README.mdの生成手順は下記のみでよいとのこと。

cargo readme > README.md

が、これまでに作ってきたパッケージで実行してみたら下記のエラーになった。

$ cargo readme | tee README.md
Error: missing field `path` for key `bin` at line 20 column 1

Cargo.tomlの[[bin]]のpathがデフォルト任せだと動作しないようなので、下記を追記した。

 [[bin]]
 name = "game_of_life"
+path = "src/bin/game_of_life/main.rs"
 doc = false

再実行したら、下記の結果になった。

$ cargo readme | tee README.md
# game-of-life

A simple implementation of Conway's Game of Life.

License: MIT OR Apache-2.0

cargo-readmeのUsageにあるように、下記が展開されたようだった。

  • # game-of-lifeは、Cargo.tomlの[package]のnameから展開
  • A simple ...は、ライブラリクレートのクレートルートのドキュメントから展開 (現在はこの1行だけを書いている)
  • License: ...は、Cargo.tomlの[package]のlicenseから展開

使い方の確認は、ひとまずこれでいいことにした。Cargo.tomlやドキュメンテーションコメントが更新されたらREADME.mdを自動更新できると間違いがなくてよいが、しばらくは見送っても問題ないだろう。

MasakiMasaki

一式を下記に置いて開発を開始した。

https://github.com/masaki-wk/life-backend

まず枠組みだけ作った。下記のような構成にする予定。

  • ライブラリクレートを1つ持つパッケージ
  • 下記の構造体を設ける
    • Board
      • ライフゲームの盤面の状態を表す
    • Game
      • ライフゲームの状態遷移を扱う
    • format::Plaintext
      • ライフゲーム用のファイルフォーマットPlaintextのローダー
    • format::Rle
      • ライフゲーム用のファイルフォーマットRLEのローダー
MasakiMasaki

Boardを実装した。おおよそ下記のようにした。

  • 実装
    • 値の保持にHashSet<Position>を使用 (Positionは盤面上の2次元座標値)
  • 機能
    • Board::new(): 空の盤面を構築
    • board.get(x, y): セルの状態を取得。戻り値はbool型で、trueなら生存セル、falseなら死亡セル
    • board.set(x, y, value: bool): セルの状態を変更
    • board.iter(): すべての生存セルの座標値の不変参照の列を借用イテレータで取得
    • board.into_iter(): すべての生存セルの座標値の列を所有イテレータで取得
    • board: Board = pattern.iter().collect(): 生存セルの座標値の不変参照の列を表す借用イテレータから盤面を構築
    • board: Board = pattern.iter_mut().collect(): 生存セルの座標値の可変参照の列を表す借用イテレータから盤面を構築
    • board: Board = pattern.into_iter().collect(): 生存セルの座標値の列を表す所有イテレータから盤面を構築
    • board.extend(pattern.iter()): 生存セルの座標値の不変参照の列を表す借用イテレータを盤面に追加
    • board.extend(pattern.into_iter()): 生存セルの座標値の列を表す所有イテレータを盤面に追加

以下は作業時のメモ。

MasakiMasaki

IntoIterator実装の際に、いくつかのイテレータアダプタを経てイテレータを返す関数を実装しようとして苦戦中。
書きたいコードは下記のようなもの。type IntoIter = Xxx の Xxx を書きたい。

impl<'a, IndexType> IntoIterator for &'a Plaintext<IndexType>
where
    IndexType: Integer + Copy
{
    type Item = &'a (IndexType, IndexType);
    type IntoIter = Xxx;
    fn into_iter(self) -> Self::IntoIter {
        self.contents  // self.contents: Vec<(IndexType, Vec<IndexType>)>
            .iter()
            .flat_map(|(y, xs)| xs.iter().map(|x| (*x, *y)))
    }
}

下記を読むなどしている。

MasakiMasaki

type IntoIter = Xxx の Xxx に意図的に誤った型を書いてcargo checkすると、下記のようにコンパイラが不一致になった型の情報を出力してくれた。

$ cargo check
...
error[E0308]: mismatched types
   --> src/format/plaintext.rs:257:9
    |
234 |   impl<'a, IndexType> IntoIterator for &'a Plaintext<IndexType>
    |            --------- this type parameter
...
256 |       fn into_iter(self) -> Self::IntoIter {
    |                             -------------- expected `IndexType` because of return type
257 | /         self.contents
258 | |             .iter()
259 | |             .flat_map(|(y, xs)| xs.iter().map(|x| (*x, *y)))
    | |____________________________________________________________^ expected type parameter `IndexType`, found struct `std::iter::FlatMap`
    |
    = note: expected type parameter `IndexType`
                       found struct `std::iter::FlatMap<std::slice::Iter<'_, (IndexType, std::vec::Vec<IndexType>)>, std::iter::Map<..., ...>, ...>`
            the full type name has been written to '.../target/debug/deps/life_backend-bc97f6d262301ca8.long-type-349383441391090197.txt'

target/debug/deps/life_backend-bc97f6d262301ca8.long-type-349383441391090197.txt には、下記が書いてあった。

std::iter::FlatMap<std::slice::Iter<'_, (IndexType, std::vec::Vec<IndexType>)>, std::iter::Map<std::slice::Iter<'_, IndexType>, [closure@src/format/plaintext.rs:259:47: 259:50]>, [closure@src/format/plaintext.rs:259:23: 259:32]>

構造を読みやすくすると、下記になる。

std::iter::FlatMap<
    std::slice::Iter<'_, (IndexType, std::vec::Vec<IndexType>)>,
    std::iter::Map<
        std::slice::Iter<'_, IndexType>,
        [closure@src/format/plaintext.rs:259:47: 259:50]
    >,
    [closure@src/format/plaintext.rs:259:23: 259:32]
>

が、下記あたりを読むと「クロージャの型はコンパイラしか知らない(よって手で書けない)」ということなので、何らかの対策をしないと力技で書くことはできないようだ。

MasakiMasaki

format::Plaintextを実装した。
new(read)のreadにファイルやバイト列を与えて読み込ませて初期化すると、.iter()で生存セルの位置を順に取り出せるようにした。おおよそ下記のように使う。

let pattern = "\
    !Name: Glider\n\
    .O\n\
    ..O\n\
    OOO\n\
";
let parser = Plaintext::<i16>::new(pattern.as_bytes())?;
let mut iter = parser.iter();
assert_eq!(iter.next(), Some((1, 0)));
assert_eq!(iter.next(), Some((2, 1)));
assert_eq!(iter.next(), Some((0, 2)));
assert_eq!(iter.next(), Some((1, 2)));
assert_eq!(iter.next(), Some((2, 2)));
assert_eq!(iter.next(), None);

構造体のフィールドは下記の構成とした。

  • name: String
    • パターン先頭行の名前の情報を保持
  • comments: Vec<String>
    • コメント行の情報を保持 (何もなければ空)
  • contents: Vec(IndexType, Vec<IndexType>)
    • パターン本体の行ごとの情報を保持。1行の情報は、Y座標値と、生存セルのX座標値のベクタ。例えば上に書いたグライダーなら、下記のようになる
      • self.contents[0] = vec![0, vec![1]]
      • self.contents[1] = vec![1, vec![2]]
      • self.contents[2] = vec![2, vec![0, 1, 2]]

以下は作業時のメモ。

  • std::io::Readトレイトを使えば、Fileとバイト列(&[u8])の両方をまとめて扱える
  • 自作の型に機能を足すときは、まず既存のトレイトの機能かどうかを考える。既存のトレイトがあるならそれを実装する。既存のトレイトがない場合のみ、独自のメソッドとして実装する
    • 例えばx.into_iter()を実装するなら、それをimpl X { pub fn into_iter() { ... } }として実装するのではなく、impl IntoIterator for X { fn into_iter() { ... } }として実装する

.iter()は実装したものの、impl IntoIterator for Plaintext と impl IntoIterator for &Plaintext は実装できていない。
self.contentsから.iter()の戻り値の生成にイテレータアダプタを使っていて、その戻り値の型を関連型に書けていないため。

.iter()の実装には、下記のようにimpl Traitを使った。

pub fn iter(&self) -> impl Iterator<Item = (IndexType, IndexType)> + '_ {
  self.contents.iter().flat_map(|(y, xs)| xs.iter().map(|x| (*x, *y)))
}
MasakiMasaki

Gameを実装した。

あらかじめ用意したBoardをnew()に与えて構築し、.update()で状態を更新するという使い方にした。例えば下記のとおり。

fn main() {
    let pattern = [(1, 0), (2, 1), (0, 2), (1, 2), (2, 2)]; // Glider pattern
    let steps = 4;
    let board: Board = pattern.iter().collect();
    let mut game = Game::new(board);
    for i in 0..=steps {
        if i != 0 {
            game.update();
        }
        println!("Generation {i}:");
        println!("{game}");
    }
}

実行結果は下記のようになる。

Generation 0:
.O.
..O
OOO

Generation 1:
O.O
.OO
.O.

Generation 2:
..O
O.O
.OO

Generation 3:
O..
.OO
OO.

Generation 4:
.O.
..O
OOO

実装の要点は、ある盤面の状態から1つ次の世代の盤面を求める下記の next_board という関数。

fn next_board(board: &Board<IndexType>) -> Board<IndexType>
where
    IndexType: Copy + PartialOrd + Add<Output = IndexType> + Sub<Output = IndexType> + One + Bounded + ToPrimitive,
{
    let survive_caondidates = board.iter();
    let birth_candidates_multiset = board
        .iter()
        .flat_map(|&(x, y)| Self::neighbour_positions(x, y))
        .filter(|&(x, y)| !board.get(x, y));
    let birth_candidates_uniquified: HashSet<(IndexType, IndexType)> = birth_candidates_multiset.collect();
    let mut next_board = Board::new();
    next_board.extend(survive_caondidates.filter(|&&(x, y)| {
        let count = Self::live_neighbour_count(board, x, y);
        count == 2 || count == 3
    }));
    next_board.extend(birth_candidates_uniquified.into_iter().filter(|&(x, y)| {
        let count = Self::live_neighbour_count(board, x, y);
        count == 3
    }));
    next_board
}

この関数内の処理の流れは下記のとおり。n は現在の盤面の生存セル数。

  1. 次の世代でも生存するセルの候補を survive_caondidates に保持する
    • これは単に現在の盤面の生存セルの情報に別名をつけただけである
    • 実体はイテレータなので、この段階では計算を実行しない
  2. 次の世代で新たにセルが誕生する(かつ現在は生存セルがない)場所の候補を求め、birth_candidates_multiset に保持する
    • 現在の盤面の生存セルの位置情報を、各位置ごとに隣接セルの位置情報(合計8セル; Moore neighbourhoodに従う)に展開し、生存セルがいる位置を取り除くことで求める
    • リストには同じ位置情報が複数含まれることがある
    • これも実体はイテレータなので、この段階では計算を実行しない
  3. birth_candidates_multiset の内容から重複を排除したものを求め、birth_candidates_uniquified に保持する
    • 実体はHashSet。HashSetは重複した値の追加を無視する: これにより重複排除が実現される
    • この段階で birth_candidates_multiset を消費し、実際に計算を行う (ループその1; 最内周ループは後述の下位関数neighbour_positions)
    • 時間計算量に対して支配的な操作は、現在の盤面に対する birth_candidates_multiset によるクエリ
      • オーダーは O(n)
      • その回数は、n \times 8 になる (8はMoore neighbourhoodのセル数)
      • 盤面の実装はHashSetなので、1回当たりのクエリのコストは O(1) の定数時間
    • なお、ソートしてから重複排除をする方法だと O(n\ log\ n) なので効率が悪い
  4. 次状態の盤面 next_board を、まず空の状態で構築する
  5. survive_caondidates の候補から、実際に生存するセルを選別し、next_board に追加する
    • next_board.extend(iter) で生存セルの情報を追加する (BoardはExtendトレイトを実装しているため、この操作を行える)
    • ループその2。支配的な操作は先ほどと同じクエリで、その回数は n \times 8 になる
  6. burth_caondidates_uniquified の候補から、実際に誕生するセルを選別し、next_board に追加する
    • ループその3。クエリ回数は、候補位置 x 8 になる。つまり、最悪ケースでは n \times 8 \times 8 になる。ただし、段階3の重複削除があるため、実際の値はそこまで大きくならない

全体の時間計算量のオーダーは O(n m^2) である(m は1セル当たりの隣接セル数)。m はMoore neighbourhoodを使う場合には8固定なので、実際の時間計算量オーダーは O(n) になる。

next_board 関数が呼び出している下位関数2つ: neighbour_positions と live_neighbour_count の実装は下記のとおり。

  • neighbour_positions は、Moore neighbourhoodの8セルの位置をその場で生成したイテレータとして返す
  • live_neighbour_count は、neighbour_positions が返す位置情報のうち、生存セルが置かれている位置のみを抽出してその個数を返す
fn neighbour_positions(x: IndexType, y: IndexType) -> impl Iterator<Item = (IndexType, IndexType)>
where
    IndexType: Copy + PartialOrd + Add<Output = IndexType> + Sub<Output = IndexType> + One + Bounded + ToPrimitive,
{
    let min = IndexType::min_value();
    let max = IndexType::max_value();
    let one = IndexType::one();
    let x_start = if x > min { x - one } else { x };
    let x_stop = if x < max { x + one } else { x };
    let y_start = if y > min { y - one } else { y };
    let y_stop = if y < max { y + one } else { y };
    range_inclusive(y_start, y_stop)
        .flat_map(move |v| range_inclusive(x_start, x_stop).map(move |u| (u, v)))
        .filter(move |&(u, v)| u != x || v != y)
}

fn live_neighbour_count(board: &Board<IndexType>, x: IndexType, y: IndexType) -> usize
where
    IndexType: Copy + PartialOrd + Add<Output = IndexType> + Sub<Output = IndexType> + One + Bounded + ToPrimitive,
{
    Self::neighbour_positions(x, y).filter(|&(u, v)| board.get(u, v)).count()
}

今後の話として、いずれ確かめたいことは下記。

  • 現在は、毎回新規に新盤面を構築し、それを構築し終わると旧盤面を廃棄している。メモリ管理的には効率が悪い。領域を再利用するようにしたら、どのぐらい時間を節約できるのか?
  • 誕生セル候補の重複を排除するために専用のHashSetを使っているが、実際には重複したまま新たな盤面に登録していっても計算結果は変わらない(盤面もHashSetなので、重複登録が無視されるため)。事前に重複排除用HashSetを使うのと、使わないのとで、どちらがどのくらい速いのか?

以下は作業時のメモ。

  • neighbour_positions内のクロージャにmoveを使う必要があった。クロージャは、何も指定しないと環境を不変参照または可変参照でキャプチャするが、moveを付けると所有権を奪って値でキャプチャする
MasakiMasaki

以前に実装したものと新規に実装し直したものの処理性能を比較した。

手段として、Criterion.rsを用いた下記3通りのベンチマークを使用した。

  • Blinkerを1,000世代まで進める関数 (blinker-1k)
    • 周期2のオシレータパターン(周期ごとにまったく同一の状態に戻るパターン)。周期全体でのbounding boxは3 x 3、人口(population)は常に3
  • [moldon30p25](https://conwaylife.com/wiki/30P25#LCM_oscillators の p100 with mold)を1,000世代まで進める関数 (moldon30p25-1k)
    • 周期100のオシレータパターン。周期全体でのbounding boxは20 x 20、人口は42から78(カタログ参照)
  • Centinalを1,000世代まで進める関数 (centinal-1k)
    • 周期100のオシレータパターン。周期全体でのbounding boxは52 x 17、人口は70から142(カタログ参照)

結果は下記のとおり。

ベンチマーク 旧実装 新実装 旧対新の時間倍率
blinker-1k 299.04 us 4.8284 ms 16.14
moldon30p25-1k 5.2367 ms 86.016 ms 16.43
centinal-1k 10.979 ms 139.64 ms 12.72

実行時間差の主な要因は、新旧実装でのデータ構造と状態遷移の方式の違いによる。それぞれ下記のようになっている。

  • 旧実装
    • 盤面をboolの配列で表現 (論理的な2次元配列を1次元配列にマッピング)
    • 時間計算量オーダーは、盤面のセル数を n とすると O(n)
  • 新実装
    • 生存セルの2次元座標をHashSetに登録して表現
    • 時間計算量オーダーは、平均人口を p とすると O(p)
    • 旧実装に対する新実装の時間計算量オーダーの比率は O(p) / O(n)。よって両者の実行時間比は平均人口密度の比に比例する

各パターンの数値情報は下記のようになっている。

ベンチマーク 盤面セル数 最少人口 最多人口 人口中央値 / セル数 旧対新の時間倍率
blinker-1k 9 3 3 0.3333 16.14
moldon30p25-1k 400 42 78 0.1500 16.43
centinal-1k 884 70 142 0.1199 12.72

moldon30p25-1k と centinal-1k の「人口中央値 / セル数」と「旧対新の時間倍率」は、だいたい比例していることがわかる(サイズが小さすぎる blinker-1k は無視)。
人口密度の平均ではなく中央値で見ているのでやや大まかだが、人口密度が1%よりも高いと旧実装のほうが速く、低いと新実装のほうが速くなるようだ。

MasakiMasaki

LifeWikiのOscillatorやCategory: Oscillators with specific populationを眺めて、人口密度の低いオシレータパターンをいくつか探してきた。

  • Nihonium
    • 周期: 113
    • bounding box: 58 x 37 (盤面セル数: 2,146)
    • 人口: 最少106、最多224 (カタログ参照)
    • 人口中央値 / 盤面セル数 = 0.0769
  • Star gate
    • 周期: 60
    • bounding box: 155 x 126 (盤面セル数: 19,530)
    • 人口: 最少1,071、最多1,191 (カタログ参照)
    • 人口中央値 / 盤面セル数 = 0.0579
  • p256glidergunwithboatbits
    • Period-256 glider gunのページ内に載っている亜種で、Period-256 glider gunにboat-bitをいくつか足して完全なオシレータにしたもの
    • 周期: 512
    • bounding box: 49 x 49 (盤面セル数: 2,401)
    • 人口: 最少100、最多173 (上記リンク先のページ内のパターンをLifeViewerで実行して確認した)
    • 人口中央値 / 盤面セル数 = 0.0569

1,000世代まで進めたときの、新旧実装での処理時間測定結果は下記のとおり。
(ベンチマークの整備まではしなかったので、timeコマンドで1回のみの簡易計測)

パターン 旧実装 新実装 新/旧 人口中央値 / 盤面セル数
Nihonium 0.09 s 0.25 s 2.778 0.0769
Star gate 0.27 s 1.49 s 5.519 0.0579
p256glidergunwithboatbits 0.09 s 0.21 s 2.333 0.0569

これよりも人口密度の低いパターンはなかなかなさそうで、試したどのパターンでも旧実装のほうが高性能という結果になった。
新実装をもっと高性能にしたいな。

MasakiMasaki

新実装の実行時間の内訳をflamegraphで計測した。使ったパターンはCentinal、世代は1,000世代までとした。結果の要点は下記のとおり。

  • Game::next_boardが実行時間全体の93.37%を占める。その内訳は下記の3つ
    • 誕生セル候補位置の重複を排除するためのHashSetのcollect操作: 36.46% (実行時間全体に対して)
    • 生存候補から実際に生存するセルを選別してBoardへextendで足す操作: 18.23%
    • 誕生候補から実際に誕生するセルを選別してBoardへextendで足す操作: 38.67%

総実行時間が0.18秒なので、比率から時間を求めると下記のようになる。

項目 時間 [sec] 比率 [%]
誕生候補重複排除 0.0656 36.46
生存候補選別 0.0328 18.23
誕生候補選別 0.0696 38.67

別のデータだとどうなるのか確かめておくため、Star gateの1,000世代でも同様の計測をした。結果は下記のとおり。

項目 時間 [sec] 比率 [%]
誕生候補重複排除 0.4696 31.52
生存候補選別 0.2762 18.54
誕生候補選別 0.6818 45.76

パターンの差異で多少比率が異なるが、傾向にそれほど違いは見られないので、ある1つのパターンの実行時間を見ながらソースコードを変更して性能向上させればよさそう。

MasakiMasaki

いくつかの変更をして処理時間短縮を図った。行った変更は下記のとおり。

  1. メモリの再割り当てを防止するために、誕生セル候補用のHashSetと新旧盤面を開放せず使いまわすよう変更
  2. 隣接セルをイテレータ経由で走査する際の盤面末端かどうかの判定を、必要な場合と不要な場合とにコードを分離して、どちらを使うのかをループ開始前に選択 (1のものに追加)

Centinalを1,000世代まで進める関数 centinal-1k でのベンチマーク結果は下記のとおり。性能は大して上がらなかった。

対象 実行時間 変更前に対する比率
変更前 137.67 ms 100.0 %
1. メモリ再割り当てを排除 129.93 ms 94.4 %
2. 盤面末端判定の要/不要のループを分離 119.77 ms 87.0 %

2に対するflamegraphによるプロファイル結果は、下記のようになった。

項目 比率 [%]
状態更新関数全体 92.41
- 誕生候補重複排除 25.32
- - 中間HashSetへの重複排除付きの要素追加(insert) 9.49
- - 旧盤面のHashSetへの問い合わせ(contains) 11.39
- - ほか 4.44
- 生存候補選別 16.46
- - 旧盤面のHashSetへの問い合わせ(contains) 13.92
- - ほか 2.54
- 誕生候補選別 47.47
- - 旧盤面のHashSetへの問い合わせ(contains) 37.97
- - ほか 9.50
- ほか 3.16

旧盤面のHashSetへの問い合わせ(contains)と、中間HashSetへの重複排除付きの要素追加(insert)を合わせると、全体の72.77%を占めることがわかる。それ以外のものは19.64%しかない。
さらに性能を上げるには、これらの回数の削減方法を考えるのがよく、ほかの方法ではあまり効果がなさそうだ。

MasakiMasaki

1つ前のコメントの「盤面末端判定の要/不要のループの分離」は、ソースコードを複雑にした割に性能向上の程度が低かったため、元に戻した。

また、もうひとつ試してみた。現在は、状態を更新する際に下記の流れとしているが:

  1. 次の世代で新たにセルが誕生する箇所の候補を、一時的なHashSetに保持 (HashSetへ登録すると重複が排除される)
  2. 現在生存しているセルの各位置について、次の世代でも生存するセルを求め、新たな盤面へと追加
  3. 新たにセルが誕生する箇所の候補の各位置について、実際にセルが誕生する箇所を求め、新たな盤面へと追加

1をやめて、重複があるままの候補を3に流し込むと、実行時間が40%ほど長くなってしまった。
重複を1つ排除する操作はHashSetに対する1回のinsertで済むが、余分な1つの重複セルに対する誕生確認操作には周囲8セルのクエリ(contains)が必要で、後者のほうが高コストということだろう。

MasakiMasaki

HashSetに対する操作の効率を上げるために、下記の変更を行った。実行時間が10%ほど短縮された。

  • 変更前
    1. 誕生セル候補を、一時的なHashSetに追加する (追加時に重複が排除される)
    2. 誕生セルの候補から、実際にセルが誕生するものを選別しながら新盤面に追加する
  • 変更後
    1. 空の新盤面に、誕生セル候補をいったん直接追加する
    2. 新盤面内の誕生セルの候補から、実際にはセルが誕生しないものをretainで削除

前者は2段階目のinsertの際に余計な重複チェックが入るが、後者は見つけたものを消すだけなので無駄がない。
ただ、retainの時間計算量は実装都合で O(len) ではなく O(capacity) とのことなので、capacityを大きくしてしまうとかえって性能が低下してしまいそうだ。

ここまでのcentinal-1k でのベンチマークの実行時間の変遷は、まとめると下記のとおり。

対象 実行時間 変更前に対する比率
変更前 137.67 ms 100.0 %
1. メモリ再割り当てを排除 129.93 ms 94.4 %
2. fnvクレートのHasherを導入 99.620 ms 72.4 %
3. retainを導入 88.946 ms 64.6 %

なお、3の後に「insertをhashbrownのinsert_unique_uncheckedで置換」を試してみたが(3同様にinsert時の余計な重複チェックがなくなる)、ほとんど性能が上がらなかった。
3のままでよいことにした。

MasakiMasaki

RLEファイルを扱うformat::Rleを実装した。
Plaintextの際と同様に、new(read)のreadにファイルやバイト列を与えて読み込ませて初期化すると.iter()で生存セルの位置を順に取り出せるようにした。

ファイル書式を正確に扱うためにあれこれ細かい工夫をしたが、Rustとしての特記事項は特になかった気がする。慣れてきたということかもしれない。

MasakiMasaki

下記を参考に、生存セルの並びの情報からformat::Plaintextを生成できるようにした。
手段として、typestateによるBuilderパターンを使用した(PlaintextBuilderという名前で実装)。

下記のようなコードで、生存セルの並びからPlaintextを生成できる。

use life_backend::format::PlaintextBuilder;

fn main() {
    let pattern = [(1, 0), (2, 1), (0, 2), (1, 2), (2, 2)];
    let name = "Glider";
    let target = pattern.iter()
        .collect::<PlaintextBuilder>()
        .name(name)
        .build();
    println!("{target}");
}

$ cargo run
!Name: Glider
.O.
..O
OOO
  • 機能
    • 生存セルのイテレータの並びに .collect::<PlaintextBuilder>() を適用すると、PlaintextBuilderの値が生成される
    • PlaintextBuilderの値に .build() を適用すると、Plaintextの値が生成される
    • PlaintextBuilderの値には、任意で .name(str: &str) を適用できる。これを行うと、.build() で生成したPlaintextの値に name() が設定される
    • .name() 同様に、PlaintextBuilderの値には任意で .comment(str: &str) を適用できる。複数行のコメントを設定する場合は、引数strに改行を含める
    • .name() と .comment() は、1回のみ適用できる。2回以上適用しようとするとコンパイルエラーになる (typestateを使うことで、実行時エラーではなくコンパイル時エラーにしている)
  • その他の実装メモ
MasakiMasaki

以前に「ループ記述からイテレータパターンに変えたいが、処理内に早期リターンを使っていて、書き方がわからない」と思ったことがあったが、早期リターンの目的がエラー処理であれば、下記のような手段が用意されているようだ。

map() などで Result<T, _> を返し、collect() を使って Result<Vec<T>, _> などに変換する

例えば下記のようなことができる。
(Fail the entire operation with collect() - Rust by Exampleから引用)

fn main() {
    let strings = vec!["tofu", "93", "18"];
    let numbers: Result<Vec<_>, _> = strings
        .into_iter()
        .map(|s| s.parse::<i32>())
        .collect();
    println!("Results: {:?}", numbers);
}

上記では、 map() のクロージャから Result<i32, _> を返し、その後の collect() で Vec<Result<i32, _>> ではなく Result<Vec<i32>, _> を返している。
これは、Result<T, E> が FromIterator を実装していることによる: これにより、 collect() は Vec<Result<T, E>> ではなく Result<Vec<T>, E> を返すことができる。
Result の from_iter() は、入力イテレータから受け取った値が Err であれば、イテレータからの値の取得を止めて Err を返す。

try_fold() で Result<T, _> 型の値に集約する

例えば下記のようなことができる。

fn main() {
    let strings = vec!["tofu", "93", "18"];
    let sum_of_numbers: Result<_, std::num::ParseIntError> = strings
        .into_iter()
        .try_fold(0, |mut acc, s| {
            let n = s.parse::<i32>()?;
            acc += n;
            Ok(acc)
        });
    println!("Results: {:?}", sum_of_numbers);
}

上記の try_fold() のクロージャの戻り値は Result<i32, _> で、失敗があれば Err を返す。 try_fold() は、クロージャからの戻り値が Err であれば、イテレータからの値の取得を止めて Err を返す。

MasakiMasaki

異なるルールを扱えるようにして、RLEファイル内のルール文字列を読み込むようにした。また、後述の資料を参考に、下記のルールのパターンファイルとテストを足した。

参考にした資料は下記のとおり。

MasakiMasaki

実装は継続しているが、習作を通してRustの技術を身につける側面は扱いが軽くなってきている感があるので、このスクラップはここまでにしよう。
2023-02-27の時点での残件と現状は下記のとおり。

  • Rustの学習として
    • ある程度使えるようになったもの
      • トレイト: 標準が提供するものはいくつか使えるようになった。自作は触り程度
      • ジェネリック型: ある程度使えるようになった
      • マクロの作成: macro_rules!で簡単なマクロを書いた
    • 今も扱った経験がないもの
      • スマートポインタ
      • 並行性
    • unsafe
  • Game of Lifeの実装として
    • 実装済み
      • 基本以外のルールへの対応
    • 非対応
      • Torus以外の盤面末端処理: 手を付けていない。LifeWikiなどを見ていて、あまり必要性を感じない
      • 標準出力以外の表示手段への対応 (2023-02-27の時点で、対応しないことにしている)
このスクラップは2023/04/29にクローズされました