当矩阵以行优先存储时，我的任务是使用行优先和列优先方法来实现矩阵向量乘法。当然，当嵌套循环的内部迭代矩阵行而不是列时，我预计会出现大量缓存未命中。我想知道矩阵的存储方法是否以及如何影响缓存未命中损失。
我将以下示例简化为最坏情况的计算，因此将行主矩阵和向量与列主算法相乘。行主矩阵与行主算法并没有显示出存储方法之间有太大差异。
第一种方法使用指向数组的指针数组来按行优先顺序存储矩阵。第二种方法使用一维数组和线性索引计算。
参见https://godbolt.org/z/zqKs4vvxE
按照评论中的要求
#include <stddef.h> // for size_t
#include <stdio.h> // for printf
#include <stdlib.h> // for malloc and rand
#include <string.h> // for memset
#include <time.h> // for clock
#define NRUNS 10
// -----------------------------------------------------------------------------
float** create_random_matrix_aop(size_t n_rows, size_t n_cols) {
float** matrix = malloc(n_rows * sizeof(*matrix));
for (size_t i_row = 0; i_row < n_rows; ++i_row) {
matrix[i_row] = malloc(n_cols * sizeof(*matrix[0]));
for (size_t i_col = 0; i_col < n_cols; ++i_col) {
matrix[i_row][i_col] = (float)rand();
}
}
return matrix;
}
void matmul_col_major_2d(size_t n_rows, size_t n_cols, float** matrix,
float* vector, float* result) {
memset(result, 0, n_rows * sizeof(*result));
for (size_t i_col = 0; i_col < n_cols; ++i_col) {
for (size_t i_row = 0; i_row < n_rows; ++i_row) {
result[i_row] += matrix[i_row][i_col] * vector[i_col];
}
}
}
void free_matrix(float** matrix, size_t n_rows) {
for (size_t i_row = 0; i_row < n_rows; ++i_row) {
free(matrix[i_row]);
}
free(matrix);
}
void array_of_pointers(size_t n_rows, size_t n_cols) {
float** matrix = create_random_matrix_aop(n_rows, n_cols);
float* vector = matrix[0]; // it's random values anyway
float* result = malloc(n_rows * sizeof(result[0]));
clock_t start;
clock_t finish;
clock_t elapsed;
clock_t mean_elapsed;
mean_elapsed = 0;
for (int i = 0; i < NRUNS; ++i) {
start = clock();
matmul_col_major_2d(n_rows, n_cols, matrix, vector, result);
finish = clock();
elapsed = finish - start;
mean_elapsed += elapsed;
}
mean_elapsed /= NRUNS;
printf("array_of_pointers: %16lu us ",
mean_elapsed * 1000000ul / CLOCKS_PER_SEC);
free_matrix(matrix, n_rows);
free(result);
}
// -----------------------------------------------------------------------------
float* create_random_matrix_1d(size_t n_rows, size_t n_cols) {
size_t n_values = n_rows * n_cols;
float* matrix = malloc(n_values * sizeof(*matrix));
for (size_t i_value = 0; i_value < n_values; ++i_value) {
matrix[i_value] = (float)rand();
}
return matrix;
}
void matmul_col_major_1d(size_t n_rows, size_t n_cols, float* matrix,
float* vector, float* result) {
memset(result, 0, n_rows * sizeof(*result));
for (size_t i_col = 0; i_col < n_cols; ++i_col) {
for (size_t i_row = 0; i_row < n_rows; ++i_row) {
size_t i_lin = i_row * n_cols + i_col;
result[i_row] += matrix[i_lin] * vector[i_col];
}
}
}
void linear_array(size_t n_rows, size_t n_cols) {
float* matrix = create_random_matrix_1d(n_rows, n_cols);
float* vector = matrix; // it's random values anyway
float* result = malloc(n_rows * sizeof(result[0]));
clock_t start;
clock_t finish;
clock_t elapsed;
clock_t mean_elapsed;
mean_elapsed = 0;
for (int i = 0; i < NRUNS; ++i) {
start = clock();
matmul_col_major_1d(n_rows, n_cols, matrix, vector, result);
finish = clock();
elapsed = finish - start;
mean_elapsed += elapsed;
}
mean_elapsed /= NRUNS;
printf("linear_array: %16lu us ", mean_elapsed * 1000000ul / CLOCKS_PER_SEC);
free(matrix);
free(result);
}
// -----------------------------------------------------------------------------
int main() {
size_t n_rows = 64;
while (n_rows <= 8192) {
size_t n_cols = n_rows;
printf("matrix %4lu x %4lu ", n_rows, n_cols);
linear_array(n_rows, n_cols);
array_of_pointers(n_rows, n_cols);
printf("\n");
n_rows <<= 1;
}
}
我的机器（第 13 代 Intel i7-1360P (16) @ 5.000GHz）使用 gcc 13.2.1 和
-O2matrix 64 x 64 linear_array: 2 us array_of_pointers: 2 us
matrix 128 x 128 linear_array: 12 us array_of_pointers: 10 us
matrix 256 x 256 linear_array: 58 us array_of_pointers: 52 us
matrix 512 x 512 linear_array: 374 us array_of_pointers: 172 us
matrix 1024 x 1024 linear_array: 2927 us array_of_pointers: 953 us
matrix 2048 x 2048 linear_array: 19790 us array_of_pointers: 5331 us
matrix 4096 x 4096 linear_array: 221155 us array_of_pointers: 54365 us
matrix 8192 x 8192 linear_array: 974931 us array_of_pointers: 306641 us
我发现的大多数帖子和文章都说，一个连续的内存块应该比指针数组具有优势。但在这种（糟糕的）情况下，一维数组的性能要差得多。
请帮我理解这是为什么。
指针数组中的缓存未命中次数是
malloc