О legacy и форматах данных

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

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

Имею сказать, что распространенный в настоящее время формат "16-битное целое на компонент" - это максимально неудачный способ с точки зрения эффективности обработки:

  • от малейшего чиха переполняется или превращается в тыкву обнуляется, нужно постоянно следить за диапазоном;
  • векторные (SSE,AVX) операции с этим типом - очень ограничены, да и не векторные - тоже.
В результате, сплошные мучения компилятору, а результат - медленно работает. Скажем, вот такой вот код (из dcraw), который делает преобразование по матричному профилю для 3-4 входных каналов (цветов) и трех выходных:
out[0] = out[1] = out[2] = 0;
for (сc=0;сc<colors;сc++) {
  out[0] += out_cam[0][сc] * img[сc];
  out[1] += out_cam[1][сc] * img[сc];
  out[2] += out_cam[2][сc] * img[сc];
}
for(cс=0;сc<3;сc++) img[сc] = CLIP((int) out[cс]);
img[] - unsigned short, out[] - int, out_cam[] - float.

Смотрю на код, который порождает интеловский компилятор. Ну код, да. (три-)четыре load по 2 байта (количество loads зависит от colors /количества цветов/), дальше "вручную" выписанный dot product (нормальный, насколько это возможно), ну и обрезание до диапазона 0-65к и store.

Скорость работы этого кода - 100 мегапикселей в секунду на Sandy Bridge 4.5Ghz (в один поток, понятно что параллелится это на ура). Как-то не очень....

Да, считаем в мегапикселях т.к. в unsigned short у нас 8 байт на (4-компонентный) пиксель, а для float/int - 16 байт.

Меняем все на float, разворачиваем внутренний цикл, считая что входных цветов всегда четыре (если их три, то допустим мы 4-й компонент обнулим заранее): 277 Mpix/sec.

Предполагаем, что у нас SSE4.1+, пишем руками три _mm_dp_ps(), два shuffle, два blendps (кстати, даже с shuffle/blend кода, получается меньше, чем на C++ с развернутым циклом, так как одним махом четверых умножахом): 423 Mpix/sec.

УдвояемРазворачиваем цикл вдвое, чтобы за один раз обрабатывать два пиксела, прячем второй load посреди первых умножений: 584 Mpix/sec. Если убрать обрезание по границам диапазона (которое в short-версии ело чуть не треть времени, а в float-версии один maxps и один minps на цикл), то 606 Mpix/sec.

Дальше особо не ускорить, просто цикл load/store работает (на одном core) со скоростью 750Mpix/sec (12Gb/sec) и разворачивать цикл дальше большого смысла нет, только утомишься и регистры кончатся.

Для 32-bit integer скорость будет примерно такая же, на каждый пиксел добавится конверсия в float и обратно.

На практике, еще получится распараллелить по ядрам и ограничение настанет в области насыщения памяти.

Я, собственно, клоню к тому, что во втором десятилетии 21-го века, когда гигабайт RAM стоит примерно $6, вся эта экономия на памяти и на математическом сопроцессоре - устарела до черезвычайности. Хранение - другое дело, диски медленные и поэкономить на чтении можно изрядно. А на обработке - наоборот.

Update: да, 606Mpix/sec по 16 байт на пиксель - это примерно 10Gb/sec на одном ядре. Как следствие, гнать этот кусочек кода на видеокарту (которая обработает его офигенно быстро) нет смысла: по PCIe будет порядка 5Gb/sec туда, столько же (в лучшем случае) обратно т.е. на одном core банально раза в 4 быстрее.

Comments

1. Есть устоявшееся мнение, дескать обработка (изображений) в целых (16-битных) числах - это быстро, а делать то же самое в плавучке - медленно.

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

Я лет 6 назад сделал (2) и сразу перестал (1). Я еще со времен Ваткома с подозрением отношусь к возможностям себя переплюнуть компилятор и уже неоднократно утверждался в.

Несмотря на мое уважение к современным кодогенераторам, совершенства нет.

Из личного опыта:
* dot product не распознают, соответственно инструкцию такую не ставит.
* я не понимаю, что такое я должен написать на С, чтобы транспонировать матрицу 4x4 столь же эффективно, как _MM_TRANSPOSE4_PS (а это оказалось ключевым местом в деле "наложения поканальной кривой")

Из чужого опыта: умножают матрицы таки kernel-ом на ассемблере (SSE и т.п.), а не доверяют кодогенератору. Потому что добиться ровно блока 8x2 (к примеру) прагмами разворотов цикла сильно сложнее, чем руками это место закодировать.

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

Я думаю (опираясь на свои старые опыты с цветокоррекцией на HLSL/GLSL) что настоящий ништяк наступит когда можно будет гнать на видимокарту слегка может быть причесанный RAW, а обратно получать уже RGB и максимум разве что профиль прикладывать. А так эти ваши туда-сюда совершенно не прикалывают.

Да, конечно.

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

Но хочется нести туда только хот-споты. Которых ну примерно 10 кусочков кода по 10 строчек (вроде вышепоказанного), ну может чуть больше, работы по переносу немного. Но приходится обломится. Зато на мобильных GPU, которые используют хостовую RAM за отсутствием своей, можно обойтись без копирования.

