面试题：Rust结构体复合运算符重载及性能优化

Question

定义一个Rust结构体 `Matrix` 表示二维矩阵，包含一个 `Vec<Vec<i32>>` 类型的字段存储矩阵数据。重载复合赋值运算符 `+=`，实现矩阵的加法（即对应位置的元素相加）。同时，分析在大规模矩阵运算时，当前实现可能存在的性能问题，并提出至少两种优化策略。最后，使用 `benchmark` 测试优化前后的性能差异。

Answer 1

struct Matrix {
    data: Vec<Vec<i32>>,
}

impl std::ops::AddAssign for Matrix {
    fn add_assign(&mut self, other: Matrix) {
        for (i, row) in self.data.iter_mut().enumerate() {
            for (j, cell) in row.iter_mut().enumerate() {
                *cell += other.data[i][j];
            }
        }
    }
}

大规模矩阵运算时的性能问题

1. 内存访问模式：Vec<Vec<i32>> 这种二维结构在内存中不是连续存储的，会导致缓存不友好，随机访问性能较差。
2. 迭代开销：嵌套的 for 循环在大规模矩阵运算时，迭代的开销较大。

优化策略

1. 使用一维数组存储：将二维矩阵数据存储在一个一维 Vec<i32> 中，通过计算偏移量来访问对应元素，提高内存连续性，增强缓存利用率。
2. 并行计算：利用多线程并行计算矩阵加法，将矩阵划分成多个部分，每个线程负责一部分的加法运算。

Benchmark测试

首先添加 cargo-bench 依赖，在 Cargo.toml 中添加：

[dev-dependencies]
bencher = "0.5.1"

编写基准测试代码：

#[cfg(test)]
mod benches {
    use super::*;
    use bencher::Bencher;

    #[bench]
    fn bench_matrix_addition(b: &mut Bencher) {
        let mut matrix1 = Matrix {
            data: vec![vec![1; 1000]; 1000],
        };
        let matrix2 = Matrix {
            data: vec![vec![1; 1000]; 1000],
        };
        b.iter(|| matrix1 += matrix2.clone());
    }
}

优化后：

struct MatrixOptimized {
    data: Vec<i32>,
    rows: usize,
    cols: usize,
}

impl MatrixOptimized {
    fn new(rows: usize, cols: usize) -> Self {
        MatrixOptimized {
            data: vec![0; rows * cols],
            rows,
            cols,
        }
    }

    fn get_index(&self, row: usize, col: usize) -> usize {
        row * self.cols + col
    }
}

impl std::ops::AddAssign for MatrixOptimized {
    fn add_assign(&mut self, other: MatrixOptimized) {
        for i in 0..self.data.len() {
            self.data[i] += other.data[i];
        }
    }
}

#[cfg(test)]
mod benches {
    use super::*;
    use bencher::Bencher;

    #[bench]
    fn bench_matrix_addition_optimized(b: &mut Bencher) {
        let mut matrix1 = MatrixOptimized::new(1000, 1000);
        let matrix2 = MatrixOptimized::new(1000, 1000);
        b.iter(|| matrix1 += matrix2.clone());
    }
}

运行 cargo bench 即可看到优化前后的性能差异。