Как стать автором
Обновить

Про C++ алиасинг, ловкие оптимизации и подлые баги

Время на прочтение 6 мин
Количество просмотров 42K
С удивлением обнаружил, что про явление алиасинга (aliasing) здесь постов нет. Ситуацию нужно исправить, тк. алиасинг в любой сколько-то сложной C++ программе обязательно хоть где-нибудь, да есть. Это может быть хорошо, давая возможность ловких оптимизаций, а может быть плохо, внося повышенной паршивости баги. Под катом вкратце про оба случая (ну и неизменное «компилятор бьет спина», конечно; для разнообразия сегодня это gcc).

Про aliasing



Что такое aliasing? Очень просто. Это когда на один и тот же участок памяти показывают несколько разных указателей. Например.

int A;
int * B = &A;
int * C = &A;


В этом примере у переменной A внезапно три разных имени (alias): A, *B, *C. Это совершенно легальный код. Компилятор успешно обработает все 3 имени, если в A что-нибудь запишут, то через *B это будет можно прочитать и наоборот, все хорошо.

Про оптимизации и __restrict



За исключением одной мелочи: возможных оптимизаций. Компилятор обязан понимать и помнить про aliasing не только в таком наглядном случае, но и там, где человек неявно никаких алиасов не предполагает. Например.

void SumIt ( int * out, const int * in, int count )
{
      for ( int i=0; i<count; i++ )
              (*out) += *in++;
}


Обычная функция с out-параметром, ничто не предвещает беды. А она есть. Компилятору никто не дал гарантий, что out-переменная по адресу *out решительно не пересекается с in-данными по адресу *in. Самостоятельно он таких предположений сделать не имеет права: мало ли, как и почему человек захочет написать? Поэтому на каждой итерации внутреннего цикла происходит запись *out обратно в память, даже при максимальном уровне оптимизации. Дизасм (gcc -O3 -S, 4.4.3, ubuntu x64) выглядит вот так.

.L7:
      addq    $4, %rax
      addl    (%rsi), %ecx
      cmpq    %rdx, %rax
      movq    %rax, %rsi
      movl    %ecx, (%rdi) ; <-- вот оно!
      jne     .L7


Компилятору однако можно подсказать, что out никак не пересекается с in. Для этого человечество придумало модификатор __restrict.

void SumIt ( int * __restrict out, const int * __restrict in, int count )
{
      for ( int i=0; i<count; i++ )
              (*out) += *in++;
}


.L14:
      addq    $4, %rax
      addl    (%rsi), %ecx
      cmpq    %rdx, %rax
      movq    %rax, %rsi
      jne     .L14
      movl    %ecx, (%rdi)


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

1783293664 in 103818 usec
1783293664 in 69818 usec


Не совсем. Удается. Упс, ускорение примерно эдак в 1.5 раза. Такая вот местами бывает цена одной инструкции (и двух модификаторов). Обычно все равно, но для хорошо нагруженных внутренних циклов полезно.

Про strict aliasing и баги



Как видим, устранение алиасинга может вылиться в неплохое улучшение скорости. Видимо, из этих соображений в стандарте C99, а через это и C++, придумали и ввели правило про strict aliasing. Ссылка для людей, владеющих мастерством чтения и понимания Стандарта: N1124, 6.5(7). Нормальному человеку туда смотреть не очень стоит: например, ни слова strict, ни слова aliasing в этом абзаце нет. ;) (Найти его сколько-то быстро удалось только потому, что в сноске номер 74 есть слово aliased.) Особо важный прикладной смысл «на пальцах» однако можно пояснить довольно просто.

В режиме strict aliasing компилятор считает, что объекты, на которые показывают указатели «существенно различных» типов, НЕ могут храниться в одном и том же участке памяти, и может использовать это при оптимизациях.

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

#include <stdio.h>

typedef unsigned int DWORD;
typedef unsigned short WORD;

inline DWORD SwapWords ( DWORD val )
{
      WORD * p = (WORD*) &val;
      WORD t;
      t = p[0];
      p[0] = p[1];
      p[1] = t;
      return val;
}

int main()
{
      printf ( "%d\n", SwapWords(1) );
      return 0;
}


Эта незатейливая программка печатает либо 65536 при сборке g++ test.cpp, либо 1 при сборке g++ -O3 test.cpp. Что за дела?!

Дело в том, что начиная с -O2 автоматом включается -fstrict-aliasing. И компилятор считает, что *p в принципе не может показывать туда, где хранится val. И успешно это дело оптимизирует насмерть: раз не может, значит нам вернут значение аргумента; значит SwapWords(1) можно заменить просто на константу 1.

Причем в данном примере проблемы, на самом деле, не очень есть. Ибо если включить -Wall (ну или хотя бы -Wstrict-aliasing), компилятор честно пожалуется на непонятное.

test.cpp:8: warning: dereferencing pointer 'p.14' does break strict-aliasing rules


Что нетяжело исправить. Детсадовский метод, это отключить проклятый strict aliasing совсем ключиком -fno-strict-aliasing. Уставной способ исправления, который де-факто работает везде и всюду, это протянуть значение через union. Полям union вроде как любой компилятор милостиво дозволяет алиасится друг с другом. Любые фокусы с указателями теоретически могут вылиться боком (undefined behavior), в случае gcc теория нетяжело превращается в практику и обратно (-fstrict-aliasing).

inline DWORD SwapWords ( DWORD val )
{
	union { DWORD d; WORD v[2]; } u;
	u.d = val;
	WORD t = u.v[0];
	u.v[0] = u.v[1];
	u.v[1] = t;
	return u.d;
}


