Производительность; илитный запил оптимальных реализаций и основы матчасти.
Поглядел я тут на пацанов и увидел прогресс в их глазах. Поэтому я решил вести тут свой бложик, в котором я буду толкать матчасть, разбирать/разрушать всякие мифы и легенды, а так же их обсуждать с пацанами. Банить меня не надо - тут всё будет очень культурно.
Это будет формат для самых маленьких, где я буду показывать как что-то пилится по-пацаночке. Его задача - на примерах пересказать штеудмануал тем, кому лень его читать, но кто очень любит спорить про код, перфоманс и матчасть. Ну и просто интересные наблюдения.
Изначально я хотел написать про то: что такое бесплатные вычисления на примере is_range() + сумма елементов массива, но тут выявилась смешная особенность, поэтому пока без is_range().
Начнём с простого - сумма елементов(float) массива. Как написать её быстро? Обычный крестопоц сделает так:
auto summ = accumulate(begin(vec), end(vec), 0.)
Этот код выдаёт 5.6GB/s(мы всё бенчим в л1д 32килобайта массив). Казалось бы, если бы мы слушали всяких «гуру», которые нам говорят: accumulate() - оптимизирован, «ты что умнее создатели stl"а?», «конпелятор умнее тебе - сам всё делает оптимально», «руками что-то делать слишком сложно и не нужно» - то мы бы там и остались с этими 5.6ГБ, но мы пойдём дальше и поймём почему так, и является ли это тем, что намн ужно.
Но посмотрев на код - он не векторизован:
addq $4, %rdx
vcvtss2sd -4(%rdx), %xmm2, %xmm2
vaddsd %xmm2, %xmm1, %xmm1
Почему? Патамучто это основная флоатпроблема: Он не ассоциативен - флоат не имеет в себе точных представлений всех чисел входящих в диапазон его «представления» т.е. порядкопроблемы.
Поэтому конпелятор НЕ ВЕКТОРИЗУЕТ флоат по умолчанию, ну никак. Даже такую банальщину.
Для решения этих проблем - есть ключик -funsafe-math-optimizations, который входит в -ffast-math, который кладёт на точность при вычислениях. Добавив его мы получаем уже 44.9GB/s.
Но теперь мы получаем ещё одну проблему - надо думать: «как бэ сунуть эту ключик не повредив там, где этот ключик не нужен».
Поэтому ноцанам, которые хотят быстро и не хоятт рандомных жоп из-за тупости конпелятора - пишут всё руками. Допустим на той же сишке это пишется так:
double memadd_autovec(buf_t buf) { //5.609465GB/s, либо 44.969652GB/s с ffast-math
float * it = buf_begin(buf), * end = buf_end(buf), summ = 0.;
do {
summ += *it++;
} while(it != end);
return summ;
}
double hsumf(__v8sf v) {
return (v[0] + v[1] + v[2] + v[3] + v[4] + v[5] + v[6] + v[7]);
}
double memadd_vec(buf_t buf) { //45.652002GB/s и класть на ffast-math
__v8sf * it = buf_begin(buf), * end = buf_end(buf), summ = {};
do {
summ += *it++;
} while(it != end);
return hsumf(summ);
}
Т.е. разницы никакой нет, кроме нужной нам реализации горизантального сложение вектора. Когда я говорил пацану: «векторную сишку для написания быстрого кода юзать намного проще, чем плюсы» - поцан нипонимэ, да и любые пацаны скажут - ну дак с -ffast-math оба выдают по 45гигов - нахрен эта сишка нужна?
А вот зачем:
double memadd(buf_t buf) { //132.878440GB/s
__v8sf * it = buf_begin(buf), * end = buf_end(buf), summ = {};
do {
summ += *it++;summ += *it++;summ += *it++;summ += *it++;
} while(it != end);
return hsumf(summ);
}
Это называется пацанский анролл копипастой, а вот заставить конпелятор нормально что-то разанролить очень сложно.
Если бы мы слушали всяких «гуру», которые нам вещают: «анрол говно и не нужен» - мы бы так и седели с 45-ю гигами, а так мы сидим с 132.878440GB/s. Т.е. анролл нам дал немного не мало ~300%.
Но основная мысль, которую толкают всякие «гуру» - это не надо следить за тактами/считать такты и прочее. Но мы о5 сделаем наоборот и посмотрим что будет.
Т.к. наш юзкейс упирается на 99% в throughput и дёргается одна инструкция, то нам достаточно просто считать теоретическую производительность для моего камня. 4.5(частота камня)*8(т.е. у нас камень с avx, то там вектор 32байта, либо 8флоатов.)*1(throughput нашей инструкции - в данном случае vpaddps из интел мануала). Т.е. 36гигафлопс, либо ~144гига. Т.е. мы сняли овер 90% теоретической производительности - остальные 10% у нас ушли в наши циклы, всякие горизонтальные суммы вектора и прочее, ну и конечно же чтение данных из кеша.
Но самое смешное - на моём хасвеле умножение имеет throughput 0.5 - т.е. на хасвеле умножение быстрее сложения. Это новая забористая трава у интела.
Казалось бы - какой жопой сложнее оказалось медленнее умножения - а вот так, на всяких штеудах производительность уже давно зависит не от каких-то технических возможностей, а от маркетинга и хотелок.
Поэтому очень смешно слушать, когда какие-то пацаны говорят: «float point имеет такую же производительность как и инты» - нет, оно имеет такоу же производительность лишь по причине того, что на штеуде инты тормазят так же, как и float.
И чтобы окончательно в этом убедится - мы взглянем на fma(вариации умножения со сложением/вычитанем), которые имеют throughput 0.5 - да, да - на хасвеле умножение+сложение в 2раза быстрее просто сложения. Это уже не просто трава - это что-то принципиально новое.
У целочисленного сложения же throughput 0.5 и казалось бы, если мы поменяем в нашей функции float на int - у нас будет сложение работать в 2раза быстрее, но это не так. Оно выдаёт те же 130гигов, а почему?
Вообще у камня есть такая фича, допустим у нас:
add $1, %reg0//вот тут инструкция add залочит регистр reg0
add $1, %reg0//а эта инструкция уйдёт в лок до особождения предыдущей инструкцией регистра reg0
Чтобы такой жопы небыло - есть специальная фича:
add $1, %reg0//lock reg0
add $1, %reg0//И тут вместо того, чтобы уйти в лок - камень вместо reg0 даёт инструкции любой свободный регистр.
Эта фича называется прееименование регистров, либо как-то так - мне лень гуглить.
Дак вот штука в том, что фича работает через жопу. Мне лень читать мануал и искать почему так, но штука в том, что она ограничивает throughput. На умножении и целочисленном сложении она огранивает throughput c 0.5 до 1.
И вот я решил заюзать сложении через fma:
__v8sf fmaadd(__v8sf a, __v8sf b) {
return _mm256_fmadd_ps(_mm256_set1_ps(1.), a, b);// a + b * 1. == a + b.
}
double memadd_fma(buf_t buf) {
__v8sf * it = buf_begin(buf), * end = buf_end(buf), summ = {};
do {
summ = fmaadd(summ, *it++);
} while(it != end);
return hsumf(summ);
}
Но меня ждала жопа: 27.347290GB/s, причем не анролл и ничего не помогал. Я уж подумал, что мануал наврал, но позже до меня допёрло: у неё latency 5тактов и ((4.5×8)÷5)×4 ~= 29гигов - т.е. я получаю производительность с её latency, но какой жопой оно так?
Потом я вспомнил, что гцц гинерит анрольный код вида:
add $1, %reg0
add $1, %reg0
//а не
add $1, %reg0
add $1, %reg1
Т.е. на неё вообще не работает переименовывание регистров - и инструкции постоянно в локе. Я это проверил и оказался прав. Ну и я написал такой мемадд:
__v8sf fmaadd(__v8sf a, __v8sf b) {
return _mm256_fmadd_ps(_mm256_set1_ps(1.), a, b);
}
inline void fma_10way_finality(__v8sf * cache, __v8sf * it, __v8sf * end) {
switch(end - it) {
case 8:
*(cache + 7) = fmaadd(*(cache + 7), *(it + 7));
*(cache + 6) = fmaadd(*(cache + 6), *(it + 6));
case 6:
*(cache + 5) = fmaadd(*(cache + 5), *(it + 5));
*(cache + 4) = fmaadd(*(cache + 4), *(it + 4));
case 4:
*(cache + 3) = fmaadd(*(cache + 3), *(it + 3));
*(cache + 2) = fmaadd(*(cache + 2), *(it + 2));
case 2:
*(cache + 1) = fmaadd(*(cache + 1), *(it + 1));
*(cache + 0) = fmaadd(*(cache + 0), *(it + 0));
case 0:
break;
default: error_at_line(-1, 0, __FILE__, __LINE__, "bad_aligned");
}
}
double memaddfma_10way(buf_t buf) {
__v8sf * it = buf_begin(buf), * end = buf_end(buf), summ = (__v8sf){};
__v8sf * cache = (__v8sf[10]){{}};
uint64_t i = 0;
while((it += 10) <= end) {
*(cache + i) = fmaadd(*(cache + i), *(it - i - 1));++i;
*(cache + i) = fmaadd(*(cache + i), *(it - i - 1));++i;
*(cache + i) = fmaadd(*(cache + i), *(it - i - 1));++i;
*(cache + i) = fmaadd(*(cache + i), *(it - i - 1));++i;
*(cache + i) = fmaadd(*(cache + i), *(it - i - 1));++i;
*(cache + i) = fmaadd(*(cache + i), *(it - i - 1));++i;
*(cache + i) = fmaadd(*(cache + i), *(it - i - 1));++i;
*(cache + i) = fmaadd(*(cache + i), *(it - i - 1));++i;
*(cache + i) = fmaadd(*(cache + i), *(it - i - 1));++i;
*(cache + i) = fmaadd(*(cache + i), *(it - i - 1));++i;
i = 0;
}
fma_10way_finality(cache, (it - 10), end);
summ = (*(cache + 0) + *(cache + 1) + *(cache + 2) + *(cache + 3) +
*(cache + 4) + *(cache + 5) + *(cache + 6) + *(cache + 7) +
*(cache + 8) + *(cache + 9));
return hsumf(summ);
}
Пришлось хреначить финалити, ибо тут «анролл» на 10, а почему на 10 - для максимального throughput"а - надо, чтобы каждый каждый регистр юзался через 5тактов - т.е. 10регистров.
И вся эта порятнка нужна для борьбы с тупостью конпелятора.
Это уже: 214.167252GB/s(раельно там в районе 250 - просто мой бенч говно). 107 гигафлопс на ведро. Из теоретических 144, но тут уже влияние кеша. Причем 50+ из которых выкидываются и просто бесплатные.
Теперь вопрос к пацанам - что нам дадут эти гагфлопсы, когда у нас будет массив не 32килобайта, а 32мегабайта? Зачем нужно выживать максимум, когда скорость памяти отсилы 20-30гигабайт и нам хватит даже С++ кода с ffast-math?
Ну и призываются упомянутые мною пацаны: 
mv - этот тот експерт, что вещал про «руками переименовывать регистры не надо» и «анрол ваще ненужен», emulek вещал про ненужность счёта тактов, и не понимал что такое «беслпатно», AIv - не понимал в чем проблема плюсов, ck114 - так же не понимал в чем проблема плюсов.
Бенчи: https://gist.github.com/superhackkiller1997/606be26fa158ef75501d - вроде я там ничего не напутал.
P.S. - не выпиливайте пж, пусть пацаны «нужно» или «не нужно». Мне интеерсно. Ну и там рекомендации пацанов.
