面试题：C语言循环嵌套优化

Question

有如下代码，使用了双重循环遍历二维数组，假设数组规模很大，如何优化这段代码以提高执行效率？ ```c #include <stdio.h> #define ROWS 1000 #define COLS 1000 int main() { int arr[ROWS][COLS]; for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { arr[i][j] = i + j; } } // 这里省略对数组后续操作 return 0; } ```

Answer 1

1. 数据访问模式优化：
   • 当前代码按行优先访问二维数组。在现代计算机体系结构中，内存是以缓存行（cache line）为单位进行读取和写入的。如果访问模式能更好地利用缓存，可提高效率。对于二维数组，连续访问同一行的数据能更好地利用缓存，因为同一行的数据在内存中是连续存储的。所以这种按行优先访问的方式本身已经比较合理，但在更复杂的场景下，比如涉及到跨缓存行的大数组操作时，可以考虑使用缓存友好的块处理方式。
2. 编译器优化选项：
   • 使用编译器提供的优化选项。例如在GCC编译器中，可以使用-O2、-O3等优化级别。-O2会进行大量的优化，包括循环优化、指令调度等；-O3在-O2的基础上进一步优化，如进行函数内联等。编译时可使用类似命令：gcc -O2 your_code.c -o your_program。
3. 并行化：
   • 利用多线程或多核CPU的并行能力。例如在C语言中，可以使用OpenMP进行并行化处理。修改后的代码如下：

#include <stdio.h>
#include <omp.h>
#define ROWS 1000
#define COLS 1000
int main() {
    int arr[ROWS][COLS];
    #pragma omp parallel for collapse(2)
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            arr[i][j] = i + j;
        }
    }
    // 这里省略对数组后续操作
    return 0;
}

• #pragma omp parallel for collapse(2)语句将两层循环并行化，collapse(2)表示将两层循环作为一个整体并行处理，充分利用多核CPU的计算资源，提高执行效率。编译时需要链接OpenMP库，例如在GCC中使用gcc -fopenmp your_code.c -o your_program。