Цена абстракции (или все, что мама не рассказывала про C++)

Оно понятно, что на компилятор надейся, а сам не плошай. Однако 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-м году тоже надо вручную.

Мораль?

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

  • CEMEH

    Надо проверить на VS2008 и багу им чтоли послать…
    Что конечно не отменяет твоих пойнтов.

  • shodan

    Мы разок нарвались на багу в кодогенерации на арифметике (не особо сложной).
    Послали 10-строчный repro.

    Hotfix получили где-то через год.
    С тех пор я знаю один ловкий ход для рекламы своих сервисов по поддержке!

  • YE

    Why does the last example mix logical and bit operations?
    What’s the behavior with ~, |, & on one hand, and ~, ||, && on the other?

  • shodan

    YE, it doesn’t. All operations are on bit level in both cases, intentionally.

  • CEMEH

    YE has a good point. “!” is not a bit-level operation, “~” is.

  • YE

    Sorry, of course I meant:
    What’s the behavior with ~, |, & on one hand, and !, ||, && on the other?

  • shodan

    YE, you are right and I was wrong; the results are indeed different. I must had copied wrong, older version.

    However, if we used ~ instead of ! there’s still 20% difference. I updated the post and attached source.

    If we use boolean ops everywhere (ie. ! and || and &&) it manages to optimize everything OK.

  • htfv2

    А не пробовал представить что случиться, если к членам будут обращаться два и более потока? Например один поток обновляет счетчик, другой его читает? Тогда, если компилятор не будет писать в память, второй поток “увидит” только начальное и конечное значения.

    Может у МС компилятор и не самый быстрый, но и не производит глюков из-за переоптимизации. А критиковать могут все.

  • shodan

    > А не пробовал представить что случиться, если к членам будут обращаться два и более потока?

    А с какого перепоя компилятор об этом должен беспокоиться?!
    В стандарте нигде не гарантируется порядок чтения или записи в память для многопоточных случаев.

    Хуже того, он не всегда гарантируется процессором.
    Добро пожаловать в эпоху out-of-order конвейеров.

    > А критиковать могут все.

    Секцию “мораль” перечитай.

  • htfv2

    Допустим, компилятор не должен беспокоится. И допустим, у тебя все таки были бы два потока. Как бы ты писал код? Или ты написал бы другой гневный пост? Мол, в 2007 компилятор не знает про потоки!

    Из двух зол выбирают меньшее. И МС выбрала надежность — работает в обоих случаях, пусть и не быстрее всех. А нужен компилятор, который не о чем не беспокоится, возьми интеловский.

  • shodan

    > Допустим, компилятор не должен беспокоится.

    Во-1х – не “допустим”, а по стандарту ни разу не должен.
    Понятно ли это?

    Ты поискал бы на досуге в стандарте слово thread вместо гаданий на кофейной гуще.
    Получишь просветление, уверяю.

    Во-2х – повторяю еще раз, порядок доступа к памяти нонче не гарантирован.
    Вообще никак не гарантирован, причем ПРОЦЕССОРОМ. См. out-of-order.
    Понятно ли это?

    > Или ты написал бы другой гневный пост? Мол, в 2007 компилятор не знает про потоки!

    Код бы я писал так, как положено с потоками – через соотв-е синхронизационные примитивы.
    И от компилятора ничего ни требовать, ни ожидать в таком случае нельзя – см. слово thread в стандарте.

    > И МС выбрала надежность — работает в обоих случаях,

    Ни от чего не спасает с тредами, тормозит без них – отлично работает, ага.
    Пост, впрочем, далеко не про MS bashing – читай ВНИМАТЕЛЬНО – НИ ОДНОГО слова на тему “компилятор говно” в нем нет.

  • htfv2

    синхронизационными примитивами ты бы защищал член класса, в который компилятор не пишет? и это как надо? не говоря уже о том, что если один поток модифицирует, а другой использует это значение только для отображения, синхронизация вообще не нужна. может компилятор должен знать о всех примитивах и писать в память? это ТАК надо? а если ты используешь особую библиотеку синхронизации для специфичной платформы?

    ищущим просветления рекомендую поискать слово register. но даже оно не гарантирует того, что переменная будет соптимизирована в регистр. если тебе не нужно значение в другом месте, какого черта ты его вынес из скопа функции?

  • htfv2

    и если уж ты обратился к стандарту, то покажи мне место, где описано, как компилятор должен оптимизить код? почему ты вообще решил, что он должен это делать?

  • shodan

    > ищущим просветления рекомендую поискать слово register… какого черта ты его вынес из скопа функции?

    Дорогой.

    Даже если ты тот самый разработчик MSVC, который принял решение отказаться от оптимизации в описанном случае, и чувствуешь себя сильно уязвленным – скучно хамить иди отсюда на хер, кому-нибудь еще.

    Корректно обсуждать техническую сторону я готов – перегавкиваться с дешевым хамлом не собираюсь.

  • htfv2

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

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

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

  • Sergei_am

    htfv2, если 2 потока читают переменную, то компилятор тут уже ничем помочь не может и не должен.
    Если тебе нужна коректная работа в етом случае, то надо юзать примитивъ синхронизации какие-то, ибо даже компайлер не знает, когда переменная скажем сбросится из кеша в память, что критично для потоков/ниток работающих на ядрах, которъе не юзают обший кеш.
    Вообще, компайлер тут ни при чем imho и данная его особенность никак не может бъть оправдана каким либо стремлением к коректности в многопоточном случае.

  • htfv2

    Компилятор не знает и не должен знать, что есть кэши. Это забота железа. Если два процессора обращаются к одному адресу, кэш будет принудительно сброшен. Поэтому и сложно написать программу эффективно работающую на двух процессорах (не HT и не Dual Core, а именно два процессора), каждый из которых имеет локальную память.

    Второй человек уже упоминает синхронизационные примитивы, но не может объяснить как они могут помочь? Если компилятор не пишет в память, что защищать? Или каким-то магическим способом, компилятор узнает, что программа многопоточная? Или кэши от этого заработают иначе?

    Компилятор не знает и не должен… это похоже на фантастику. Должен, еще как должен. Так же как должен знать, например, о выравнивании адресов или чередовании команд. Эти знания вас ведь не смущают? Компилятор для того и есть, чтобы знать о процессоре и его особенностях.

    Уже в простой ситуации при предложенной автором оптимизации появляются побочные эффекты даже (!) на одном ядре с кэшем или без него. Но запустите предложеный мной вариант программы — он будет работать и на двух-процессорной системе.

    Не надо ассоциировать многопоточность с синхронизационными примитивами. Это не актуально. Даже interlocked операции считаются медленными и вредят масштабируемости. А использование синхронизационных примитивов в большинстве случаев приводит к переключению контекста. А уж в этом точно ничего хорошего нет.

  • look4awhile

    to htfv2:
    давайте я попробую объяснить понятно.
    прежде всего чтение, по степени подробности

    http://msdn2.microsoft.com/en-us/library/12a04hfd(VS.80).aspx
    http://blog.gamedeff.com/?p=44
    http://www.nwcpp.org/Downloads/2007/Machine_Architecture_-_NWCPP.pdf

    если на пальцах, тезисно
    0. С++ никаких гарантий при доступе к памяти не даёт вообще.
    1. в С++ есть ключевое слово volatile, которое предназначено для работы с объектами, которые могут быть модифицированны вне контекста программы. на практике это означает что переменная когда нибудь будет записана, и всегда будет прочитана при всяком использовании. порядок записи, latency итп это слово не гарантирует.
    2. на основе такого ключевого слова обмениваться данными между потоками нельзя. примеры есть по приведённым ссылкам (3-ей). если вдуматься – их нетрудно сконструировать итак.
    3. для того чтобы гарантировать такой обмен данными нужны примитивы синхронизации, т-е atomic операции, которые гарантируют порядок обмена данными.

  • IronPeter

    Вот человек хорошо пишет, с примерами.

    http://ridiculousfish.com/blog/archives/2007/02/17/barrier/

    А так конечно забавная дискуссия.

  • shodan

    > я тебе поставил простую задачу:

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

    > задал простой вопрос, как быть в данной ситуации, если компилятор соптимизирует запись в переменную. ответа или обоснования не получил.

    Ответ был даден (см. про синхронизационные примитивы).
    Если ты его не заметил в угаре, это твои проблемы.

    > назван хамом. я не хамил,

    Тон и форма твоих постингов меня не устраивает, и корректным общением я их назвать категорически не могу.
    Лично я (лично я) их расцениваю как хамство в свой адрес.

    Понятно ли это?

    > про другие подумать ты не можешь.

    Это, я так понимаю, ты опять “не хамишь”?
    Если ты вот так “не хамишь” – ты иди, иди на хер-то – уже не трать время на общение с недоумками типа меня.