Преждевременная оптимизация , анализ и выводы.

[Qraizer]

Часто приходится слышать хулящие преждевременную оптимизацию отзывы. Мол, зло это. И вроде мало кто с этим спорит, но и мало кто аргументирует. Может давайте попробуем показать на примере? Или опровергнуть, а то мало ли, вдруг это всё лентяи напридумывали, чтоб поменьше работать над кодом.
Итак, возьмём простую задачу: написать функцию, вычисляющую среднее арифметическое двух целых чисел и возвращающую результат так же в виде целого. Чтоб не совсем уж настолько просто, вспомним, что прямое решение в виде полусуммы аргументов сталкивается с проблемой переполнения, тогда как результат всегда будет находиться в пределах диапазона типа параметров. Поэтому дополним функцию требованием быть устойчивой к возможному переполнению. Идея этого примера родилась из недавнего холивара, участники которого весьма эмоционально пытались отстоять свои позиции, так что рассматриваемые тут функции являются в немалой степени реализациями предложенных ими вариантов.
Для начала возьмём вариант с беззнаковыми целыми, как более простой. Итак, первый кандидат:

unsigned avg(unsigned x, unsigned y)
{
  if (x > y) return y + (x - y) / 2;
   else return x + (y - x) / 2;
}

Идея ухода от переполнения банальна: заменить сложение вычитанием. Правда тут мы сталкиваемся с переполнением в обратную сторону, поэтому приходится использовать ветвление, чтобы избежать отрицательных промежуточных результатов. Известно, что ветвление - это плохо... Ну что ж, заодно и проверим.
Всё-таки хочется по возможности избежать ветвлений. Первое, что при этом приходит в голову - раскрыть скобки и получить т.о. сумму половин аргументов вместо их полусуммы. Вариант, предложенный Дер-ом, кстати. У него есть, однако, важный недостаток: у него ниже точность, ведь целочисленных делений теперь два. Но его несложно поправить, правда, ценой дополнительных вычислений, что и сделал OpenGL:

unsigned drgl(unsigned x, unsigned y)
{
  return (x>>1) + (y>>1) + (x&y&1);
}

Вот, уже лучше. Однако можно улучшить и иначе - вообще уйти от арифметических операций к битовым. Как известно, однобитный сумматор легко строится на одном AND для старшего бита результата и одном XOR для младшего. Несложно, вспомнив об идее SIMD, распространить это на 32-битный сумматор и получить что-то вроде (((x&y) << 1) + (x^y)) >> 1, где арифметический + всё-таки нужен, чтобы учесть переносы старших битов двухбитных сумм, но зато всего один. Осталось только избавиться от избыточного сдвига влево, заодно победив и переполнение, чтобы получить вариант dliauchuk-а:

unsigned mean(unsigned x, unsigned y)
{
  return (x&y) + ((x^y) >> 1);
}

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

unsigned port(unsigned x, unsigned y)
{
  return (static_cast<unsigned long long>(x) + y) / 2;
}

Теоретически тут требуется ещё один каст для самого результата. Но т.к. возвращаемое значение и так указывает требуемый тип, компилятор способен сам выполнить неявный каст, а реально, учитывая, что после деления старшая половина long long-а всегда будет нулевой, это необязательно. Оптимизатор видимо тоже это прощёлкивает, поэтому я не наблюдаю даже варнинга. Тем не менее, если Вам компилятор ругается, можно и добавить. Я не стал, чтобы код был прозрачнее.
Думаете, всё? Как бы не так. Если уж говорить об оптимизации, то нужно рассмотреть и такие агрессивные средства, как аппаратнозависимые. Тут, к сожалению, придётся забыть о портабельности, вспомнить об ассемблере и некоторых его архитектурных особенностях. Естественно, невозможно учитывать всё многообразие процессоров, поэтому я остановил выбор только на одной архитектуре, естественно x86.
Итак, первый камень бросил тот же dliauchuk. Совершенно справедливо заметив, что при сложении двух 32-битных чисел результат всегда будет укладываться в 33 бита, причём старший 33-й бит автоматом попадает во флаг переноса и при обычном сложении, а x86 имеют замечательную способность вращать аргументы вместе с этим флагом как дополнительным битом, он побил все рекорды краткости:

unsigned cool(unsigned x, unsigned y)
{
  __asm mov eax, [x];
  __asm add eax, [y];    // в CF самый старший (дополнительный) бит результата
  __asm rcr eax, 1;      // сдвинуть 33-битный результат (деление на 2)
}

Замечательный результат! Может и соревноваться не сто́ит? Ну уж нет. Сравнивать так сравнивать. Если честно, меня это решение слегка покоробило. В первую очередь оригинальностью. Так что не менее оригинальная мысль меня посетила аж на следующий день.
А мысль звучала так. Избежать ветвлений можно и иначе. Ведь ещё в первых P6 aka Pentium Pro, где сбросы конвейера при неверно предсказанных переходах впервые стали очень дороги, Intel ввела в систему команд условные пересылки cmovXX, эдакие аналоги предикатных команд, присутствующие во многих RISC-архитектурах. Да и ранее уже имелись команды setXX, выполняющие вместо переходов запись результата в виде bool в байтовый регистр. Вот если взять лобовое решение и убрать оттуда переход, заменив условной пересылкой... Правда, для этого нужно получить оба результата, т.е. по двум формулам. Хм, оптимизация, называется... а собственно, всего-то надо вычислять их одновременно за (хотя бы примерно) то же время... на двух ядрах, что ли? CUDA? ...не, ну это бред, конечно, но почему бы и не уже упоминавшийся SIMD в лице MMX? В общем, решил я приколоться, прекрасно осознавая, что для единичных вычислений упаковка/распаковка съест весь выигрыш да ещё и в накладе не останется. Заодно протестим и другой аспект оптимизации.
Итак. Вот функция, основанная на стандартных векторных классах от MS. (Точнее, они впервые были представлены Intel. Как они позже попали к MS, не знаю. Но они и там, и там очень похожи.)

unsigned ivec(unsigned x, unsigned y)
{
  Guard    guard;                // В конце блока будет EMMS
  Iu32vec2 m1(x, y),             // Первая формула - младший DWORD в MMX packed qword,
           m2(y, x);             // вторая         - старший DWORD.
 
  m1 += ((m2-m1) >> 1);
 
  return _MM_2UDW((x<y), m1);     // Выбор старшего или младшего DWORDа
}

Надо сказать, что это решение в общем-то даже вполне переносимо. И MSный, и Intel-ный компиляторы осведомлены об MMXовых интринсиках, для остальных же несложно набросать #define-ы или inline-ы. Естественно, для не x86 (или для x86 без MMX, если вы таковые сможете найти) они интереса не представляют. Единственно что, для этой функции нужен простенький классик

