请教一个 C++性能问题

[wisefree]

对于两个转置运算，两种的性能明显不一样，是为什么呢？

我电脑的输出是：

0.0473308

0.0265206

#include <iostream>
#include <chrono>


int main(void)
{
    int I = 100;
    int J = 200;
    int K = 300;
    
    int idealI = 105;

    // i j k
    int* arr = new int[I * J * K];
    for (int i = 0; i < I; i++) {
        for (int j = 0; j < J; j++) {
            for (int k = 0; k < K; k++) {
                arr[i * (K * J) + j * K + k] = k;
            }
        }
    }

    // k j i
    float* transArr = new float[idealI * J * K];

    auto startTime = std::chrono::steady_clock::now();

    for (int i = 0; i < I; i++) {
        for (int j = 0; j < J; j++) {
            for (int k = 0; k < K; k++) {
                transArr[k * (J * I) + j * I + i] = arr[i * (K * J) + j * K + k] * 0.1f;
            }
        }
    }

    auto endTime = std::chrono::steady_clock::now();

    std::chrono::duration<double> diffTime = endTime - startTime;

    std::cout << diffTime.count() << std::endl;

    startTime = std::chrono::steady_clock::now();

    for (int i = 0; i < I; i++) {
        for (int j = 0; j < J; j++) {
            for (int k = 0; k < K; k++) {
                transArr[k * (J * idealI) + j * idealI + i] = arr[i * (K * J) + j * K + k] * 0.1f;
            }
        }
    }

    endTime = std::chrono::steady_clock::now();

    diffTime = endTime - startTime;

    std::cout << diffTime.count() << std::endl;

    delete[] arr;
    delete[] transArr;

    return 0;
}

根据大家的解释，我重新写了一个例子，由于 V2EX 附言的长度有限制，所以把 func1 和 fun2 分开在两个附言种

func1 比 func2 快了 3 倍左右


``` c++
#include <iostream>
#include <chrono>


int I = 360;
int J = 280;
int K = 3;

int idealI = 512;

void func1(int* arr, float* transArr)
{
auto startTime = std::chrono::steady_clock::now();

for (int i = 0; i < I; i++) {
for (int j = 0; j < J; j++) {
for (int k = 0; k < K; k++) {

int realIdx = (i * (K * J) + j * K + k) * 2;
int imagIdx = realIdx + 1;

int transRealIdx = (k * (J * I) + j * I + i) * 2;
int transImagIdx = transRealIdx + 1;

transArr[transRealIdx] = arr[realIdx] * 0.1f;
transArr[transImagIdx] = arr[imagIdx] * 0.1f;
}
}
}

auto endTime = std::chrono::steady_clock::now();

std::chrono::duration<double> diffTime = endTime - startTime;

std::cout << diffTime.count() << std::endl;
}

int main(void)
{

// i j k
int* arr = new int[I * J * K * 2];
for (int i = 0; i < I; i++) {
for (int j = 0; j < J; j++) {
for (int k = 0; k < K; k++) {
int realIdx = (i * (K * J) + j * K + k) * 2;
int imagIdx = realIdx + 1;

arr[realIdx] = k;
arr[imagIdx] = k;
}
}
}

// k j i
float* transArr = new float[idealI * J * K * 2];

for (int i = 0; i < idealI; i++) {
for (int j = 0; j < J; j++) {
for (int k = 0; k < K; k++) {
int realIdx = (i * (K * J) + j * K + k) * 2;
int imagIdx = realIdx + 1;

transArr[realIdx] = 0;
transArr[imagIdx] = 0;
}
}
}

func1(arr, transArr);


delete[] arr;
delete[] transArr;

return 0;
}

```

#include <iostream> #include <chrono>

int I = 360; int J = 280; int K = 3;

int idealI = 512;

