矩阵与向量相乘中的时间常数

发表于 分类于

以下代码中，mul1 是行向量乘矩阵，mul2 是矩阵乘列向量。

可以看出，两段代码的内存访问都是连续的，那为什么 mul2 会比 mul1 慢 3 倍？

1
2
3
4
5
6
7
8
9
10
11
12
using Vector = int[MAXN];
using Matrix = int[MAXN][MAXN];
void mul1(int n, const Vector& a, const Matrix& b, Vector& ans) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans[j] = (ans[j] + (long long)a[i] * b[i][j]) % MOD;
}
void mul2(int n, const Matrix& a, const Vector& b, Vector& ans) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans[i] = (ans[i] + (long long)a[i][j] * b[j]) % MOD;
}

原因在于， mul1 中每次循环修改的是 ans[j]，其中 j 是内层循环变量，所以每次执行时 ans[j] 都是不同的变量，运算时不存在数据依赖，现代超标量 CPU 可以充分进行并发运算。

而 mul2 中每次循环修改的是 ans[i]，其中 i 是外层循环变量，导致连续 n 次循环中 ans[i] 都是同一个变量，每次运算都依赖上一次运算结果，无法同时执行。

事实上，虽然在现代编译器的优化下，对常数取模可以不使用 div 指令，但取模的开销仍然不小。

如果将以上代码中的 % MOD 去掉，两个函数的效率就一样了，可见让 mul2 变慢的主要原因是 ans[i] 参与了取模，导致每次取模运算必须顺序执行。

那么我们可以只对 (long long)a[i][j] * b[j] 取模，保证复杂运算之间不存在数据依赖，也可以让 CPU 充分并发。

也就是将 mul2 改成这样：

1
2
3
4
5
6
7
8
void mul2(int n, const Matrix& a, const Vector& b, Vector& ans) {
    for (int i = 1; i <= n; i++) {
        long long sum = ans[i];
        for (int j = 1; j <= n; j++)
            sum += (long long)a[i][j] * b[j] % MOD;
        ans[i] = sum % MOD;
    }
}

效率就和 mul1 一样了。