class Guard
{
public:
  ~Guard() { empty(); }
};

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

unsigned mmx(unsigned x, unsigned y)
{
  __asm
  {
   mov       eax, [x]
   mov       edx, [y]
   movd      mm0, eax    // 0 x                 в mm0
   movd      mm1, edx    // 0 y                 в mm1
   cmp       eax, edx    // определение правильного DWORDа
   punpckldq mm1, mm0    // y x                 в mm1
   punpckldq mm0, mm1    // x y                 в mm0
   psubd     mm0, mm1    // x-y y-x             в mm0
   psrld     mm0, 1      // (x-y)/2 (y-x)/2     в mm0
   paddd     mm1, mm0    // y+(x-y)/2 x+(y-x)/2 в mm1
   movd      ecx, mm1    // младший DWORD
   punpckhdq mm1, mm1    // старший DWORD в младший
   movd      eax, mm1    // исходно старший DWORD
   cmovnb    eax, ecx    // выбор правильного DWORDа
   emms                  // Вуаля, бранчей нет
  }
}

Помимо всего прочего, тут я постарался не потратить зря ни единого такта.
Ну, 7-ми вариантов, наверно, хватит. Сложно было остановиться, потому что были мысли касательно std::valarray<>. Но это уже была бы паранойя. (Впрочем, я всё-таки попробовал, результат хуже на 2 порядка.)
Ну что, уже интересно? Однако, сначала закончим с функциями. Теперь уже работающими со знаковыми целыми. С ними основная проблема та, что для отрицательных результатов сдвиги дают округление не то, какое требует Стандарт для делений. А именно к -∞ вместо 0. Это значит, что каждая функция со сдвигами должна содержать коррекцию отрицательного результата.
Вот, к примеру, аналог первой:

signed avg(signed x, signed y)
{
  signed tmp;
 
  if ((x^y) < 0) tmp = (x + y) >> 1;
   else tmp = x + ((y - x) >> 1);
 
  return tmp + (tmp<0 && (x^y)&1);
}

Здесь нейтрализация переполнения выполняется также заменой суммы на разность, только критерий выбора формулы другой, т.к. следует учитывать не величину параметров относительно друг друга, т.к. мы теперь можем работать с отрицательными числами, а их знаки, т.к. при суммировании переполнение может случиться при одинаковых знаках. Кроме того, если тут использовать деление, что оно хоть и будет выполнено по Стандарту, т.е. к 0, но результат второй формулы может отличаться от точного (что было выявлено тестами), если разность будет отрицательна. Коррекция этой разницы более накладна, чем "стандартной" для остальных функций, поэтому тут вместо деления тоже используется сдвиг. Так что коррекция отрицательного результата, выполняемая в return, та же, что и у других функций.
Что любопытно, следующие две функции остались без изменений, если не считать коррекцию и типы:

signed drgl(signed x, signed y)
{
  signed tmp = (x>>1) + (y>>1) + (x&y&1);
 
  return tmp + (tmp<0 && (x^y)&1);
}

signed mean(signed x, signed y)
{
  signed tmp = (x&y) + ((x^y) >> 1);
 
  return tmp + (tmp<0 && (x^y)&1);
}

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

signed port(signed x, signed y)
{
  return (static_cast<signed long long>(x) + y) / 2;
}

тоже ожидаемо не изменилось. Даже коррекции нет, т.к. тут используется арифметическое деление.
А вот с непортабельными функциями интереснее. Во-первых, аналогом флага переноса для знаковых целых является флаг переполнения, а система команд x86 не имеет для него такой же удобной аналогичной. К тому же знаковые данные имеют на один значащий бит меньше, чем беззнаковые, и дополнительный 32-й значащий бит при переполнении инвертирует бит знака. Так что в итоге функция cool() приобрела следующий вид:

signed cool(signed x, signed y)
{
  __asm
  {
   xor  eax, eax
   mov  ecx, [x]
   mov  edx, ecx
   add  ecx, [y]
   seto al               // Получаем признак переполнения
   sar  ecx, 1           // Делим на 2 (и сохраняем текущий знак)
   ror  eax, 1           // Перемещаем признак переполнения в знаковый бит
   xor  edx, [y]         // x^y
   and  edx, 1           // (x^y)&1
   xor  eax, ecx         // Восстанавливаем правильный знак
   sets cl               // tmp<0 (весь ecx нулить не нужно: edx и так будет либо 0, либо 1)
   and  edx, ecx         // Готовая компенсация для отрицательного
   add  eax, edx         // Вуаля, бранчей нет
  }
}

Жёстко. С учётом коррекции отрицательных - так совсем. Зато нет ветвлений. Мда... Ну ладно, посмотрим. Портабельные функции в общем-то тоже не блещут.
Во-вторых, MMXовые функции сталкиваются с несимметричностью формул. Так что пришлось немного потрудиться, сделав их симметричными. Плюс опять же компенсация.

signed ivec(signed x, signed y)
{
  Guard    guard;        // В конце блока будет EMMS
  Is32vec2 m1(y, y),     // Первая формула - старший DWORD в MMX packed qword,
           m2(x,-x),     // вторая         - младший DWORD.
           m3(Is32vec2(0, x) + ((m2+m1) >> 1));
 
  m3 += cmpgt(Is32vec2(0), m3) & (m1^m2) & Is32vec2(1, 1); // Компенсация при отрицательном
 
  // Выбор старшего при разных знаках операндов, младшего при наоборот
  return _MM_2DW(((x^y) < 0), m3);
}

Класс Guard естественно не изменился.

signed mmx(signed x, signed y)
{
  __asm
  {
   mov       edx, [y]
   mov       eax, [x]
   movd      mm0, edx    // 0 y               в mm0
   movd      mm1, eax    // 0 x               в mm1
   pxor      mm2, mm2    // 0 0               в mm2
   psubd     mm2, mm1    // 0 -x              в mm2
   punpckldq mm0, mm0    // y y               в mm0
   punpckldq mm2, mm1    // x -x              в mm2
   movq      mm3, mm2    //                 и в mm3 на будущее
   mov       ecx, 1      // Подготовка единиц в mm2
   paddd     mm2, mm0    // y+x y-x           в mm2
   psrad     mm2, 1      // (y+x)/2 (y-x)/2   в mm2 (деление заменено сдвигом)
   paddd     mm1, mm2    // (y+x)/2 x+(y-x)/2 в mm1
   pxor      mm4, mm4    // 0 0               в mm4
   movd      mm2, ecx    // 0 1               в mm2
   pcmpgtd   mm4, mm1    // tmp (hi и lo) < 0 в обоих DWORDах mm4 (0 или -1)
   pxor      mm3, mm0    // y^x               в обоих DWORDах mm3 (знак x пофигу, важен младший бит)
   punpckldq mm2, mm2    // 1 1               в mm2
   pand      mm4, mm3    // tmp<0 & (y^x)     в обоих DWORDах mm4 (0 или не 0)
   pand      mm4, mm2    // компенсации в mm4 (0 или 1) готовы
   xor       eax, edx    // знаки операндов
   paddd     mm1, mm4    // компенсации из mm4 учтены
   movd      eax, mm1    // младший DWORD
   punpckhdq mm1, mm1    // старший DWORD в младший
   movd      edx, mm1    // исходно старший DWORD
   cmovs     eax, edx    // выбор правильного DWORDа
   emms                  // Вуаля, бранчей нет
  }
}

