9 / 10 TLB

Two Loops One Matrix

#define N 2048
static int m[N][N];        /* 16 MiB, page aligned */

long row_major(void) {
    long s = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            s += m[i][j];
    return s;
}

long col_major(void) {
    long s = 0;
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            s += m[i][j];
    return s;
}

Pages are 4 KiB, the data TLB holds 64 entries, huge pages are off. Both functions read all 4,194,304 elements exactly once. How do their TLB miss counts compare?

A

col_major takes about twice as many, since each row of the matrix is exactly two pages wide.

B

col_major takes roughly 1000 times as many, because each step of its inner loop moves 8192 bytes and the 2048 pages one column touches do not fit in 64 entries.

C

About the same. Both read all 4096 pages of the matrix, so both pay 4096 compulsory misses.

D

col_major takes about 64 times as many, since the TLB holds 64 entries.