Ну и конечно всякие AMD Fusion и прочие Ivy Bridge, где память тоже общая - тоже сильно упрощают жизнь.

А на мобильных реально без копирования, то есть там просто ремаппинг из хоста в GPU? Получается тогда что обычный PCIex16 должен отсасывать у хорошего ноутбука просто не нагибаясь?

Я делал эксперимент один раз, на макбуке с GF 8600M и у меня вроде так и получилось (ну то есть скорость записи в mapped-память GPU была равна скорости записи просто в память).

Хотя вот про OpenCL AMD пишет странное CPU-to-GPU data transfers exceed 15GB/s using APU zero copy path

Казалось бы, если zero copy, то какие в жопу 15Gb/s, оно должно "со скоростью мысли"

Насколько я понимаю, это и есть скорость мысли, т.е. пропускная способность подсистемы памяти. Скорость записи из процессора в ОЗУ.

Ну значит у них текст написан/озаглавлен неправильно, им бы акцентировать на то, что заполненный буфер на вычислителе оказывается "сразу".

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

Да, согласен, кривовато.

на мобильных реально без копирования, то есть там просто ремаппинг из хоста в GPU?

Смотря на каких, бывает что да

если применять основную мысль (legacy data types) к обработке изображений, то она верная, т.к. в основном это stream processing и задача легко влезает в память.

вообще говоря, конечно же нет. скажем, используя char и short вместо int и long можно добиться более высокой плотности хранения данных, соответственно больше данных можно впихнуть в кэш для тех алгоритмов, где есть смысл кэшировать.

ну и конечно есть море задач, где лучший тип данных это вообще vector(bool) или bitset, куда запакован массив int, обрезанный по макс. битовой ширине. опять же, из соображений кэша или нехватки памяти.

Да, естественно, если мы боремся за влезает/не влезает в кэш (или "влезает в L1/влезает в L2"), то жизнь другая совершенно. Или если мы боремся за bandwidth памяти/диска, что тоже часто встречается.

А вот конкретно с (единичными) картинками - не так. В кэш в любом случае не влезет (а что влезет - то обрабатывается с "достаточной скоростью"), а ситуация, когда ограничены bandwidth диска - неинтересная на практике т.к. в память то влезет.

Про кино - не знаю, мало опыта.

Я что-то туплю ... А зачем что-то ВЫЧИСЛЯТЬ в 16 битах? 16 бит - это только формат хранения для больших объемов. Вычислять на современных процессорах менее чем в 32 битах просто смысла нет.

В случае dcraw куча 16-битных вычислений тянутся понятно откуда: в 97 году память была узким местом для обработки фото.

И что ты там меняешь на float? Насколько я понимаю, img дан нам в unsigned short свыше :)

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

Ну вот, к примеру, фотошоп. Сделали "действие". На старте было 16 бит, на выходе - 16 бит. Промежуточная математика - допустим в 32, но проблема то не в ней.

Ну так очевидно, что формат промежуточных результатов определяется постановкой: если их мегамного и для нас стоит вопрос об эффективности использования процессорного кеша, а то и дискового :), то приоритет будет у минимизации памяти и пусть считает в 4 раза медленее. А если наоборот - то 32 бита.

Т.е. дело тут совсем не в float, а в битах для хранения.

Процессорный кэш, пусть даже L3 и пусть на 8Mb - это мегапиксель. А с мегапикселем оно и так не тормозит (см. выше про 100 мегапикселей в секунду в плохом случае).

Вот это надо гениям из RPP показать. А то у них плавучка это оправдание тормознутости софта.

Я не знаю про RPP, а обычно проблема в том, что подобных хот-спотов не один, а пара десятков, причем треть из них - в чужих компонентах (например, в color management engine), еще треть - в подготовке/приеме данных для/от этих чужих компонент и только треть - своя.

И получается, что не сделав свою *быструю* CMS - ничего и не получится. А это - тот еще геморой.