Ура-ура? Но увы, есть одно маленькое но: -Wstrict-aliasing ничего не гарантирует. Для поимки всех случаев алиасинга, не совместимых с текущим режимом компиляции, его недостаточно. Достаточно короткого и потому наглядного примера у меня нет (есть слишком длинный), поэтому придется поверить на слово: совсем немного шаблонного фарша, функтор-другой, и strict aliasing ловко маскируется и ворнинга не дает. В программе с активным использованием STL и-или Boost, подозреваю, незаметно нарушить strict aliasing где-нибудь в дебрях кода должно быть довольно нетяжело. Третьи лица также свидетельствуют, что фокусы с приведением к void* и обратно успешно подавляли warning как минимум на gcc 4.1.x, при этом оставляя генерацию кривого кода, разумеется.

Несмотря на undefined behavior винт оно, конечно, не отформатирует. (Ну, не сразу.) Однако переставить местами чтение и запись в память в целях оптимизации компилятор может запросто. Выглядит это примерно вот так.

inline uint64_t GetIt ( const DWORD * p )
{
      return *(uint64_t*)p;
}

int main()
{
      DWORD buf[10];
      uint64_t t;

      buf[0] = 1;
      buf[1] = 2;
      t = GetIt(buf);
      buf[2] = 3;
      buf[3] = 4;

      printf ( "%d, %d, %d, %d\n", buf[0], buf[1], int(t>>32), int(t) );
      return 0;
}


Печатает оно опять же немного неожиданные циферки: 1, 2, 32573, -648193368. В отличие от предыдущего примера, где компилятор упростил функцию SwapWords() до полного отсутствия функции, здесь происходит именно перестановка местами чтения и записи. Компилятор делает вывод, что GetIt(buf) не зависит от содержимого buf, и поэтому сует «вызов» GetIt() куда считает нужным. Нужным получается вообще перед заполнением буфера.

mov    (%rsp),%r8 ; t = GetIt(buf)
...
movl   $0x1,(%rsp) ; buf[0] = 1
movl   $0x2,0x4(%rsp) ; buf[1] = 2
movl   $0x3,0x8(%rsp) ; buf[2] = 3
movl   $0x4,0xc(%rsp) ; buf[3] = 4
mov    %r8d,%r9d ; r9 = int(t)
shr    $0x20,%r8 ; r8 = int(t>>32)
callq  0x400510 <__printf_chk@plt>


В итоге в какой-нибудь переменной оказывается неверное значение (или слишком старое, или слишком новое)… и далее все вытекающие. Ловить такой подлый баг можно долго и безуспешно: для успешного проявления оптимизатор должен именно в этом «слепом» месте решить провести оптимизацию во1х, оптимизация должна проявится так, чтобы результаты поймались во2х.

Как уверенно бороться? Годных автоматических методов и тулзов не знаю. Раньше думал, что компилятор более-менее ловит; теперь однако вот знаю, что может пропустить и совершенно тривиальную конверсию, если ее слегка обернуть шаблонами (а может, и просто функциями даже). Бороться потому разве что молитвой и постом жесткой дисциплиной. Сменил указателю тип, подумай о сайд-эффектах. Почувствуй себя компилятором, подумай мальца за него: не бежит ли лиса, не летит ли орел, не ломается ли алиасинг.

Side-note: про всякие другие тонкости и фокусы из-за strict aliasing можно читать классический подробный пост по теме тов. Майка Актона, cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html

Что насчет MSVC?



Проблемы про strict aliasing там нет. Более того, возможности включить тоже нет. Видимо, MS приняло решение, что C99-compliant кода в мире без тонких граблей про aliasing в мире куда меньше, чем какого обычно, поэтому незачем создавать сложности. Просветительскую миссию осуществляет gcc, ну и бажок-другой иногда втихую нагенерит, не без этого.

Это автоматически означает, что фокусы про оптимизацию и __restrict для указателей там несколько важнее. Скажем, для void SumIt ( int64_t * out, const int * in, int count ) согласно strict правилу gcc имеет право «догадаться», что вряд ли out лежит в середине in; MSVC об этом догадываться гарантированно не будет. Надо либо restrict-ить вручную, либо вручную же сводить записи к минимуму. Уж локальную переменную он в регистр положить сможет.

Важно понимать, что член класса это тоже данные, лежащие по указателю this. Поэтому постоянное обращение к члену класса в цикле может компилироваться в постоянные мучения памяти.

Итого



1. Пишешь внутренний цикл, вспомни про aliasing и про __restrict.
2. Конвертируешь указатель, вспомни про strict aliasing и ядерный потенциал перестановки сайд-эффектов.
3. Пользуешься gcc, помни про дефолтный -fstrict-aliasing, не игнорируй -Wall.
4. Пользуешься MSVC, помни про принудительное отсутствие strict-aliasing-style оптимизаций, оптимизируй рукой.
5. Видишь warning насчет strict aliasing, разберись, может и UB-нуть.
6. Не видишь warning насчет strict aliasing? А он есть. Как суслик.
6.1. Компиляторы врут, ворнинги ненадежны, -Wall иногда работает (надо включать!), но гарантий не дает.
6.2. Самому себе вообще верить нельзя, только бенчмарки, дизасм, молитва и пост.
Теги:
Хабы:
+88
Комментарии 49
Комментарии Комментарии 49

Публикации

Истории

Работа

Программист C++
128 вакансий
QT разработчик
15 вакансий

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн