Quiz

• Q6: 考慮以下程式碼:

#define N 1024
void diag(int A[4][4], int val) {
    for (long i = 0; i < N; i++)
        A[i][i] = val;
}

當用 gcc -O2 -S 編譯可得以下組合語言輸出:

        .globl  diag
        .type   diag, @function
diag:
        leaq    20480(%rdi), %rax
.L2:
        movl    %esi, (%rdi)
        addq    $20, %rdi
        cmpq    %rax, %rdi
        jne     .L2
        rep ret

請試著從最佳化反推對應的 C 程式碼，並避免將 N 寫死。

void diag(int A[4][4], int val) {
    int *Abase = &A[0][0];
    long i = 0;
    long lend = N * 5;
    do {
        Abase[i] = val;
        i += 5;
    } while (i != lend);
}

• Q7: 試圖改善 merge sort 的效能，考慮以下程式碼:

void merge(long *dst, long *src1, long *src2, size_t n) {
    size_t i1 = 0, i2 = 0, id = 0;
    while (i1 < n && i2 < n) {
        if (src1[i1] < src2[i2])
            dst[id++] = src1[i1++];
        else
            dst[id++] = src2[i2++];
    }
    while (i1 < n)
        dst[id++] = src1[i1++];
    while (i2 < n)
        dst[id++] = src2[i2++];
}

分支預測錯誤發生在首次發生錯誤時，又，src1[i1] 和 src2[i2] 之間的比較，對數據較難預測。請試著重寫以上第 4 到 7 行之間的程式碼，讓分支預測達到更好的表現。