История одной оптимизации

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

В этот раз я, забредя на страничку про модифицированный логарифмический тон-маппинг...

Что вы говорите? Что я там делал посреди дебага глянса? Нуу.. в последние дни знакомый только и делал что спамил мне в аську вопросами про рендеринг, про шойдеры в DX, итп. Движок он пишет. :) По-моему уже третий или четвёртый.. Занимался освещением, писал свет во флоатовый буфер, вот и дошло дело до тонемапенга. Я на практике дел с ним не имел, но что-то читал; посоветовал погуглить, а позже и сам последовал совету.

Так вот, забрёл я, значит на сайт, забрал пдфку, понатырил сочных фоток, ни с того ни с сего закинул одну в блокнот, увидел структуру, напомнившую Netpbm, загорелся идеей по-быстренькому состряпать декодер формата RGBE из семейства Radiance. Было это в первом часу ночи..

Дооо, как же, "по-быстрому"! Щяз. С чяс я провозился, парся хедер, голова уже почти не варила, а впереди была веселуха с RLE неведомой природы; в общем, пошёл я того.. этого; утро вечера оно как бы.. ну этаа.

Засыпая, грезил как пишу раскукоживатель RLE общего назначения.. Я не имел представления, какого оно рода в этом формате, просто надеялся, что не сильно отличается от такового в TGA. "Не сильно" - это в пределах шаблонной параметризации. :) "Чё-нибудь я придумаю, главное начать кодиххххрррррр...."

На следующий день бодренько настрочил задуманное в полудрёме и тут же применил, попытавшись декодировать оставшиеся после хедера пиксельные данные. Конечно же, вышла цветастая ахинея; я немного поигрался параметрами, но без заметного успеха. Решив завязать с кодингом впотьмах, отправился на поиски описания этого самого RLE в этом самом RGBE. Но без заметного успеха.

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

Затейливый форматик заслуживает пары слов о себе. Данные расфасованы построчно, вначале строки сидит Странный Пиксель, исходя из содержимого которого определяется метод декодирования оставшейся строки - либо RLE, либо какая-то НЁХ, в которой я ещё не разбирался по причине того, что не попадались файлы с ней. Сам же рле тут, как оказалось, вполне вписывается в написанный ранее шаблон, с одной оговоркой: каждый канал (красный, зелёный, синий, экспонента) в строке покоится отдельно и неразрывно; то есть пиксели фрагментированы - красный там, зелёный сям.. Мне, ясное дело, нужно, чтобы в целевом буфере они располагались вместе, в виде самодостаточных пикселей, поэтому запись раскукоженных данных в буфер идёт в 4 прохода с шагом в 4 байта.

Не имея, откровенно говоря, ни малейшего понятия о том, что из себя вообще представляет экспонента в RGBE-пикселе, я сперва пошёл по наивно-интуитивному методу: левый сдвиг E на 8 бит, битовое сложение с R, G, и B, деление на 65535... *сhirp сhirp* Вы сейчас, вероятно, потеряли всякую веру в меня, как в программера, поэтому спешу заверить, что я, получив блёкло-серый результат, тут же исправился: нашёл там же код конвертации во float и.. да, скопипастил. :3 И оно завертелось, зажужжало и взлетело, wheee.

const rgba8888 &in = ...;
float3 &out = ...;
...
out.Init( in.r, in.g, in.b );
out += 0.5f;
int exp = (int)in.a - (128+8);
out *= ldexp( 1.0f, exp );

ldexp(x,n), как выяснилось, возвращает x∙2ⁿ. Ну или бесконечность или нолик - как сложится. То есть, грубо говоря, тупо делает числу с плачающей точкой битовый сдвиг экспоненты. Я до сих пор не знаю, что это за 128+8 или зачем там 0.5f, но оно хотя бы даёт результат, очень схожий с фотошоповским (после гамма-коррекции 2.2 в последнем), хотя насыщенность цвета в ФШ ниже.. Oh well.

Время до появления жалкой картинки 760x1016 на экране было просто неприлично большим, субъективно больше секунды, причём от раза к разу время сильно колеблется. "С этим надо что-то делать", - говорю себе я и заменяю прямое чтение файла с диска на чтение из памяти. Субъективно ничего не меняется. :) Но я помню, что работа с флоатовыми текстурами у меня тут всегда была сопряжена с большой потерей времени: на загрузке в видеопамять, на генерации мипмапов, да и наверняка на самопальном ресэмплере для построения тамбнейла. Всё это означало неизбежность использования performance counter-а на тестируемом клочке кода.

Заменил буферный ридер обратно на файловый и замерил, выставив приоритет потока на time-critical. Примерно 530 мс. Это, конечно, лучше "субъективно больше секунды", но всё же не лезет ни в какие ворота, ибо другая картинка занимала мой дыкодырь чуть ли не на 4 секунды.. Снова поменяв ридер на буферный, я, конечно, надеялся на некоторый буст (я ведь избавляюсь от безумно медленного чтения с диска, хоть и буферизованного системой), но уж никак не ожидал, что время упадёт с 530 до 260 мс. о_о Это означает двухкратную потерю на вызовах CRT и файловых операциях; и никакие 4-киловые буферы не спасают, потому что файлы весят мегабайты.

