Какая оптимизация делает мою программу ржавчины намного быстрее?

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 раз с индексом в виде константы.Вот почему ссылка godbold от @MatthieuM в комментариях выше настолько длинна.
• Проверка диапазона: поскольку i, j и k теперь являются константами (вразвернутых циклов) и массивы имеют известный размер, компилятор пропустит все проверки диапазона.
• Функция встраивания.

Фактически, каждый раз, когда вы пишете board[i][j]:

• В режиме отладки вы вызываете две библиотечные функции, которые выполняют проверки и вычисления.
• В режиме выпуска каждый экземпляр такого кода представляет собой просто чтение или запись с фиксированным смещением в стеке.