Может ли gcc предварительно выбрать два массива? (косвенная предварительная выборка) - PullRequest
Новая
       38

Может ли gcc предварительно выбрать два массива? (косвенная предварительная выборка)

0 голосов
/ 03 мая 2018

Предположим, у меня есть два массива a и b, которые изначально не находятся в кэше. У меня есть цикл с шагом i, вычисляющий некоторую функцию b[a[i]]. Сможет ли gcc вставить необходимую предварительную выборку, чтобы b[a[i]] находился в кэше, как только мы углубимся в цикл?

1 Ответ

0 голосов
/ 03 мая 2018

Никакой gcc этого не делает (по крайней мере, для современных x86-64-архитектур). Например, скомпилированный с -O2 следующий простой код: 

double calc(int *add, double *ptr, int N){
    double res=0.0;
    for(int i=0;i<N;i++)
       res+=1.0/ptr[add[i]];
    return res;
}

приводит к ассемблеру без предварительной выборки, здесь только цикл, весь код на godbolt.org : 

...
.L3:
        movslq  (%rdi), %rax
        movapd  %xmm2, %xmm1
        addq    $4, %rdi
        cmpq    %rdi, %rdx
        divsd   (%rsi,%rax,8), %xmm1
        addsd   %xmm1, %xmm0
        jne     .L3
        rep ret
...

Но тогда gcc обычно не выполняет предварительную выборку и для прямого доступа: 

double calc(double *ptr, int N){
    double res=0;
    for(int i=0;i<N;i++)
       res+=1.0/ptr[i];
    return res;
}

с результирующим циклом ( весь ассемблер здесь ): 

...
.L3:
        movapd  %xmm2, %xmm1
        addq    $8, %rdi
        divsd   -8(%rdi), %xmm1
        cmpq    %rax, %rdi
        addsd   %xmm1, %xmm0
        jne     .L3
        rep ret
...

Обычно gcc не связывается с кэшированием / предварительной загрузкой и оставляет его аппаратному обеспечению.

Как вы правильно заметили, -fprefetch-loop-arrays предложит gcc предварительно извлечь данные ( весь ассемблер ): 

.L4:
    movapd  %xmm1, %xmm2
    addl    $8, %edx
    prefetcht0      (%rax)   ;!!! HERE PREFETCH FOR FUTURE
    addq    $64, %rax
    divsd   -160(%rax), %xmm2
    addsd   %xmm2, %xmm0
    movapd  %xmm1, %xmm2
    divsd   -152(%rax), %xmm2
    addsd   %xmm0, %xmm2
    movapd  %xmm1, %xmm0
    divsd   -144(%rax), %xmm0
    addsd   %xmm0, %xmm2
    movapd  %xmm1, %xmm0
    divsd   -136(%rax), %xmm0
    addsd   %xmm2, %xmm0
    movapd  %xmm1, %xmm2
    divsd   -128(%rax), %xmm2
    addsd   %xmm2, %xmm0
    movapd  %xmm1, %xmm2
    divsd   -120(%rax), %xmm2
    addsd   %xmm0, %xmm2
    movapd  %xmm1, %xmm0
    divsd   -112(%rax), %xmm0
    addsd   %xmm0, %xmm2
    movapd  %xmm1, %xmm0
    divsd   -104(%rax), %xmm0
    cmpl    %ecx, %edx
    addsd   %xmm2, %xmm0
    jne     .L4

Однако это не делает программу быстрее - аппаратная часть достаточно умна, чтобы самостоятельно выбирать данные без подсказок компилятора. Не уверен, какая функция ответственна за это, я думаю, будет внеочередное исполнение .

Вы подняли вопрос о том, что не хватает «работы» для чередования с извлечением данных. Это правда, но даже для таких функций, как 

double calc(double *ptr, int N){
    double res=0;
    for(int i=0;i<N;i++){
        res+=1.0/ptr[i]*ptr[i]/ptr[i]*ptr[i]/ptr[i]*ptr[i];
    }
    return res;
}

ничего не меняется .

Последний вопрос: что происходит с -fprefetch-loop-arrays и косвенным доступом, как в первом примере? Мы легко можем увидеть , что предварительно выбран только массив add, но не массив ptr: 

.L4:
        movslq  -40(%rax), %r8
        movapd  %xmm1, %xmm2
        prefetcht0      (%rax)  ;HERE rax CORRESPONDS TO add !!
        addl    $16, %ecx
        addq    $64, %rax
        divsd   (%rsi,%r8,8), %xmm2
        movslq  -100(%rax), %r8
        addsd   %xmm2, %xmm0
        movapd  %xmm1, %xmm2
        divsd   (%rsi,%r8,8), %xmm2
        movslq  -96(%rax), %r8
        addsd   %xmm0, %xmm2
        movapd  %xmm1, %xmm0
        divsd   (%rsi,%r8,8), %xmm0
        movslq  -92(%rax), %r8
        addsd   %xmm0, %xmm2
        movapd  %xmm1, %xmm0
        divsd   (%rsi,%r8,8), %xmm0
        movslq  -88(%rax), %r8
        addsd   %xmm2, %xmm0
        movapd  %xmm1, %xmm2
        divsd   (%rsi,%r8,8), %xmm2
        movslq  -84(%rax), %r8
        addsd   %xmm2, %xmm0
        movapd  %xmm1, %xmm2
        divsd   (%rsi,%r8,8), %xmm2
        movslq  -80(%rax), %r8
        addsd   %xmm0, %xmm2
        movapd  %xmm1, %xmm0
        divsd   (%rsi,%r8,8), %xmm0
        movslq  -76(%rax), %r8
        addsd   %xmm0, %xmm2
        movapd  %xmm1, %xmm0
        divsd   (%rsi,%r8,8), %xmm0
        movslq  -72(%rax), %r8
        addsd   %xmm2, %xmm0
        movapd  %xmm1, %xmm2
        divsd   (%rsi,%r8,8), %xmm2
        movslq  -68(%rax), %r8
        addsd   %xmm2, %xmm0
        movapd  %xmm1, %xmm2
        divsd   (%rsi,%r8,8), %xmm2
        movslq  -64(%rax), %r8
        addsd   %xmm0, %xmm2
        movapd  %xmm1, %xmm0
        divsd   (%rsi,%r8,8), %xmm0
        movslq  -60(%rax), %r8
        addsd   %xmm0, %xmm2
        movapd  %xmm1, %xmm0
        divsd   (%rsi,%r8,8), %xmm0
        movslq  -56(%rax), %r8
        addsd   %xmm2, %xmm0
        movapd  %xmm1, %xmm2
        divsd   (%rsi,%r8,8), %xmm2
        movslq  -52(%rax), %r8
        addsd   %xmm2, %xmm0
        movapd  %xmm1, %xmm2
        divsd   (%rsi,%r8,8), %xmm2
        movslq  -48(%rax), %r8
        addsd   %xmm0, %xmm2
        movapd  %xmm1, %xmm0
        divsd   (%rsi,%r8,8), %xmm0
        movslq  -44(%rax), %r8
        cmpl    %r9d, %ecx
        addsd   %xmm0, %xmm2
        movapd  %xmm1, %xmm0
        divsd   (%rsi,%r8,8), %xmm0
        addsd   %xmm2, %xmm0
        jne     .L4
...