Ещё бы сравнить это по производительности с встроенными в GCC переносимыми (не завязанными на конкретную процессорную архитектуру) векторными типами (http://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html). Умеет порождать как SSE, так и legacy FPU код с циклами. Вероятно, будет несколько медленнее ручного SSE, зато элегантно.

Я по ссылке вижу только целые вектора.

Где поподробнее почитать.

Вещественные описываются точно так же. На той же странице: "The vector_size attribute is only applicable to integral and float scalars". Только, как и в случае с ручным кодингом на intrinsics (по сути, на ассемблере), надо помнить о выравнивании на размер всего вектора при ручном выделении памяти. Запаковывать/распаковывать вектора можно как обычно, через union, например. Документация, к сожалению, крайне скудная, но примеры нагуглить можно, типа такого http://stackoverflow.com/questions/4596912/sse-simd-extensions-support-i...

Ага.
Накодировал dot product. Код получается нихрена не компактным для SSE (4.2), встроенный dot product оно, понятное дело, не распознало. Для AVX с виду поприличнее, но тоже 35 инструкций в теле цикла, а руками (с dot product в виде инструкции) - всего 9.

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

Ага, разобрался.

Прикольная штука (т.к. умеет legacy FPU), жаль что совместимость с другими компиляторами отсутствует.

Сравнил. Пока на core2, у меня на AVX нету свежего gcc сейчас.

gcc: получается медленнее, чем развернутое руками умножение просто на C.

clang (llvm 3-devel): "умножение руками" и векторное - одинаково. Но "умножение руками" имеет сильно более очевидный код.

И все это сильно медленнее, чем я ожидал. Похоже, что Sandy Bridge в сравнении с Core2 - офигенный просто шаг вперед, не только по частоте.

Завтра подробнее напишу.

Я, собственно, клоню к тому, что во втором десятилетии 21-го века, когда гигабайт RAM стоит примерно $6, вся эта экономия на памяти и на математическом сопроцессоре - устарела до черезвычайности.

надо начать с того, что оптимизация для десктопных процессоров в большинстве случаев не нужна ;)
(а для недесктопных код из dcraw может иметь смысл)

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil

Если хочется иметь instant updates в программе вроде Lightroom (RPP, whatever), т.е. по движению контрола сразу виден результат, то оптимизация нужна.

Понятно, что первейшая оптимизация - это уменьшение количества обрабатываемых данных до размера экрана (2-4 мегапикселя), но это - тоже оптимизация. Ну и для этого количества данных весь пайплайн обработки надо бы за 50-100 (а лучше - 30) миллисекунд прогнать.

простите мой френч но читать из памяти по 2 байта в 2011 это диагноз. Зачитать в вектор из 8ми шортов и сделать пару shuffle и все полетит как птица. Ваши 10G моментально начнут упираться в bandwidth как только вы запустите на всех ядрах что-то такое же.

Ну а зачем вы это мне объясняете?
Объясните компилятору.

Потому что если я уж дойду до ручного написания _mm_loadu_si128, то я и сделаю все в плавучке и на dpps, это всяко быстрее.

ну так я и объясняю что потому и 16бит что нельзя весь bandwidth выжирать в одно горло. А будете вы там конвертить прочитанные шорты во флоаты или нет это практически не повлияет на поведение системы под нагрузкой на все cpu. Кстати будете смеяться, но на gpu специально есть float16.

А компиляторы и вся эта "модель черного ящика" в стиле plug'n'pray мне уже в печени сидят.

Я не понимаю, против чего вы согласны, разжуйте поподробнее.

Собственно, в тексте поста есть сниппет кода, если вы дадите свой вариант, мне несложно его побенчмаркать вместе с прочими.

Вот полная версия, для удобства:

float mat[3][4] = {{ 0.17f,0.22f,0.33f,0.44f},{0.55f,0.66f,0.77f,0.88f},{1.01f,1.02f,1.03f,1.04f}} ;

void sdotp(unsigned short *image,int sz)
{
int cc;
unsigned short *img = image;
float out[3];
for(int i = 0; i < sz; i++,img+=4)
{
out[0] = out[1] = out[2] = 0;
for(cc=0;cc<4;cc++) {
out[0] += mat[0][cc] * img[cc];
out[1] += mat[1][cc] * img[cc];
out[2] += mat[2][cc] * img[cc];
}
for(cc=0;cc<3;cc++)
img[cc] = out[cc];
img[3] = 0;
}
}

мда зарапортовался )
мои жалобы были против "экономии на памяти" и гигабайтов в памяти в виде float[] картинок. sorry.

поскольку сейчас на работе простой :) попробовал ваш сниппет и на 2008й если тупо заменить матрицу и out на int и вставить clamp(0, ushort_max, out[cc]) то оно в пару раз быстрее. Разумеется надо мерять оптимизированный против оптимизированного :) так как и там и там оно не векторизировало ничего. Мое впечатление что если возня с переводом матрицы в целые себя оправдает то на пре-avx машинках целочисленка выиграет с малым отрывом.

с выводом что вычисления сейчас очень дешевы по сравнению с хранением я не спорю просто это никак не связано с ценой гигабайта RAM. Как в шутку сказал в одной из недавних презенташек Meyer "RAM is new disk".

Не-не. Матрицу не надо "тупо менять на int", вы тут запросто пару бит в младших разрядах потеряете об округления.

Собственно, если взять и "тупо поменять на int" матрицу из примера, то получится матрица:
{0,0,0,0},{1,1,1,1,1},{1,1,1,1}
Поверьте - результат расчетов с такой матрицей будет совсем иной :)

не ну зачем жеж так пошло. мы результат сохраняем по сути как 16 бит fixed point значит и преобразование в 32 битных fixed point вполне может нас устроить. Если же матрица в плавучке это данность свыше, то о какой экономии сопроцессора речь? :)

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

Ну и может быть обратная сторона: в матрице уже очень большие значения, но с разным знаком. И результат умножения в float влезает (а после сложения - остается в 16-битном диапазоне), а в int - не хватает пары десятков порядков. В этом случае, наоборот, надо бы поделить на константу....

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