Попросил ChatGPT написать код замера скорости обхода большого массива в правильном и неправильном порядке. Он правильно распознал, что речь шла про обход по рядам-столбцам и столбцам-рядам, правильность и неправильность которых происходит из неравномерного доступа к оперативной памяти через систему кэшей. Запустив предложенный код, я решил добавить изменённый обход с допонительными перескоками для большего соответствия произвольному доступу.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#if defined BIG
# define N 1
# define LEN 20000
# define JUMP 111
#endif
#if !defined N
# define N 1+40000
#endif
#if !defined LEN
# define LEN 200
#endif
#if !defined JUMP
# define JUMP 11
#endif
static unsigned csum;
static void fill_array(int array[LEN][LEN]) {
int i, j;
for (i = 0; i < LEN; i++) {
for (j = 0; j < LEN; j++) {
array[i][j] = rand() % 0x100;
}
}
}
static double measure_row_major(int array[LEN][LEN]) {
unsigned sum; int i, j, n; clock_t start, end;
start = clock();
sum = 0;
for (int n = N; n > 0; n -= 1)
for (int i = 0; i < LEN; i++)
for (int j = 0; j < LEN; j++)
sum ^= array[i][j] << (j % 24);
csum = sum;
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC;
}
static double measure_column_major(int array[LEN][LEN]) {
unsigned sum; int i, j, n; clock_t start, end;
sum = 0;
start = clock();
for (n = N; n > 0; n -= 1)
for (j = 0; j < LEN; j++)
for (i = 0; i < LEN; i++)
sum ^= array[i][j] << (j % 24);
csum = sum;
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC;
}
static double measure_strange(int array[LEN][LEN]) {
unsigned sum; int i, j, n, m, k; clock_t start, end;
sum = 0;
start = clock();
for (n = N; n > 0; n -= 1)
for (m = 0; m < JUMP; m++)
for (j = m; j < LEN; j += JUMP)
for (k = 0; k < JUMP; k++)
for (i = k; i < LEN; i += JUMP)
sum ^= array[i][j] << (j % 24);
csum = sum;
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC;
}
int main(void) {
int ok; int (*array)[LEN]; double row_major_time, column_major_time, strange_time;
array = malloc(sizeof(int) * LEN * LEN);
ok = (array != NULL);
if (!ok) {
fprintf(stderr, "Memory allocation failed\n");
} else {
fill_array(array);
row_major_time = measure_row_major(array);
printf("Row-major order: %.5f seconds; %u\n", row_major_time, csum);
column_major_time = measure_column_major(array);
printf("Column-major order: %.5f seconds; %u\n", column_major_time, csum);
strange_time = measure_strange(array);
printf("Column-strange order: %.5f seconds; %u\n", strange_time, csum);
free(array);
}
return ok;
}Я заказал этот тест, потому что хотел конкретных измерений работы процессора при влиянии кэша на вычислительную сложность алгоритма, но в не меньшей степени удалось проверить и компиляторы, потому что в этом тесте они изрядно отличились. На неправильном обходе сlang поломался и выдал совсем плохой результат, который оказался даже хуже, чем при выключенной оптимизации. gcc же наоборот c -O3 сумел распознать паттерн и неправильный обход превратить в правильный, уравняв скорость. Это и побудило меня добавить более сложный обход с прыжками, позволяющими лучше представить произвольный доступ. На нём поломался уже и gcc, тоже выдав результат хуже, чем неоптимизированный.
Замеры для обхода большого массива:
| процессор | Intel® Core™ i7-1185G7 |
| gcc | 13.2.0 |
| clang | 18.1.3 |
| tcc | 0.9.27 |
: clang main.c -O0 -DBIG && ./a.out
Row-major order: 0.54849 seconds; 1923116029
Column-major order: 2.88732 seconds; 1923116029
Column-strange order: 5.88750 seconds; 1923116029
: clang main.c -O3 -DBIG && ./a.out
Row-major order: 0.17319 seconds; 1923116029
Column-major order: 3.15131 seconds; 1923116029
Column-strange order: 7.96815 seconds; 1923116029
: gcc main.c -O0 -DBIG && ./a.out
Row-major order: 0.89732 seconds; 1923116029
Column-major order: 3.04100 seconds; 1923116029
Column-strange order: 7.77280 seconds; 1923116029
: gcc main.c -O3 -DBIG && ./a.out
Row-major order: 0.35919 seconds; 1923116029
Column-major order: 0.35695 seconds; 1923116029
Column-strange order: 8.03063 seconds; 1923116029
: tcc main.c -O3 -DBIG && ./a.out
Row-major order: 0.69452 seconds; 1923116029
Column-major order: 2.97060 seconds; 1923116029
Column-strange order: 7.41493 seconds; 1923116029
Для полноты картины сделаны замеры для обхода малого массива, который должен хорошо помещаться в кэш. Тут тоже не обошлось без сюрприза. Если без оптимизаций обходы ожидаемо оказались в целом сопостовимы по скорости, то при высокой оптимизации «неправильный» обзод оказался значительно быстрее «правильного». Замеры показывают, что не только человек, но компилятор изрядно путается при выборе лучшей стратегии обхода массива в условиях сложной логики доступа.
: clang main.c -O0 && ./a.out
Row-major order: 2.15677 seconds; 1374448224
Column-major order: 2.17528 seconds; 1374448224
Column-strange order: 2.95493 seconds; 1374448224
: clang main.c -O3 && ./a.out
Row-major order: 1.00091 seconds; 1374448224
Column-major order: 0.25905 seconds; 1374448224
Column-strange order: 0.37111 seconds; 1374448224
: gcc main.c -O0 && ./a.out
Row-major order: 3.80649 seconds; 1374448224
Column-major order: 3.73850 seconds; 1374448224
Column-strange order: 3.89375 seconds; 1374448224
: gcc main.c -O3 && ./a.out
Row-major order: 1.38273 seconds; 1374448224
Column-major order: 1.38412 seconds; 1374448224
Column-strange order: 0.72818 seconds; 1374448224
: tcc main.c -O0 && ./a.out
Row-major order: 2.80466 seconds; 1374448224
Column-major order: 2.46870 seconds; 1374448224
Column-strange order: 3.21835 seconds; 1374448224
В хорошем, ясном языке программирования должно быть как можно меньше подобных имитаций. В нашем случае всё это произошло из-за несоответствия машинного языка решаемым задачам, из-за чего и пришлось лепить сложную многослойную систему виртуализаций.