Тоже не впечатляет. Зато опять же без ветвлений.
Ну что ж, теперь о методике тестирования.
Сначала были написаны тесткэйзы для тестирования корректности реализаций. Таковых для беззнаковых оказалось 16 штук: 3+1 - тестирование единственного класса эквивалентности входных параметров и целочисленности деления, столько же на тестирование двух классов эквивалентности совокупности обоих параметров, 2+2 - тестирование на робастность каждого из параметров и 4 - тестирование на робастность совокупности параметров. А вот для знаковых - целых 48. Во-первых, за счёт 4 классов эквивалентности совокупности параметров по новому критерию, во-вторых, ещё один класс эквивалентности для каждого параметра при тестировании на робастность. (При тестировании все функции показали абсолютное совпадение реальных и ожидаемых результатов.) Затем этот набор данных использовался для циклического заполнения тестового массива, чей размер был выбран из расчёта ¾ кэша второго уровня. Общее количество тестовых пар было эмпирически выбрано в 10⁹, что даёт приемлемое время тестирования одной функции в несколько секунд на современном железе.
Определения функций при тестировании были доступны компилятору, чтобы разрешить агрессивную оптимизацию их тел, но результат отработки функции накапливался XORами и в итоге тоже выводился на консоль, чтобы предотвратить чрезмерную оптимизацию, из-за которой вызовы могли тупо быть выкинуты из-за неиспользования результата. Время замерялось с использованием RTL, предоставляемых стандартной библиотекой в <ctime>. Предварительно использовался холостой прогон по тестовому массиву без замера времени, чтобы вычистить кэш от "мусора". Циклическое заполнение массива достаточно корреляционное, поэтому оно дало возможность процессору продемонстрировать возможности по предсказанию переходов. Однако для пущей объективности после тестирования всех функций массив перемешивался алгоритмом std::random_shuffle<>, и функции, потенциально могущие содержать в себе ветвления, перетестировались. Инициализация генератора случайных чисел не выполнялась, что даёт воспроизводимость результатов от запуска к запуску и объективность тестирования на разных компиляторах.
Используемые компиляторы. Я ограничился двумя:

• Microsoft ® C/C++ версии 15.0 из состава Microsoft Visual Studio 2008 Express Edition (командная строка в консоли "cl -EHs -O2 -GL -arch:SSE2 testing.cpp");
• Intel® C++ Compiler версии 11.1 (командная строка в консоли "icl -EHs -O3 -Qip -QxSSSE3 testing.cpp")

Эти компиляторы умеют MMX. Понятно, что это малость необъективно. Если у кого есть желание, можете перенести аппаратно-зависимые тесты на другие компиляторы или хотя бы ограничиться на них портабельными функциями. Замечу, что MSный компилятор ругается варнингами на отсутствие EMMS в конце перегруженных в векторных классах операторов, что в принципе правильно, но в данном случае естественно совершенно лишнее. А вот в Intel-ном компиляторе попутно обнаружился глюк. Его оптимизатор выкинул EMMS из функции ivec(), что в общем-то логично, но и не поместил её нигде за циклом тестирования, т.к. посчитал, что FPU нигде не будет использоваться, однако сам же себя и обманул, т.к. заюзал FPU для каста long long во float. Глюк наблюдался в любых режимах оптимизации за исключением -O1. В общем, это послужило причиной смены принципа замера времени (изначально планировалось использовать отличный от описанного здесь). Для полноценного использования этого компилятора пришлось обзавестись свежей шароварной лицензией.
Используемые ОС и железо.

1. Windows XP x86 Pro RUS SP3, Intel-P45/P43, Pentium® Dual-Core E6300 2.8ГГц 2Mb cache, 3Гб RAM DDR-667.
2. Windows XP x86 Pro RUS SP3, SiS-661FX, Pentium® 4 Celeron 2.54ГГц 256Kb cache, 1Гб RAM DDR-400.

Приведу полный код обоих тестов.
Вот беззнакunsigned.cpp (9,4 Кбайт, скачиваний: 787) , а вот и знакsigned.cpp (13,87 Кбайт, скачиваний: 550) .
Считайте это OpenSource.
Итак, пора компилировать и запускать. Замечу, что следствием предотвращения ультраоптимизации является вывод на консоль большего количества данных, чем нужно. Это видно и из сырцов. Нас будут интересовать строки с именами функций, а именно первые числа в них, которые показывают время исполнения 10⁹ раз вызванной соответствующей функции в миллисекундах. Первое железо. Беззнаковая арифметика. Microsoft Visual C++ 2008.

B:\2del\unsigned>vc.exe
4294967288
mean: 1968      0
avg:  2891      0
drgl: 2125      0
port: 2641      0
cool: 3671      0
ivec: 15579     0
mmx:  5343      0
4294967288
avg  (no branch prediction): 5953       0
ivec (no branch prediction): 15547      0

Если кратко, то победила портабельность. И какая - SIMDовая битовая. Не очень удивительно, впрочем, учитывая, что mean() не содержит ветвлений и имеет меньше операций, чем drgl(). Гораздо интересны остальные результаты. Весьма неплохое время показало лобовое увеличение разрядности (port()), и совсем немного от него отстала стандартная avg(), если дать предсказателю ветвлений достаточно достоверной статистики. А вот без таковой avg() с треском проваливается - теряется больше половины производительности. Первый вывод: не следует недооценивать предсказание переходов, если код обрабатывает достаточно детерминированые данные. И уж совсем удивил лидер лаконичности. Полазив по Intel-овой документации, я выяснил, что вот эта вот замечательная RCR reg, 1 требует для исполнения обоих портов и от 5 до 7 тактов. Вот и ответ. Тормозить оба порта на 7 тактов, это вам не парой пальцев об асфальт. На её фоне такая же ROR просто душка - всего-то нужны свободным 0-й порт и один такт. Второй вывод: избегать сложных инструкций категорически важно.
Что же касается MMX, то тут довольно ожидаемо. Упаковка двух параметров в единое 64-битное упакованное и последующая обратная распаковка результатов делает своё дело, тактов не напасёшься. Впрочем, ручной код всё равно умудрился обогнать "непредсказуемую" avg(), что немного радует . А печалит то, что сгенерированный компилятором код оказался ниже плинтуса. Посмотрев в ассемблер, я там увидел такие огрехи, какие не допустил бы, пожалуй, и новичок в MMX. Даже предсказуемость переходов - а они там-таки были - мало повлияло на настолько неэффективную кодогенерацию. Третий вывод, хоть и частный: иногда имеет смысл применить MMX там, где ему казалось бы не место, но не доверяйте компилятору. Впрочем, такое внимание реализаций к MMX вполне объяснимо. Когда MMX был ещё в отрочестве, оптимизаторы были маленькие и глупые. Когда же они научились сами более-менее адекватно генерировать SIMD, MMX был уже стар и мало кому интересен. Если найдутся желающие переписать SIMD-функции на SSEx, милости прошу, добавим к отчёту. Я не увидел особого смысла дальше пытаться считать овец по количеству ног.
Давайте посмотрим теперь на Intel C++ Compiler 11.1.

