Что такое псевдонимы и как это влияет на производительность?

Question

В случае GoingNative, во время Interactive Panel на DAY2 на 9-й минуте, Чандлер Carruth говорит:

Указатели создают проблемы наложения спектров. Они замедляют ваши двоичные файлы, а не ускоряют их.

Что это значит? Можно ли это проиллюстрировать (простым) примером?

Answer 1

Алиасинг влияет на производительность, не позволяя компилятору выполнять определенные оптимизации. Например:

void foo(int *array,int *size,int *value) { 
    for(int i=0;i<*size;++i) { 
     array[i] = 2 * *value; 
    } 
} 

Глядя на этот код можно было бы ожидать, что компилятор может загрузить *value один раз вне цикла, а затем установить каждый элемент массива на это значение очень быстро. Но это не так из-за псевдонимов. Потому что *value может быть псевдонимом для элемента массива, который он может изменить на любой заданной итерации. Поэтому код должен загружать значение каждой отдельной итерации, что приводит к потенциально большому замедлению.

Если переменные могут не псевдоним, то приведенный выше код будет эквивалентно следующему:

void foo(int *array,int size,int value) { 
    for(int i=0;i<size;++i) { 
     array[i] = 2 * value; 
    } 
} 

Использование LLVM-х online demo получить сгенерированный код, вот различные результаты:

1) С ступенчатостью

foo:         # @foo 
    .cfi_startproc 
# BB#0: 
    cmpl $0, (%rsi) 
    jle .LBB0_3 
# BB#1: 
    xorl %eax, %eax 
    .align 16, 0x90 
.LBB0_2:        # %.lr.ph 
             # =>This Inner Loop Header: Depth=1 
    movl (%rdx), %ecx 
    addl %ecx, %ecx 
    movl %ecx, (%rdi,%rax,4) 
    incq %rax 
    cmpl (%rsi), %eax 
    jl .LBB0_2 
.LBB0_3:        # %._crit_edge 
    ret 
    .size foo, .Ltmp1-foo 
    .cfi_endproc 
.Leh_func_end0: 

---

2) Без наложения

foo:         # @foo 
    .cfi_startproc 
# BB#0: 
    testl %esi, %esi 
    jle .LBB0_3 
# BB#1:         # %.lr.ph 
    addl %edx, %edx 
    .align 16, 0x90 
.LBB0_2:        # =>This Inner Loop Header: Depth=1 
    movl %edx, (%rdi) 
    addq $4, %rdi 
    decl %esi 
    jne .LBB0_2 
.LBB0_3:        # %._crit_edge 
    ret 
    .size foo, .Ltmp1-foo 
    .cfi_endproc 
.Leh_func_end0: 

Вы можете увидеть, что версия с ступенчатостью должна делать больше работы в теле цикла (между этикетками LBB0_2 и LBB0_3).

Answer 2

указатель представляет собой значение, которое представляет собой адрес памяти иногда 2 указатели могут представлять одни и те же адреса памяти, вот что сглаживание является

int * p; 
*p = 5; 

int * alias; 
alias = p; 

переменной alias является псевдонимом р и *alias равно 5, если вам изменить *alias затем *p изменения вместе с ним

Answer 3

Тип проблемы Чендлер говорил о можно легко проиллюстрировать с упрощенным strcpy:

char *stpcpy (char * dest, const char * src); 

При написании этой реализации вы можете предположить, что память, на которую указывает dest, полностью отделена от памяти, на которую указывает src. Компилятор), возможно, захочет оптимизировать его, читая блок символов из строки, на которую указывает src, и записывая все их сразу в dest. Но если dest указал на один байт перед src, поведение этого будет отличаться от простой посимвольной копии.

Здесь проблема в том, что сглаживание src может псевдоним dest, и сгенерированный код должен быть менее эффективный, чем она могла бы быть, если src не был разрешен псевдонимом dest.

Реальный strcpy использует дополнительное ключевое слово, Restrict (который technically only part of C, not C++, что говорит компилятору предположить, что src и dest не пересекаются, и это позволяет компилятору генерировать более эффективный код.

---

Вот еще более простой пример, где мы можем увидеть большую разницу в сборке:

void my_function_1(int* a, int* b, int* c) { 
    if (*a) *b = *a; 
    if (*a) *c = *a; 
} 

void my_function_2(int* __restrict a, int* __restrict b, int* __restrict c) { 
    if (*a) *b = *a; 
    if (*a) *c = *a; 
} 

Предположим, что это упрощение функции где на самом деле имеет смысл использовать два if-утверждения, а не только if (*a) { *b=*a; *c=*a; }, но намерение остается тем же.

Мы можем предположить при написании этого, что a != b, потому что есть какая-то причина, почему это не имеет смысла для my_function использовать таким образом.Но компилятор не может предположить, что и делает магазин b и повторную загрузку a из памяти перед выполнением второй линии, чтобы покрыть случай, когда b == a:

0000000000400550 <my_function_1>: 
    400550:  8b 07     mov (%rdi),%eax 
    400552:  85 c0     test %eax,%eax     <= if (*a) 
    400554:  74 0a     je  400560 <my_function_1+0x10> 
    400556:  89 06     mov %eax,(%rsi) 
    400558:  8b 07     mov (%rdi),%eax 
    40055a:  85 c0     test %eax,%eax     <= if (*a) 
    40055c:  74 02     je  400560 <my_function_1+0x10> 
    40055e:  89 02     mov %eax,(%rdx) 
    400560:  f3 c3     repz retq 

Если удалить потенциал для наложения путем добавления __restrict, компилятор генерирует более короткий и более быстрый код:

0000000000400570 <my_function_2>: 
    400570:  8b 07     mov (%rdi),%eax 
    400572:  85 c0     test %eax,%eax 
    400574:  74 04     je  40057a <_Z9my_function_2PiS_S_+0xa> 
    400576:  89 06     mov %eax,(%rsi) 
    400578:  89 02     mov %eax,(%rdx) 
    40057a:  f3 c3     repz retq 

Answer 4

Рассмотрим следующую функцию:

void f(float* lhs, float* rhs, float* out, int size) { 
    for(int i = 0; i < size; i++) { 
     out[i] = *lhs + *rhs; 
    } 
} 

Какова самая быстрая версия этой функции? Возможно, вы выходите из цикла *lhs + *rhs. Проблема заключается в том, что происходит, когда псевдонимы указателей. Представьте себе, что это оптимизация делает, если я называю это так:

float arr[6] = { ... }; 
f(arr, arr + 1, arr, 6); 

Как вы можете видеть, проблема в том, что *lhs + *rhs не может быть поднята из петли, потому что out[i] изменяет их значение. Фактически, компилятор не может поднять любую логику из цикла. Таким образом, компилятор не может выполнить «очевидную» оптимизацию, потому что если параметры псевдонимы логики теперь неверны. Однако, если поплавки берутся по значению, компилятор знает, что они не могут использовать псевдоним и могут выполнять подъем.

Конечно, эта функция довольно глупа, но она демонстрирует точку.