highly professional scums

Оно понятно, что на компилятор надейся, а сам не плошай. Однако 2007-й год за окном провоцирует многих думать, что современный компилятор от ведущей-компании разработчика ПО (это MSVC 2005) достаточно умен, чтобы хорошо компилировать несложный код.

Увы, это заблуждение.

Пример 1.

Активная запись в члены класса из метода даже в несложных циклах – приводит к почти что 2-кратному падению производительности на синтетическом примере, и вполне измеримой 5-10% разнице на боевом коде.

Пример кода и результаты исполнения (приведены только ключевые фрагменты; полный код всех примеров приаттачен):

[code lang="cpp"]
struct Test
{
unsigned int m_iCounter;
unsigned int m_iLimit;
char m_sBuffer[1024];

Test ()
{
m_iLimit = sizeof(m_sBuffer);
for ( int i=0; i m_sBuffer[i] = (char)( rand() % 6 );
}

const char * Test1 ()
{
// skip whitespace
while ( m_iCounter m_iCounter++;

// check for eof
if ( m_iCounter>=m_iLimit )
{
m_iCounter = 0;
return NULL;
}

// skip nonwhitespace
int iRes = m_iCounter;
while ( m_iCounter m_iCounter++;

return m_sBuffer + iRes;
}

const char * Test2 ()
{
// skip whitespace
int iPos = m_iCounter;
while ( iPos iPos++;

// check for eof
if ( iPos>=m_iLimit )
{
m_iCounter = 0;
return NULL;
}

// skip nonwhitespace
int iRes = iPos;
while ( iPos iPos++;

m_iCounter = iPos;
return m_sBuffer + iRes;
}
};

member write-pressure
test1 701.00 msec
test2 413.00 msec
[/code]

Причина проблемы ясна. Компилятор отчего-то не может догадаться, что счетчик следует держать в регистре, и постоянно записывает его обратно в память - несмотря, что код абсолютно (!) тривиален - в нем нет никаких ранних выходов из цикла, никаких исключений, никакого aliasing - в общем, ни одной разумной причины, по которой компилятор мог бы прокатить оптимизацию по выносу записи счетчика в память за границы цикла.

Решение проблемы также ясно, и оформляется в несложный rule-of-thumb: при большом write-pressure на член класса следует вручную выносить его во временную переменную на стеку.

Неприятно, конечно, что в 2007-м году приходится заниматься такой дурью, как ручной вынос записи за цикл. А вот!

Пример 2.

Вскользь упомянутый в первом примере aliasing также может неплохо влиять на производительность, так что остановимся на нем несколько подробнее.

Aliasing - это ситуция, когда на одну и то же область памяти может существовать несколько разных указателей. В этом случае компилятор не имеет права оптимизировать доступ к этой области памяти, и вынужден генерировать неэффективный код. Помимо тупо добавления ненужных чтений и записей в память, aliasing может также повлечь невозможность более тонких оптимизаций: перестановки доступов к памяти, выноса инвариантов за цикл, итп.

Про aliasing немногие знают и нечасто вспоминают, но это достаточно частая в коде ситуация в коде - хотя иногда с первого взгляда она не заметна. Рассмотрим вот такой пример:

[code lang="cpp"]
__declspec(noinline) void Process1 ( int len, int * b, int * c, int * out )
{
*out = 0;
for ( int i=0; i *out += *b++ - *c++;
}

__declspec(noinline) void Process2 ( int len, int * b, int * c, int * out )
{
int res = 0;
for ( int i=0; i res += *b++ - *c++;
*out = res;
}

__declspec(noinline) void Process3 ( int len, int * b, int * c, int * __restrict out )
{
*out = 0;
for ( int i=0; i *out += *b++ - *c++;
}

aliased RAM churning
original 102.00 msec
temp-var 82.00 msec
restrict 84.00 msec
[/code]

Что происходит в данном примере, откуда берутся 20% разницы?

В первом случае компилятор не может быть уверен, что указатель на выходной параметр out не указывает в середину массивов "b" или "c"; и поэтому не может (не имеет права!) оптимизировать запись в него выносом за цикл.

Во втором случае вынос записи за цикл сделан вручную.

В третьем случае модификатор __restrict подсказывает компилятору, что адресуемая область памяти не пересекается с другими аргументами; после чего оптимизацию с выносом он догадывается провести сам.

Соответствующий rule-of-thumb: при случае подсказывайте компилятору про гарантированно неперекрывающиеся адреса аргументов, оно того стоит (см. 20%). (Только перед этим не забывайте заодно вставлять assert()-ы на проверку фактического неперекрытия, иначе очередной тонкий баг придется ловить примерно неделю.)

Пример 3.

Можно спорить о том, что анализировать граф исполнения из первого примера компилятору очень сложно и непросто (тут напоминаю: компилятор - ведущий; граф - тривиальный); а во втором примере так и вообще по уставу дело программиста подсказывать про отсутствие aliasing (тут согласен: так и есть).

Но вы таки думаете, что в других моментах - типа доступной первокурснику оптимизации логических выражений - оно шибко кошернее? Ша!

[code lang="cpp"]
for ( int i=0; i<100000000; i++ )
if ( ~a[i&31] | ~b[i&31] )
res++;

...
for ( int i=0; i<100000000; i++ )
if (~( a[i&31] & b[i&31] ))
res++;

boolean expression evaluation
not-or-not 252.00 msec
and-not 212.00 msec
[/code]

Выражения полностью эквиваленты, но второе на 20 процентов быстрее - в первом при трансляции "в лоб" получается 3 операции, а во втором выходит 2 плюс-минус оверхеды на получение индекса и сам цикл. Оптизировать арифметику, выходит, в 2007-м году тоже надо вручную.

Мораль?

Знай свой инструмент, и умей им пользоваться.
И не забывай профайлить очевидное.
Результат может оказаться невероятным.