Порадовавшись немного, я уставился на вызов ldexp. Мне не давало покоя, что она зовётся 772160 раз. =\ Счёт вызовов ридера шёл на миллионы, но меня это тогда заботило куда меньше. =) Из описания функции стало ясно, что делает она что-то очень простое. Ну, достаточно простое, чтобы не тратить время на вызов, inline - наше всё. Я не стал воспроизводить поведение функции в точности, т.к. не отыскал в PSDK её сорцов, а доустанавливать сдк было лень. Да что там, я вообще не стал воспроизводить эту функцию. Я снова пошёл наивно-интуитивной дорогой: взял беззнаковую 32-битную единичку, сдвинул на exp бит влево и конвертировал во флоат:

if ( exp > 0 )
  if ( exp < 32 )
    out *= float(1ul << exp);
  else
    out = inf;
else if ( exp < 0 )
  if ( exp > -32 )
    out /= float(1ul << -exp);  // не пугайтесь, внутри оператора сидит инверсия и умножение
  else
    out = zero;

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

Поигрался с типом выходных пиксельных данных. Поменял float3 на float4a (это у меня align-еный вектор со всякими SSE-плюшками), надеялся, получится чуточку быстрее.. Вы уже поняли, да?)) Конечно же, стало медленнее; и ирония в том, что даже float4 оказался быстрее своего sse-собрата. Ещё предстояло расследовать почему так, ну а пока я откатился к 3-компонентному варианту и устремил взор к вызовам ридера. И здесь я сделаю ещё одно небольшое отступление.

IReader. Интерфейс, который я состряпал для удобной и гибкой доставки данных из одного места в другое. Ну, например, от распаковщика архива до декодера картинки. Нечто, отдалённо напоминающее COM-овский IStream. Основной метод - Read, принцип работы с ним тот же, что с fread: принимает размер элемента и сколько их читать, возвращает кол-во успешно прочитанных.

У и-фейса две основных имплементации: для чтения из файла и из памяти. В порядке эксперимента написал также чтец файла из RAR-архива; было весело, но самостоятельно решить возникшую задачу "producer-consumer" не удалось, помогли, как всегда, интернеты. :D А теперь - назад к оптимизации!

Упомянутые миллионы вызовов функции Read - совершенно очевидный боттлнек. Миллионы виртуальных вызовов!!1 Вся гибкость и универсальность отправилась лесом на деревню к дедушке, когда я это осознал. Неважно, какой ценой, я теперь был просто обязан заставить эти вызовы заинлайниться. Первым делом в распоряжение была получена имплементация ридера вместо интерфейса. Следом шла борьба с компилятором, который ни в какую не хотел инлайнить код имплементации виртуального метода. Пришлось оставить два варианта: инлайновый и виртуальный, что привело к различному их именованию. =\

Как бы там ни было, своего я добился: 145 -> 65; но и не думал останавливаться.

Следующим шагом стала перегрузка инлайнового метода read для чтения объекта фиксированного размера: избавление от лишней арифметики, а самое главное - от memcpy. У меня все чтения в боттлнеке этого декодера - по одному байту. Вы вдумайтесь: звать CRT для копирования одного байта. Одного несчастного байта!!1 И да, миллионы раз.

Результатом стал свой шаблонизованный memcpy, с маджонгом и гейшами, для копирования фиксированного кол-ва байт. Сделал явные специализации для размеров 1, 2, 4 и 8, остальные размеры копирует рантайм, но это временно.

Всё это, смело надеялся я, даст ещё мс пятнадцать... Итог? 65 -> 40. :D Я уже хотел остановиться, но..

Вспомнил про трабли с SSE. Краткие исследования показали, что главная ошибка была при расширении одиночного флоата до вектора: я тупо вручную копипастил этот флоат 4 раза, при том, что существуют инструкции для заполнения xmm-регистра одним значением. Немного шаблонной магии, и ошибка была исправлена. Время потихоньку поползло в сторону float3-вариации. Заменил скалярные константы векторами, и время сравнялось с "референсным". ^_^

Ну, гулять - так гулять. Решил вывекторизововать дальше:

out *= float(1ul << exp);

...было скоропалительно заменено на...

__m128i ish = _mm_slli_epi32(ione,exp);  // битовый сдвиг векторной единицы
__m128  fsh = _mm_cvtepi32_ps( ish );    // конвертация во float
out *= (float4a &)fsh;

Инициализация пикселя тоже стала более другой:

__m128i iin = _mm_setr_epi32( in.r, in.g, in.b, 1 );  // компоненты вырастают с 8 до 32 бит, затем оказываются в xmm-регистре
__m128  fin = _mm_cvtepi32_ps( iin );  // опять-таки конвертация во флоат
out._xyzw = fin;

За всю эту ювелирщину я был награждён.. четырьмя срезанными миллисекундами, их стало 36. :D

Итого:

• 14.7-кратный прирост скорости
• 33-процентный прирост веса текстуры как побочный эффект
• Весь код гладок как лоб младенца - не осталось (ну, я надеюсь) ни единого вызова
• Выводы:
  • Вызовы функций в боттлнеках - зло (оставим в стороне __fastcall и т.п.)
  • Вызовы виртуальных функций в боттлнеках - зло
  • Вызовы системных функций работы с файловой системой в боттлнеках - ЗЛО
  • SSE надо уметь пользовать, и даже тогда высока вероятность, что выгода от него не будет поражать ваше воображение

В ближайший релиз этот декодер не попадёт, т.к. при малейшей некорректности файла в худшем случае он уронит программу, а в лучшем потечёт память. Да и полноценную поддержку флоатовых текстур я ещё не сделал; нужен тот самый тонмаппинг + ручная фильтрация текстуры шейдером, т.к. хардварная [у меня] тормозит как крызис на смартфоне.

Благодарю вас, если вы дочитали до сюда. :) А если не дочитали.. well, fuck you! Ха-ха, дошло, да? :D