B:\2del\unsigned>intel.exe
4294967288
mean: 1750      0
avg:  3031      0
drgl: 2640      0
port: 1672      0
cool: 3016      0
ivec: 6812      0
mmx:  5969      0
4294967288
avg  (no branch prediction): 3063       0
ivec (no branch prediction): 6828       0

Отонокак. Увидев вот это, я сказал "брр-р-р..." и запустил ещё раз. Впереди планеты всей оказалась 64-битная арифметика, на мизер, но-таки обогнав mean(). А вот avg() сильно удивила. Во-первых, элементарная целочисленная арифметика - и Intel-овый компилятор уложен на лопатки какой-то там - фи - MicroSoft. Во-вторых, вот чего у Intel не отнять, свои процессоры она знает великолепно. Детерминированы данные или нет, avg() показала практически одинаковые результаты. Собственно, я думаю, как раз поэтому она немного и проиграла MicroSoft-у, ИМХО выиграв в целом. Ну и генерённый MMX тоже порадовал, разница от ручного кода не так велика. Самое любопытное, компилятор умудрился в cool() смягчить негатив от RCR, переставив код вокруг неё так, что она в результате сравнялась с avg().
Вторая серия тестов. Теперь знаковая арифметика. Обратите также внимание: количество функций с потенциальными ветвлениями увеличилось. К сожалению, что в беззнаке планировалось и удалось сделать без бранчей, в знаке возможно только с отклонением в точности результата. Microsoft Visual C++ 2008.

B:\2del\signed>vc.exe
-3
mean: 4375      0
avg:  6234      0
drgl: 4797      0
port: 16297     0
cool: 4609      0
ivec: 18938     0
mmx:  7171      0
-3
mean (branch prediction suppressing): 8969      0
avg  (branch prediction suppressing): 11594     0
drgl (branch prediction suppressing): 9468      0
ivec (branch prediction suppressing): 20453     0

Времена ожидаемо больше. И распределение мест почти то же. Но есть и отличия. Так, 64-битная арифметика с отрывом ушла в арьергард. Зато cool() не посрамила, доказав конкурентоспособность инструкций SETxx на фоне даже предсказанных ветвлений. Ну и ручной MMX не подкачал, всё-таки CMOVxx тоже не лыком шиты перед некоррелированными ветвлениями. И это несмотря на её размер, явно остальные функции имеют меньше инструкций. Да и её отрыв от других функций не настолько большой, как в беззнаке.
Теперь Intel C++ Compiler 11.1.

B:\2del\signed>intel.exe
-3
mean: 5140      0
avg:  6110      0
drgl: 5765      0
port: 4672      0
cool: 4125      0
ivec: 9906      0
mmx:  6859      0
-3
mean (branch prediction suppressing): 6859      0
avg  (branch prediction suppressing): 7593      0
drgl (branch prediction suppressing): 7532      0
ivec (branch prediction suppressing): 9859      0

И снова я с первого раза не поверил тому, что увидел. Не знаю, как оно вам, но я, обогнав на полсекунды ближайшего конкурента, счастлив . А ближайшим оказалась... 64-битная арифметика, снова отличившись, теперь уже антиколлинеарно, обойдя чемпиона по беззнакам аж на те же полсекунды . Причина же её неудачи у MicroSoft-а банальна: 64-битными операциями у неё заведует специальная внутренняя функция, инлайнить которую компилятор напрочь отказывается. Четвёртый вывод: помогать кодогенератору не всегда полезно, иногда тупое решение оптимизируется на ура и без всяких подсказок. Конечно, не первое место, зато портабельно.
Что касается остальных портабельных решений, то avg() тут более чем скромна, как и у MicroSoft. Компилятору не удалось даже полностью защитить код от недетерминированных данных, так что ручной MMX сделал её и тут. Как и ещё две из трёх оставшихся функций, а вот mean() сопротивляется упорно - ничья!
Для пущей объективности потестим теперь на более слабом железе. Т.к. у процессора кэш в 8 раз меньше, сырцы были рекомпилированы с другим размером тестового вектора. Кроме того, Intel-компилятору было сообщено об иной архитектуре заменой ключа -QxSSSE3 на -QxSSE3.
Беззнаковая арифметика. Microsoft Visual C++ 2008.

B:\2del\unsigned>vc.exe
4294967288
mean: 5406      0
avg:  5782      0
drgl: 5547      0
port: 8734      0
cool: 8547      0
ivec: 105562    0
mmx:  18844     0
4294967288
avg  (no branch prediction): 18218      0
ivec (no branch prediction): 105359     0

Цифры побольше, но качественно картинка та же. По-прежнему лидирует mean(), по-прежнему лаконичная cool() в конце таблицы, только 64-битная арифметика подкачала, даже ещё больше, чем cool(). И по-прежнему предсказанные ветвления держатся молодцом, зато хорошо видно, насколько Prescott-овая архитектура NetBurst чувствительна к капризам своего гиперконвейера: падение производительности - более чем в 3 раза. А вот MMX вообще в глубоком дауне. Ручному не угнаться даже за косяками предсказаний переходов, а генерённый медленнее авангарда почти в 20 раз.
Intel C++ Compiler 11.1.

B:\2del\unsigned>intel.exe
4294967288
mean: 4765      0
avg:  9094      0
drgl: 7391      0
port: 6078      0
cool: 7953      0
ivec: 42172     0
mmx:  19062     0
4294967288
avg  (no branch prediction): 8875       0
ivec (no branch prediction): 42703      0

