rust - 什么优化让我的 Rust 程序变得如此快？

Question

因为无法解决数独难题而感到沮丧，我很快拼凑了一个简单的递归回溯求解器:

fn is_allowed(board: &[[u8; 9]; 9], row: usize, col: usize, x: u8) -> bool {
    for i in 0..9 {
        if board[row][i] == x {
            return false;
        }
        if board[i][col] == x {
            return false;
        }
    }

    let r = row - (row % 3);
    let c = col - (col % 3);
    for i in r..(r + 3) {
        for j in c..(c + 3) {
            if board[i][j] == x {
                return false;
            }
        }
    }

    true
}

fn solve(board: &mut [[u8; 9]; 9]) -> bool {
    for i in 0..9 {
        for j in 0..9 {
            if board[i][j] == 0 {
                for x in 1..=9 {
                    if is_allowed(board, i, j, x) {
                        board[i][j] = x;
                        if solve(board) {
                            return true
                        }
                        board[i][j] = 0;
                    }
                }
                return false;
            }
        }
    }
    true
}

fn main() {
    let mut board = [
        [ 0, 0, 8, 0, 0, 4, 0, 0, 0 ],
        [ 0, 0, 0, 0, 0, 0, 0, 0, 7 ],
        [ 0, 0, 6, 0, 0, 0, 0, 1, 0 ],
        [ 0, 0, 0, 0, 0, 0, 5, 0, 9 ],
        [ 0, 0, 0, 6, 0, 0, 0, 0, 0 ],
        [ 0, 2, 0, 8, 1, 0, 0, 0, 0 ],
        [ 9, 4, 0, 0, 0, 0, 0, 0, 0 ],
        [ 0, 0, 0, 0, 0, 0, 1, 8, 0 ],
        [ 0, 0, 7, 0, 0, 5, 0, 0, 0 ],
    ];

    if solve(&mut board) {
        for i in 0..9 {
            println!("{:?}", board[i]);
        }
    } else {
        println!("no solution");
    }
}

在没有优化的情况下运行时(cargo run)，运行时间超过 6 分钟。

在优化运行时(cargo run --release)，运行大约需要 7 秒。

什么优化导致了这种差异？

Answer 1

如果不分析生成的程序集很难确定，但我认为它与这些优化的组合有关:

• 循环展开:编译器知道每个循环运行 8 次，因此它不是循环而是将循环体编译 8 次，并将索引作为常量。这就是为什么上面评论中@MatthieuM 的godbold 链接这么长。
• 范围检查:由于 i、j 和 k 现在是常量(在展开的循环中)并且数组的大小已知，编译器将忽略所有范围检查。
• 函数内联。

事实上，每次你写board[i][j]时:

• 在 Debug模式下，您调用两个库函数来执行检查和计算。
• 在 Release模式下，此类代码的每个实例都只是对堆栈中固定偏移量的读取或写入。