PythonのライブラリをC++で作成する（4）

なぜC++で書いたライブラリは遅いのでしょう。
Pythonのコードは、

    for i in range(H):
        for j in range(W):
            C[i][j] = int(sum(A[i][k] * B[k][j] for k in range(M)) % D)
    return C

C++のコードは、

    for(size_t i = 0U; i < H; ++i) {
        for(size_t j = 0U; j < W; ++j) {
            for(size_t k = 0U; k < M; ++k)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % D;
        }
    }

Pythonのコードは総和を取ったあとにDの剰余を取っていますが、C++のコードは掛け算して足し算するたびにDの剰余を取っています。
なぜこうなっているかというと、競技プログラミングではDが32ビットに近い数が選ばれるため、すぐに64ビットではオーバーフローしてしまうからです。一方、Pythonでは多倍長整数に移行するため、オーバーフローを考慮しなくてよく、また多倍長整数の加算は64ビット整数の除算よりずっと速いです。
C++では64ビットより長い整数を使えばよいですが、幸いにしてGCCには__int128という128ビット整数があり、これを利用すれば速くなります。

PyObject *mul(PyObject *self, PyObject *args) {
    ...
    Matrix  C = mul_core128(A, B, D);
    return make_python_matrix(C);
}

Matrix mul_core128(const Matrix& A, const Matrix& B, long D) {
    const size_t    H = A.size();
    const size_t    M = B.size();
    const size_t    W = B.front().size();
    
    Matrix  C(H, Vec(W));
    for(size_t i = 0U; i < H; ++i) {
        for(size_t j = 0U; j < W; ++j) {
            __int128    e = 0;
            for(size_t k = 0U; k < M; ++k)
                e += A[i][k] * B[k][j];
            C[i][j] = (long)(e % D);
        }
    }
    return C;
}

実行してみましょう。

1134
256330968
30.565128803253174

変更前に対して6.8倍速くなりました。
速度アップの方法がもう一つあります。