И снова Intel удивляет. И бог с ним, MMXом - генерённый быстрее MicroSoft-ового почти втрое - посмотрите, как перераспределились места. Только mean() и осталась на своём месте, причём даже улучшила MicroSoft-овый результат. 64-битная port() выпрыгнула на второе место, зато в конце оказалась avg(). Причём недетерминированные данные её не только не смутили, но оказались даже более быстрыми, впрочем, оставив тем не менее на последнем месте. Можно предположить, что Intel разучилась оптимизировать под старые процессоры, но ИМХО это наоборот, MicroSoft наконец-то подтянулась к тому, на что Intel махнула рукой.
Теперь знак. Microsoft Visual C++ 2008.

B:\2del\signed>vc.exe
-3
mean: 8859      0
avg:  10156     0
drgl: 11390     0
port: 110013    0
cool: 13719     0
ivec: 134592    0
mmx:  24515     0
-3
mean (branch prediction suppressing): 27578     0
avg  (branch prediction suppressing): 39999     0
drgl (branch prediction suppressing): 28938     0
ivec (branch prediction suppressing): 132639    0

Ну, не очень-то и надо было. Подумаешь, cool() в хвосте. Зато, как и прежде, ручной MMX уделал "промахивающийся" гиперконвейер. Что совсем уж ни в какие ворота, "коррелированная" avg() оказалась на втором месте, но потеряла в производительности аж вчетверо на недетерминированных данных.
Ну и наконец последняя серия - Intel C++ Compiler 11.1:

B:\2del\signed>intel.exe
-3
mean: 8672      0
avg:  12563     0
drgl: 10375     0
port: 13328     0
cool: 14562     0
ivec: 40031     0
mmx:  24437     0
-3
mean (branch prediction suppressing): 19890     0
avg  (branch prediction suppressing): 25360     0
drgl (branch prediction suppressing): 21313     0
ivec (branch prediction suppressing): 41594     0

И тут чемпионы по новому железу наоборот в самом тылу, хоть и не таком глубоком. С avg() по-прежнему бардак, зато разрыв по детерминизму сократился до двух раз вместо трёх, но ручной MMX и тут умудрился её обогнать. Вообще, что касается MMX, сложилось такое впечатление, что Целерону банально не хватает пропускной способности шины. Видимо данные не успевают попадать в кэш первого уровня, потому конвейер теряет такты. Ибо производительность MMX у него заявлена вполне на уровне.
Ну что ж, частные выводы сделаны, дело за окончательными. Вывод, какой-то на очереди... ага, пятый: тезис о преждевременной оптимизации не врёт. На создание и отладку этих функций было потрачено в общей сложности 3 дня. Сюда включено всё - выдумывание алгоритмов, реализация, создание теста, его отладка, тестирование функций, коррекция их алгоритмов и наконец документирование - ибо всё это пришлось бы делать и в реальном проекте. Многовато для погони за эфемерным выигрышем ~2,5 секунды на миллиард вызовов, при том, что они оптимизируются максимально агрессивно, что вообще-то будет далеко не всегда, не во всех проектах и тем более не для всех функций.
Вывод шестой: нет смысла оптимизировать функцию, если она будет располагаться в общей библиотеке. Нет, конечно это не означает, что её можно писать, как бог на душу положит. Это означает, что не следует делать из оптимизации религию. Не пессимизировать вполне хватит на все случаи жизни в качестве быстрого старта. Не зная компилятора, Ваша оптимизация у пользователя библиотеки может вылиться в пессимизацию. Максимум, что можно позволить, ультраоптимизацию под конкретный компилятор, но и тут будут проблемы с пессимизацией на некотором железе. Вывод седьмой: не верьте очевидному. cool(), port() и mmx() это наглядно показали. Конечно, неудача MMX для детерминированных данных вполне была предсказуема, но успех для недетерминированных, особенно для такого капризного NetBurstового конвейера, и для меня был сюрпризом.
И конечно результаты выше не означают, что MMX плох. Дополнительный эксперимент, моделирующий микширование 16-битного стереозвука в один канал с помощью того же простейшего среднего арифметического, показал, что для многословных массивов, где не требуется упаковка/распаковка, MMX даёт 6-кратный прирост, даже генерённый - и тот дал 4-кратный. Вот функции, можете запросто проверить сами:

void standard(const unsigned short* x, const unsigned short* y, size_t count, unsigned short* z)
{
  for (size_t i=0; i<count; ++i)
   z[i] = (x[i] + y[i]) / 2;
}
 
void ivec(const Iu16vec4* x, const Iu16vec4* y, size_t count, Iu16vec4* z)
{
  Guard guard;
 
  for (size_t i=0; i<count/4; ++i)
   z[i] = (x[i] + y[i]) >> 1;
}
 
void mmx(const Iu16vec4* x, const Iu16vec4* y, size_t count, Iu16vec4* z)
{
  __asm
  {
   mov   esi, [x]
   mov   edi, [y]
   mov   edx, [z]
   mov   ecx, [count]
   xor   eax, eax
   shr   ecx, 2
L:
   movq  mm0, [esi+eax*8]
   movq  mm1, [edi+eax*8]
   inc   eax
   paddw mm0, mm1
   psrlw mm0, 1
   movq  [edx+eax*8-8], mm0
   cmp   eax, ecx
   jb    L
   emms
  }
}

Честно говоря, не помню, почему я не стал заморачиваться знаковостью (16-битные звуковые отчёты вообще-то стандартно знаковые). Так же не стал учитывать возможную некратность четырём размера массивов.
Знаковая арифметика даётся тяжело. Замечу, что функции могли бы быть проще и работать быстрее, если б идеальная точность была бы не нужна. В этом же тестировании упор был сделан на соответствие поведения ожидаемому. Аналогично ведут себя и компиляторы, когда оптимизируют код и подменяют одни инструкции другими. Вывод восьмой: если важна максимальная производительность, имеет смысл рассмотреть менее точные алгоритмы и замену знаковых типов данных на беззнаковые, если это применимо.
Ну и вывод основной: запасайтесь профайлером. Спасибо за внимание.

Boroda aka Qraizer.

Сообщение отредактировано: Qraizer - 13.09.10, 17:35

[amk]

Заметил, что mean во всех тестах, если не лидирует, то, по крайней мере, следует прямо за лидерами. Так что оптимизация все же дала эффект.
Хотя, ИМХО, доводка алгоритма в целом обычно дает эффект более сильный, чем вылизывание отдельных строчек кода.
Подо доводкой я тут имею в виду, как выбор адекватного алгоритма (нет смысла применять сортировку Хоара для сортировки десятка чисел), так и некоторые другие аспекты - например, иногда имеет смысл даже на процессоре с быстрой плавающей арифметикой (сигнальники, например) часть вычислений произвести в целочисленной арифметике, особенно если исходные данные в виде целых.

[amk]

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

Но вот в графике точно главенствуют беззнаковые числа.