void func2(int* arr, float* transArr) { auto startTime = std::chrono::steady_clock::now();

for (int i = 0; i < I; i++) {
    for (int j = 0; j < J; j++) {
        for (int k = 0; k < K; k++) {
            int realIdx = (i * (K * J) + j * K + k) * 2;
            int imagIdx = realIdx + 1;

            int transRealIdx = (k * (J * idealI) + j * idealI + i) * 2;
            int transImagIdx = transRealIdx + 1;

            transArr[transRealIdx] = arr[realIdx] * 0.1f;
            transArr[transImagIdx] = arr[imagIdx] * 0.1f;
        }
    }
}

auto endTime = std::chrono::steady_clock::now();

std::chrono::duration<double> diffTime = endTime - startTime;

std::cout << diffTime.count() << std::endl;

}

int main(void) {

// i j k
int* arr = new int[I * J * K * 2];
for (int i = 0; i < I; i++) {
    for (int j = 0; j < J; j++) {
        for (int k = 0; k < K; k++) {
            int realIdx = (i * (K * J) + j * K + k) * 2;
            int imagIdx = realIdx + 1;

            arr[realIdx] = k;
            arr[imagIdx] = k;
        }
    }
}

// k j i
float* transArr = new float[idealI * J * K * 2];

for (int i = 0; i < idealI; i++) {
    for (int j = 0; j < J; j++) {
        for (int k = 0; k < K; k++) {
            int realIdx = (i * (K * J) + j * K + k) * 2;
            int imagIdx = realIdx + 1;

            transArr[realIdx] = 0;
            transArr[imagIdx] = 0;
        }
    }
}

func2(arr, transArr);


delete[] arr;
delete[] transArr;

return 0;

}

[bfjm]

不能这样一起测吧 cpu cache 命中率不一样

[awenxjtu]

cpu 有缓存，缓存的访问速度比内存的访问速度快的多，另外缓存会一大块一大块的和内存交换数据以提高内存的访问速度。第一个 for 循环写法基本上是连续访问内存地址，内存地址基本上会命中缓存中的数据；而第二种写法访问的内存中的地址一会儿这里一会儿那里距离比较远就很可能访问的数据不在缓存中，这样就要等待从内存中读取数据，所以就比第一种写法慢了。

[jark006]

简单试了一下，结论就是：第一个三重 for 跑的时候，数据还没完全载入 CPU 缓存，到第二次三重 for 的时候，此时数据都在 CPU 高速缓存里了，数据命中率高，自然就快了。

你互换一下这俩三重 for ，结果也是第一次的就是慢点。或者再拿个 for 把他俩包起来跑 10 次就发现，开始几次就是慢点，后面都一样快了

[neocanable]

把这段代码编译出来，拿 IDA 反编译一下
第一个循环：
```
for ( m = 0; m < v29; ++m )
{
for ( n = 0; n < v28; ++n )
{
for ( ii = 0; ii < v27; ++ii )
v21[m + v29 * n + v29 * v28 * ii] = (float)(int)v25[ii + v27 * n + v28 * v27 * m] * 0.1;
}
}
```

第二个循环：
```
for ( jj = 0; jj < v29; ++jj )
{
for ( kk = 0; kk < v28; ++kk )
{
for ( mm = 0; mm < v27; ++mm )
v21[jj + v26 * kk + v26 * v28 * mm] = (float)(int)v25[mm + v27 * kk + v28 * v27 * jj] * 0.1;
}
}
```


没啥不一样，只能是 cpu cache 的问题

[ty29022]

>> There are only two hard things in Computer Science: cache invalidation and naming things.

[ty29022]

但我有些疑惑的是这个数据量以现代 cpu 的缓存大小来说应该没多大区别才是

[bfjm]

@ty29022 warm cache 对性能影响比较大 https://img.picui.cn/free/2024/11/08/672e1695ad332.png

[lzoje]

new 的时候并没有实际分配到内存，所以第一次访问的时候都是未命中，比较耗时

[pf94]

@ty29022 100*200*300*4b=22.88MB “现代 CPU”的 L1 缓存您认为是多少？

