Как считать разделимый фильтр быстрее, в 2 отдельных прохода или с чередованием?

gpu

https://github.com/nodeca/pica/commit/cef0c6360b7ae429b582f5803d80c1dc3f5bc50d

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

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

за что ты его так?

Насчет чтения по байтам и по словам понял, сенькс.

Таблица фильтров килобайт 50. Картинку режем тайлами 1024х1024, то есть 4 мегабайта.

Меньше обращений к памяти не получится. Просто в первом случае буфер из себя представляет прямоугольник размера [высота_входа * ширина_выхода], а во втором - циклический список из нескольких строк.

Но количество операций чтения и записи одно и то же. Хотя из-за циркулярного буфера, скажем 1/3 от всех чтений и 2/3 от всех записей станут намного более «концентрированными» в одной области.

С этого реально что-то осязаемое вымутить? Просто если там 5-10% профита, то нет смысла код уродовать.

https://github.com/nodeca/pica/blob/3.0/lib/mathlib/wasm/math.c#L36-L44 вот тут ради интереса заменял умножение на сложение, стало раза в два быстрее.

PS. SIMD пока нема, не завезли еще :(

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

Расскажи историю про SIMD итп

Как это было?

Я правильно понимаю, что в V8 дропнули векторизацию, ожидая, что она появится в вебассемблере, а в нём её еще не прикрутили, и в результате мы остались без векторизации везде?

Есть ли какие-нибудь знаковые пруфлинки? Тесты?

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

Создай отдельную тему. В этой меня интересуют особенности реализации конвольверов.

https://people.freebsd.org/~lstewart/articles/cpumemory.pdf

В разделе 6 есть пример про умножение матриц.

Можешь глянуть реализацию в libvips, они сильно хвалились своими бенчмарками, и используют многопоточность со всякими там SSE емнип

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

Теперь там сначала что-то типа мипмапинга (с непонятными операциями на краях), а потом доводка ланцошом. Надо перепроверять насколько это вообще корректно.

А что за процессор? 4 мб кэш и SIMD даже у 10-летнего Xeon есть.

Только не смейсо. Это webassembly, исполняемое в браузере. Соотвественно - ну чо там у пипла на десктопах и мобилках.

И да, т.к. я не совсем дебил, то я смотрел через webassemly explorer, какой код генерит фаерфокс под x86. Там вроде именно то что должно быть, с учетом временного отсутствия SIMD.

https://github.com/nodeca/pica/tree/3.0/lib/mathlib/wasm

По ссылке есть .wast, а тут (mbebenita.github.io) можно проверить.

Остается в силе вопрос, возможен ли теоретически заметный профит, если вместо кучи записей в 1 мегабайт памяти циклически перезаписывать 10 килобайт (кольцевой буфер из строк), но тем же объемом данных.

Анонимус, спасибо! Ссылка очень годная.

Буду думать, реально ли перегруппировать запись в последовательную, для моего случая.

https://github.com/nodeca/pica/tree/3.0/lib/mathlib/wasm

for (; filterSize > 0; filterSize--) {
        filterVal = filters[filterPtr++];
        rgba = src[srcPtr++];

        r += filterVal * R(rgba);
        g += filterVal * G(rgba);
        b += filterVal * B(rgba);
        a += filterVal * A(rgba);
};

Думаю что этот момент можно попробовать ускорить и без SSE, например разместить сразу два канала (R и B) в одной 64-битной переменной (двоичным сдвигом, например чтобы было 0x000000RR000000GG), и потом умножать на этот самый filterVal, после чего доставать результат умножения битовой маской и сдвигом

Спасибо. А я что-то затупил, пытался сразу 4 байта всунуть и битов не хватило. Ща заценим.

Да, можно ведь как-нибудь так

uint64_t rgbargba;
...
memcpy (&rgbargba, &src[srcPtr], sizeof(rgbargba);
srcPtr += 2;
uint64_t rr = (rgbargba & 0xff000000ff000000) >> 24ULL;
uint64_t gg = (rgbargba & 0x00ff000000ff0000) >> 16ULL;
uint64_t bb = (rgbargba & 0x0000ff000000ff00) >> 8ULL;
uint64_t aa = (rgbargba & 0x000000ff000000ff) >> 0ULL;

И кстати, под filterVal точно нужна знаковая переменная?

uint64_t rr = (rgbargba >> 24LLU) & 0x000000ff000000ff;
uint64_t gg = (rgbargba >> 16LLU) & 0x000000ff000000ff;
uint64_t bb = (rgbargba >> 8LLU ) & 0x000000ff000000ff;
uint64_t aa = (rgbargba >> 0LLU ) & 0x000000ff000000ff;

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

Остается в силе вопрос, возможен ли теоретически заметный профит, если вместо кучи записей в 1 мегабайт памяти циклически перезаписывать 10 килобайт (кольцевой буфер из строк), но тем же объемом данных.

Perf'ом посмотри, как дела сейчас обстоят.

$ sudo perf stat -ddd -p `pidof firefox` & sleep 5; sudo killall -s SIGINT perf
[1] 7669

 Performance counter stats for process id '2149':

        299.535554      task-clock (msec)         #    0.061 CPUs utilized          
             1,439      context-switches          #    0.005 M/sec                  
                88      cpu-migrations            #    0.294 K/sec                  
               638      page-faults               #    0.002 M/sec                  
       245,626,710      cycles                    #    0.820 GHz                      (33.70%)
       185,128,848      instructions              #    0.75  insn per cycle           (41.80%)
        42,268,167      branches                  #  141.112 M/sec                    (42.01%)
         1,330,216      branch-misses             #    3.15% of all branches          (41.09%)
        48,119,843      L1-dcache-loads           #  160.648 M/sec                    (41.81%)
         4,883,033      L1-dcache-load-misses     #   10.15% of all L1-dcache hits    (36.47%)
         2,242,918      LLC-loads                 #    7.488 M/sec                    (24.92%)
           901,512      LLC-load-misses           #   80.39% of all LL-cache hits     (25.64%)
   <not supported>      L1-icache-loads                                             
         3,556,955      L1-icache-load-misses                                         (27.13%)
        49,286,285      dTLB-loads                #  164.542 M/sec                    (29.34%)
           399,965      dTLB-load-misses          #    0.81% of all dTLB cache hits   (31.79%)
           248,235      iTLB-loads                #    0.829 M/sec                    (33.09%)
           233,637      iTLB-load-misses          #   94.12% of all iTLB cache hits   (29.97%)
   <not supported>      L1-dcache-prefetches                                        
   <not supported>      L1-dcache-prefetch-misses                                   

       4.892337343 seconds time elapsed

filterVal - абсолютно точно 16 бит со знаком. Это значение точки на фильтре ланцоша. Тут ошибки нет, битов меньше тоже нельзя.

https://github.com/nodeca/pica/commit/bc359b0391fb03dd2bbfa0ec0aa91e35d0bb367...

Хьюстон, у нас проблемы. 64-битное умножение превращает код в тыкву. ХЗ почему emsdk хочет внешнюю функцию. Возможно wasm только 32*32 -> 64 умеет.

Чтобы посмотреть, нужно две реализации, а у меня только одна :(. И как раз хочется понять, стоит ли убивать время на вторую.

Но за инфу в любом случае спасибо. Потом пригодится.

Ну так ты и посмотри на те же LLC/dTLB loads/misses.

https://habrahabr.ru/post/308874/ пишут вроде, что надо через LLVM делать, чтобы там было i64.mul

Теперь попробуем более сложный способ, C/C++ Source ⇒ WebAssembly LLVM backend ⇒ s2wasm ⇒ WebAssembly.

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

блеат... как же всё не просто...

А по LLVM есть мануал для тупых или скрипт как всё для WASM чохом поставить?

Я ставил emsdk по инструкции http://webassembly.org/getting-started/developers-guide/, там пару строчек набрать и подождать часик.

Я тут протестировал https://mbebenita.github.io/WasmExplorer/ -> https://goo.gl/hx2ebG и вроде как i64.mul нормально генерируется

Там есть даже фича скачать бинарник, проблема была в том, что тот бинарник не работал когда проверял :).

https://gist.github.com/yurydelendik/37566c46197f6208dc457c680810f595

Нашел мануал от правильного перца из мозиллы. Попробую по нему сделать.

https://gist.github.com/yurydelendik/4eeff8248aeb14ce763e вот правильная ссылка.

Кровавые подробности насчет wasm-эксплорера - в коде, который он генерит, экспортируемые функции без подчеркивания. Это я поправил. Но тогда код падает внутри конвольвера, memory index out of bounds. ХЗ почему.

Сейчас собираю шланг по инструкции, напишу что как.

https://github.com/nodeca/pica/commit/bc34d66343ee8136c2b2a47220a3b9afe703dc6...

Разобрался почему падала сборка из под llvm. Оно по дефолту описывает объект Memory как экспортируемый. А emsdk описывает его как импортируемый (из яваскрипта). В итоге не просовывался объект памяти нужного размера и с данными, и все накрывалось нефритовым стержнем.

Надо при вызове s2wasm указать ключик --emscripten-glue, и оно всё починит. Код после llvm на несколько процентов быстрее.

Теперь насчет колхоза с умножением. Не помогло. Стало хуже, процентов на 15-20.

Как считать разделимый фильтр быстрее, в 2 отдельных прохода или с чередованием? (комментарий) а если как тут?

Кроме того, со сложением тоже можно что-то придумать с таким вот псевдо-SIMD

Хотя да, там я что-то затупил, ведь задача какая, на каждое RGBA умножать R G B A на одно значение, следующие 4 штуки RGBA же надо умнодать уже на что-то другое. Собственно, что тут можно придумать? Вот это 0xRRGGBBAA - 32 bit. Надо б сделать скажем такую штуку 0x000000RR000000АА - и потом умножить на filterVal. Ну т.е. фактически берем 0xRRGGBBAA расширяем до 64 бит 0x00000000RRGGBBAA и потом делаем маску 0x00000000FF000000 и сдвигаем влево на 8 бит -> 0x000000RR00000000. Ну и потом туда добавляем по маске 0xFF кусочек от альфа канала. Вот так и получится 0x000000RR000000АА который можно умножить на filterVal. Тут вот еще что - умножение 16-битного на 8-битное занимать будет максимум 24 бита, и тогда можно еще simd-ом пытаться что-то поскладывать, ведь там еще есть целых 8 бит про запас, но ситуацию портит то, что используется signed и в результате может быть отрицательное значение, что все испортит. В общем можно еще повозиться и что-нибудь попробовать придумать, например для отрицательных и положительных filterVal писать отдельное суммирование, но мне кажется что оно только затормозится сильнее от такого

Хотя стоп. Раз для каждой RGBA пары происходит...

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

В общем вот где-то такой код

      for (; filterSize > 0; filterSize--) {
        filterVal = filters[filterPtr++];
        rgba = src[srcPtr++];
        uint64_t rgba64 = rgba;
        int64_t ___r___a = ( (rgba64      ) | (rgba64 << 8 ) ) & 0x000000ff000000ff;
        int64_t ___g___b = ( (rgba64 >> 8 ) | (rgba64 << 16) ) & 0x000000ff000000ff;
        uint64_t m_rrr_aaa = ___r___a * filterVal;
        uint64_t m_ggg_bbb = ___g___b * filterVal;
        r += (int32)(m_rrr_aaa >> 32);
        a += (int32)m_rrr_aaa;
        g += (int32)(m_ggg_bbb >> 32);
        b += (int32)m_ggg_bbb;
};

А еще можно попробовать добавить __restrict спецификатор. См. https://ru.wikipedia.org/wiki/Restrict

Ну в общем оно того не стоит.

Я тут попробовал подурить процессер на более простой задаче https://github.com/nodeca/pica/blob/2.0.8/lib/js/unsharp.js#L15-L28

Развернул цикл 4 раза, перетащив запись в конец, 4 раза подряд. Думал, ща запись в кеш объединится и все взлетит. Даже если в один банк не попадем, будет профит в 2 раза а не в 4.

А заметной разницы нет. То ли процессор и так умный, то ли сам правильно разворачивает. Надо бы конечно на wasm написать для чистоты эксперимента, но что-то мне подсказывает, что принципиальной разницы не будет.