Насчет скорости команды RCR. На практике эта команда слишком редко бывает нужна. Описанная ситуация - пожалуй единственная, где ее использование могло бы быть оправданным. Поэтому она реализуется не аппаратным сдвигом, а микропрограммно. Фактически блок сдвигов реализует всего четыре варианта сдвигов - обычный и циклический сдвиги влево и знаковый и беззнаковый сдвиги вправо. В качестве будущего значения флага переноса просто берется нужный разряд исходного слова.
Думается, команда RCL с константным сдвигом на 1 разряд, которую можно выполнить в сумматоре ("RCL R,1" аналогична "ADC R,R") может выполняться быстрее, чем RCR или та же команда, с другим размером сдвига.

Сообщение отредактировано: amk - 18.09.10, 12:54

[leo]

Цитата Qraizer @ 07.09.10, 03:30

пятый: тезис о преждевременной оптимизации не врёт

Преждевременная оптимизация - это когда берешься что-то "оптимизировать" прежде, чем поймешь\изучишь основные принципы\приемы оптимизации
В данном случае речь идет о паре-тройке элементарных арифметических действий. Поэтому если эти действия выполняются не от случая к случаю, а над большими массивами чисел, то в первую очередь стоит подумать о том, стоит ли их выделять в отдельную функцию = способен ли компилятор заинлайнить эту функцию и развернуть цикл - если нет, то простая азбучная оптимизация (отказ от использования функции + разворот цикла) может дать больший выигрыш, чем ловля прочих блох

Цитата amk @ 18.09.10, 12:17

Насчет скорости команды RCR...

В данном случае речь идет о "загадочно\экзотично тормозном\монструозном" P4, точнее об архитектуре NetBurst, в которой и rcr\rcl, и adc\sbb выполняются 7-10 тактов вместо 1-2 на других "нормальных" процах

[AndNot]

А мне хочется упомянуть о еще одном правиле: прежде чем переходить на ассемблер, нужно попытаться упростить алгоритм. Для деления знаковых чисел на 2**n используется общепринятый алгоритм, в котором производится корректировка отрицательных результатов по маске (d-1), где d - делитель. Но, для того же сдвига на единицу маска будер равна 1 и для правильного округления отрицательных чисел алгоритм вырождается лишь в добавлении единицы, перед сдвигом, к отрицательным числам:

signed avg(signed x, signed y)
{
  __asm
  {
        mov     ebx, [y]
        mov     eax, [x]
        mov     ecx, ebx
        cdq                     // edx:eax = x
        sar     ecx, 31         // ebx:ecx = y
        add     eax, ebx
        adc     edx, ecx        // edx:eax += ebx:ecx
        mov     ecx, edx
        sar     ecx, 31         // if (edx:eax < 0) { ecx:ecx = -1 }
        sub     eax, ecx        // коррекция для правильного округления
        sbb     edx, ecx        // edx:eax -= ecx:ecx
        shrd    eax, edx, 1     // edx:eax >>= 1
  }
}

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

[Offtop]

Цитата amk @ 18.09.10, 12:17

Насчет скорости команды RCR. На практике эта команда слишком редко бывает нужна.

Не, это очень полезная и востребованная команда. В тестах асм-вставки проиграли только по одной причине - компилятор их не умеет инлайнить и параметры передает только через стэк. В результате затраты на CALL .. RET и передачу параметров едва ли не превысили время работы самой функции cool. Написанные на Си функции полюбому инлайнились. Отсюда и такие "неожиданные" результаты замеров. Хотя это все измышления по всем процам, кроме P4, я с ним даже не сталкивался.

Цитата amk @ 18.09.10, 12:17

Я могу ошибаться, но на звуковую карту отсчеты вроде уходят в виде беззнаковых.

Еще самые первые звуковухи имели два режима работы: со знаковыми и беззнаковыми данными. Так что тут кому как удобнее.

[Qraizer]

leo, NetBurst - это второе железо. И насколько мне известно, его слабое место - именно сбросы конвейера. В остальном он, вроде, вполне на уровне. Но это так, к слову. На самом деле получить максимальную производительно задачи не стояло. Хотелось сравнить разные функции в равных условиях. Именно это зачастую проделывают при утраоптимизации локальных фрагментов кода, когда перекраивать его структуру уже поздно.
AndNot, принятая мной коррекция для отрицательных была направлена не на коррекцию деления, а на коррекцию цельного результата функции. Например, имея 456 и -123, по первой формуле получим 166, по второй 167. И это при том, что там деления (!), а не сдвиги. Безусловно, если упростить требования, например, посчитав допустимым толеранс в 1 из-за неточности целочисленного деления, формулы для знаковых будут проще. Это и было отмечено в 8-и совете.

[AndNot]

Сань, я хреновый объясняльщик, поэтому попробую по другому.
На Си нет операции арифметического сдвига и нет никаких средств контролировать переполнение. И если проблема переполнения частично решается расширением размерности операндов до двойной точности, то заменить арифметический сдвиг можно только его эмуляцией, через серию беззнаковых сдвигов и исключающего сложения. Все это и отражается на выборе подходящего алгоритма, чему наглядный пример твоя статья.
Так вот, ошибка многих, кто пытается оптимизировать за счет перехода на ассемблер, состоит именно в том, что они пытаются оптимизировать те же самые алгоритмы, что использовали на Си. Но это в корне не правильно, практически всегда есть альтернативные алгоритмы, не реализуемые на языках высокого уровня, но прекрасно подходящие для ассемблера. В данном случае такой алгоритм есть. Это всем известное знаковое деление на степень двойки:

// d = n / 2**k
m = (n sar (k-1)) shr (32-k)
d = (n+m) sar k

Этот алгоритм не подходит для Си, поскольку имеет две операции арифметического сдвига (sar), но он прекрасно подойдет для ассемблера. Поскольку k=1, получим:

m = n shr 31
d = (n+m) sar 1

То есть, алгоритм получился очень простой и идеально подходящий именно для ассемблера.
Проще говоря, нужно правильно выбирать алгоритм, в зависимости от языка его реализации. В этом я и увидел ошибку dliauchuk-а, попытавшегося перенести на асм сишную реализацию, из-за чего signed Cool приняла довольно мудреный вид и без стакана не поддается пониманию. Да и твоя реализация на MMX пошла по тому же пути, по оптимизации именно Сишного алгоритма. По сути это девятое правило - для каждого языка есть свои, наиболее оптимальные для реализации алгоритмы. И это правило позволяет сильно экономить время на написание и отладку кода.

Что касается

Цитата Qraizer @ 20.09.10, 11:46

принятая мной коррекция для отрицательных была направлена не на коррекцию деления, а на коррекцию цельного результата функции

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

Цитата Qraizer @ 20.09.10, 11:46

Безусловно, если упростить требования, например, посчитав допустимым толеранс в 1 из-за неточности целочисленного деления, формулы для знаковых будут проще. Это и было отмечено в 8-и совете.

Это да. Но моя функция выдает те же самые результаты, что и команда процессора IDIV, т.е. никак не попадает под 8-й пункт, иначе была бы в два раза короче

[B.V.]

Qraizer, и только ради этих выводов, которые, к слову, приведены в статье Алана Зейчика "Optimizing Your C/C++ Applications" http://developer.amd.com/documentation/articles/pages/6212004126.aspx, http://developer.amd.com/documentation/articles/pages/7162004127.aspx, ты накатал столько текста, привел столько вариантов кода и провел столько тестов? Поистине, сизифов труд..
Приведенная статья, к слову, хоть и очень короткая, но в ней отмечается гораздо больше приемов оптимизации, нежели в твоем опусе. И, конечно, прослеживается простое правило: скорость выполнения кода не зависит от его размера
Уж лучше бы ты провел тестирование кода с использованием расширенных наборов инструкций. Интересно было бы посмотреть, дают ли какие-нибудь преимущества SSE1-SSE4.x в простых арифметических функциях, и как себя ведет код на разных архитектурах Intel и AMD. В принципе, хватило бы NetBurst, Core, Nehalem со стороны Intel и K10, K10.5 со стороны AMD

[AndNot]

B.V., в тех статьях речь совсем о другом, не имеющим к данной теме никакого отношения

Цитата B.V. @ 21.09.10, 09:23

Уж лучше бы ты провел тестирование кода с использованием расширенных наборов инструкций. Интересно было бы посмотреть, дают ли какие-нибудь преимущества SSE1-SSE4.x в простых арифметических функциях, и как себя ведет код на разных архитектурах Intel и AMD.

Преимущество по сравнению с чем? Если сравнивать с целочисленной арифметикой, то нет. Если с FPU, то в редких случаях. Все это уже давно выяснено Вот различие Intel и AMD конечно интересно. Но где взять компилятор Си под AMD? Такие вообще бывают?

[trainer]

Цитата AndNot @ 21.09.10, 09:53

Но где взять компилятор Си под AMD? Такие вообще бывают?

MSVC сейчас имеет ключик /favor:AMD64

Добавлено 21.09.10, 10:14
А у GCC вообще куча вариантов: http://gcc.gnu.org/onlinedocs/gcc/i386-and-x86_002d64-Options.html

[B.V.]

Цитата AndNot @ 21.09.10, 09:53

B.V., в тех статьях речь совсем о другом, не имеющим к данной теме никакого отношения

Да ладно? Укажешь мне различия?

Цитата AndNot @ 21.09.10, 09:53

Преимущество по сравнению с чем?

С голым x86-ассемблером, конечно

Цитата AndNot @ 21.09.10, 09:53

Все это уже давно выяснено

Ой, да ладно? И где можно поглядеть на реальные тесты int/fp арифметики с расширенными наборами инструкций? Да что бы на разных камушках?

[AndNot]

Цитата B.V. @ 21.09.10, 10:38

Да ладно? Укажешь мне различия?

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

Цитата B.V. @ 21.09.10, 10:38

Цитата (AndNot @ Сегодня, 13:53)
Преимущество по сравнению с чем?

С голым x86-ассемблером, конечно

Давай отделять мух от котлет и не пытаться сравнить железо (SSE) с языком программирования (асмом) Да и я вроде не выдвигал никаких лозунгов, типа асм форевор, си сакс, микрософт маст дай

Цитата B.V. @ 21.09.10, 10:38

Ой, да ладно? И где можно поглядеть на реальные тесты int/fp арифметики с расширенными наборами инструкций? Да что бы на разных камушках?

Опять же, влом искать. Сравнивали FPU (asm) с SSE ©, на матричных операциях, а точнее началось все с банального C vs Asm. Сишники выдали более десятка различных вариантов, откомпилированных различными компиляторами и с разными ухищрениями (попался даже образец адской смеси FPU и SSE перемножения векторов!). Но, как они не старались, так и не смогли обогнать написанный мной, с пьяну глаз, код, хотя бы на десяток процентов. Тесты проводили на разных машинах, включая AMD и корки. Правда в моем коде была махонькая ошибка, но раз никто не заметил, то и я промолчал, она пару процентов выигрывала Но на целочисленных операциях я отыгрался по полной, благо ни один компилятор не умеет самостоятельно юзать MMX
В общем, если есть желание, то я непрочь провести тесты заново, создавай тему, а я поищу в загашниках те тесты, да напишем новые. Будет даже интересно узнать, насколько с тех пор улучшилась аппаратная реализация SSE (а в этом сомнений нет) и оптимизаторы компиляторов. Заодно и целочисленную арифметику протестируем, насколько я знаю CPU vs SSE еще никто не проводил.

[leo]

Цитата Qraizer @ 20.09.10, 11:46

leo, NetBurst - это второе железо

Ах, да, пардон. Тогда интересно, в какой-такой документации Intel ты нашел "от 5 до 7 тактов" RCR reg,1 для семейства P6, поскольку в офиц. оптим-мануалах конкретные цифры для RCL/RCR reg,1 приводятся только для NetBurst (family 0Fh), а для 06h только Throughput = 4 и то для общего случая (без указания второго операнда) ? По данным А.Фога во всех P6 latency\throughput RCL/RCR reg,1 составляют 2\2, что выглядит вполне правдоподобным (с учетом корреляции с adc\sbb)

Цитата Qraizer @ 20.09.10, 11:46

И насколько мне известно, его слабое место - именно сбросы конвейера

Не только, обрати внимание на "загадочно заоблачные" латентности adc\sbb, rcl\rcr, bt.. и bs.., по сравнению с которыми mul\imul и div\idiv являются просто "слегка завышенными" в 2-3 раза

[Qraizer]

Цитата leo @ 21.09.10, 13:27

Тогда интересно, в какой-такой документации Intel ты нашел "от 5 до 7 тактов" RCR reg,1 для семейства P6...

Уже не помню. Счас попробую найти снова.

Цитата leo @ 21.09.10, 13:27

Не только, обрати внимание на "загадочно заоблачные" латентности adc\sbb, rcl\rcr, bt.. и bs.., по сравнению с которыми mul\imul и div\idiv являются просто "слегка завышенными" в 2-3 раза

Ну, все команды я не смотрел. Что сильно удивило, то и посмотрел. Вообще, ассемблер тут присутствует, поскольку рано или поздно кто-то бы всё равно спросил, а почему не рассмотрели ассемблер. Основная тема была всё-таки Плюсовый код.

Цитата AndNot @ 21.09.10, 06:23

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

Та не, я понял, что ты хочешь сказать, но посмотри, что я только что ответил leo. Ассемблер - это крайне агрессивный метод оптимизации, в первую очередь из-за плохой портабельности. Да, я в некоторой степени его коснулся. Но текста и так получилось много, больше, чем я рассчитывал, раза в 2. Так что пришлось ограничиться наиболее интересными результатами. Возможно, есть и более интересные, и более эффективные, но эти по крайней мере... неожиданны, что ли. Да и Плюсовый код можно было бы дополнить. Ради бога, берите приложенные сырцы и экспериментируйте самостоятельно, я не против. Для того и приложил. Добавлять туда новые функции несложно. И было бы неплохо посмотреть на другие компиляторы ещё.
Да, кстати, знаковые функции целиком мои, кроме avg() и port(). Холивар, который я упомянул, касался только беззнака.
B.V., я преследовал несколько иные цели - показать, насколько могут отличаться результаты на разных реализациях и разном железе. Ну и по дороге не обошёл вниманием, что ко всему оказалось ещё и интересным. На предмет других SIMDов уже как-то не очень потенции оставалось, да и железа столько разного в доступе нет. Кстати, целерон тоже уже вне зоны досягаемости, админ забрал .

Сообщение отредактировано: Qraizer - 21.09.10, 15:41

[Qraizer]

leo, не, счас не найду. Доки дома. Могу через Удалённый стол зайти, но это значит кого-то из домашних оттуда согнать.
Впрочем, если нет желания ждать, это было в тем мануалах, которые я недавно выложил в Пополнении полезных ссылок в разделе Ассемблера.

[trainer]

Цитата leo @ 21.09.10, 13:27

RCR reg,1 для семейства P6, поскольку в офиц. оптим-мануалах ... а для 06h только Throughput = 4 и то для общего случая (без указания второго операнда)

06h - это мобильные процессоры. Для них декларируется "one cycle in Pentium 4 processor is NOT equal to one cycle in Pentium M processor" Примечание к таблице говорит, что вариант со сдвигом на 1 разряд является оптимизированным, сдвиг на другое значение является более тормозным. "248966-009 IA-32 Intel® Architecture Optimization" дает для RCR/RCL reg,1 значение 4/1

Цитата leo @ 21.09.10, 13:27

с учетом корреляции с adc\sbb

Документ от Intel "248966-009 IA-32 Intel® Architecture Optimization" дает для ADC/SBB в лучшем случае 6/2. Документ наверное устарел, но видимо хотя бы для части процессоров эти данные правильные.

[leo]

Цитата trainer @ 22.09.10, 04:20

06h - это мобильные процессоры

Нет, 06h это "классическая" архитектура P6 начиная с Pentium II\III, которая была без лишнего шума развита в Pentium M (во времена господства тупиковой ветки NetBurst), и затем стала основой современных Core. Достаточно в винде глянуть в "Сведения о системе" Processor -> Family или переменную окружения PROCESSOR_IDENTIFIER - для вариаций P4 это значение равно 15=0Fh, а для Core = 6
Ну и потом можно глянуть труды А.Фога (microarchitecture.pdf и instruction_tables.pdf), который наверняка свои супер-подробные сведения не из пальца высосал

[B.V.]

Цитата AndNot @ 21.09.10, 13:05

Давай отделять мух от котлет и не пытаться сравнить железо (SSE) с языком программирования (асмом)

Отчего бы не сравнить? Тем более, что я не говорил о ручном набивании инструкций x86, пусть этим занимаются компиляторы с настройками максимальной оптимизации

Цитата AndNot @ 21.09.10, 13:05

В общем, если есть желание, то я непрочь провести тесты заново, создавай тему, а я поищу в загашниках те тесты, да напишем новые. Будет даже интересно узнать, насколько с тех пор улучшилась аппаратная реализация SSE (а в этом сомнений нет) и оптимизаторы компиляторов. Заодно и целочисленную арифметику протестируем, насколько я знаю CPU vs SSE еще никто не проводил.

Желание есть, а вот знаний по SSE нет. То есть, если я и смогу предложить какие-то тесты, то только на высоком уровне с настройками для компилятора, принуждающими использовать тот или иной набор инструкций
Такой вариант подходит?

[AndNot]

B.V., создавай тему, предлагай конкретные тесты. Все желающие смогут выложить скомпилированный сишный код, из которого я выдеру нужную функцию и выложу готовый файл, с сорсами на асме, для замеров всеми желающими, на любых камнях. Эта мудреная схема нужна с той целью, что сишные компиляторы любят "шульмовать" и умело делают не только все возможные предвычисления, но и порой умело разносят вычисления по всему коду екзешника, из-за чего часть вычислений не попадает в замеры времени исполнения. С этим я уже сталкивался, после чего зауважал VC++ и IntelC
Ну и по мере возможности буду предлагать свой код, под FPU и CPU (fixed point).

[AndNot]

Цитата leo @ 22.09.10, 06:08

Нет, 06h это "классическая" архитектура P6 начиная с Pentium II\III

На счет второго пня не уверен, но пень про точно выдавал на CPUID шестерку, как и последующий пень три

[leo]

В доке Intel® Processor Identification and the CPUID Instruction приведена кодировка Family & Model для всех процев от Intel486™ до "наших дней"

PS: Кстати и в упомянутом trainer'ом мануале по оптимизации (по кр.мере в "свежем" 248966-020) перед таблицами латентностей приведена краткая справочка по кодировке Family_Model, в которой представлены все Core и Enhanced Core без различия по мобильности, и соотв-но цифирьки по ADC\SBB нужно смотреть в таблице C-13a, а не в C-13

[Ирокез]

Преждевременная оптимизация – зло в том случае, если она снижает читабельность, или замедляет сочинение исходника. То есть когда увеличивает трудоёмкость создания и/или поддержки. Потому что усилия приложены, когда не известно, будет ли от них толк. Потому что когда окажется, что оптимизация нужна в другом месте, так как именно в другом месте она эффективней, окажется также, что сделанная оптимизация сделана вместо нужной. Может лучше будет вместо этого оптимизировать что-то другое? Ели же оптимизация прозрачна и дополнительного труда не требует, то не имеет значения, на каком этапе она сделана. Более значимой оптимизации она не мешает. Если ты точно знаешь, что быстрей присвоить литерал, чем гонять цикл, а вспомнить двенадцатую степень двойки можешь меньше, чем за секунду, то не имеет значения, сразу ты напишешь

a=4096;

вместо

for (a=1, i=12; i>0; a*=2, --i);

, или потом заменишь. Более того, иногда даже проще оптимизировать сразу, чем вносить изменения. И пофигу, умеет ли компилятор делать ту же замену. Если её не делать, то будет медленнее.