[lzoje]

可以试下 new 之后访问一下，然后再测

[mightybruce]

cpu 缓存 和 提高计算/访存比 是对大型矩阵计算是有非常大的影响的，对于大多数人不做 HPC 高性能计算，很多优化比如循环拆分和向量化是看不到的，很多时候大家都是借助库比如 openblas 和 openmp 来解决的。

我提供几篇文章给大家参考参考
https://renzibei.com/2021/06/30/optimize-gemm/
https://lzzmm.github.io/2021/09/10/GEMM/

[CedarChen]

这个我记得是 csapp 封面上的问题哦，op 可以拿过看下

[wisefree]

``` c++

#include <iostream>
#include <chrono>


int I = 360;
int J = 280;
int K = 3;

int idealI = 512;

void func1(int* arr, float* transArr)
{
auto startTime = std::chrono::steady_clock::now();

for (int i = 0; i < I; i++) {
for (int j = 0; j < J; j++) {
for (int k = 0; k < K; k++) {

int realIdx = (i * (K * J) + j * K + k) * 2;
int imagIdx = realIdx + 1;

int transRealIdx = (k * (J * I) + j * I + i) * 2;
int transImagIdx = transRealIdx + 1;

transArr[transRealIdx] = arr[realIdx] * 0.1f;
transArr[transImagIdx] = arr[imagIdx] * 0.1f;
}
}
}

auto endTime = std::chrono::steady_clock::now();

std::chrono::duration<double> diffTime = endTime - startTime;

std::cout << diffTime.count() << std::endl;
}


void func2(int* arr, float* transArr)
{
auto startTime = std::chrono::steady_clock::now();

for (int i = 0; i < I; i++) {
for (int j = 0; j < J; j++) {
for (int k = 0; k < K; k++) {
int realIdx = (i * (K * J) + j * K + k) * 2;
int imagIdx = realIdx + 1;

int transRealIdx = (k * (J * idealI) + j * idealI + i) * 2;
int transImagIdx = transRealIdx + 1;

transArr[transRealIdx] = arr[realIdx] * 0.1f;
transArr[transImagIdx] = arr[imagIdx] * 0.1f;
}
}
}

auto endTime = std::chrono::steady_clock::now();

std::chrono::duration<double> diffTime = endTime - startTime;

std::cout << diffTime.count() << std::endl;
}

int main(void)
{

// i j k
int* arr = new int[I * J * K * 2];
for (int i = 0; i < I; i++) {
for (int j = 0; j < J; j++) {
for (int k = 0; k < K; k++) {
int realIdx = (i * (K * J) + j * K + k) * 2;
int imagIdx = realIdx + 1;

arr[realIdx] = k;
arr[imagIdx] = k;
}
}
}

// k j i
float* transArr = new float[idealI * J * K * 2];

for (int i = 0; i < idealI; i++) {
for (int j = 0; j < J; j++) {
for (int k = 0; k < K; k++) {
int realIdx = (i * (K * J) + j * K + k) * 2;
int imagIdx = realIdx + 1;

transArr[realIdx] = 0;
transArr[imagIdx] = 0;
}
}
}

func1(arr, transArr);
func2(arr, transArr);


delete[] arr;
delete[] transArr;

return 0;
}
```

[wisefree]

@awenxjtu 重新写了一个例子，应该就可以用你的说法解释了，附言没有发送没有用 markdown 语法，格式有点混乱

[wisefree]

@jark006 是的，重新写了一个例子，发现应该是缓存起作用

[wisefree]

@neocanable 同意，我重新写了一个例子，也应该是缓存导致速度差异

[wisefree]

@lzoje 多谢，是这样的，我调整了用例，new 之后全部赋值

[wisefree]

@CedarChen 好的，多谢

[wisefree]

@mightybruce 多谢啦，我调整了一下，发现自己对高性能运算，确实没有了解太多

[stinkytoofool]

空间局部性