История повторяется
Поставило тут начальство задачу: научить наш движок распознавания автомобильных номеров эффективно использовать многоядерные процессоры.
Ну, казалось бы, в номере 6-8 символов. Грубо 50% времени уходит на их нахождение, остальные 50% - на распознавание. Запустим распознавание символов параллельно, получим довольно дёшево 20-40% прироста производительности.
Щаззз. 5-10% выигрыша есть, но профилировщик показывает, что общее использование процессора (в процессор⋅секундах) увеличилось. Разбиваем по функциям - тормозит нахождение скелета символа. Ну то есть как тормозит: за один запуск на тестовом наборе в 600 картинок параллельная версия проводит там на две секунды больше, чем последовательная.
Разбиваем её подробнее, до уровня вызовов функций библиотеки IPP. Собираем статистику ещё раз. В топе - вызов ippFilter.
Алгоритм скелетизации построен на анализе окрестностей 3×3 каждого пиксела. Если окрестность имеет определённый вид, то точка является краевой и её можно погасить. Когда на очередном шаге гасить нечего, то, что осталось - это и есть скелет.
Ну и, для скорости, мне нужна матрица, такая, чтобы в каждом элементе была закодирована вся окрестность соответствующего пиксела:
N[x,y] = 8 A[x-1,y+1] + 4 A[x,y+1] + 2 A[x+1,y+1] + 16 A[x-1,y] + A[x+1,y] + 32 A[x-1,y-1] + 64 A[x,y-1] +128 A[x+1,y-1]
Вот чего проще, вроде бы: бери свёртку A с ядром
842 1601 3264128
и это будет то, что надо.
Оно, конечно, то, что надо. Но вот выходит, что быстрее сделать вот так:
N[0:w-2, 0:h-1] = A[1:w-1, 0:h-1] A <<= 1 N[0:w-2, 0:h-2] |= A[1:w-1, 1:h-1] A <<= 1 N[0:w-1, 0:h-2] |= A[0:w-1, 1:h-1] A <<= 1 N[1:w-1, 0:h-2] |= A[0:w-2, 1:h-1] A <<= 1 N[1:w-1, 0:h-1] |= A[0:w-2, 0:h-1] A <<= 1 N[1:w-1, 1:h-1] |= A[0:w-2, 0:h-2] A <<= 1 N[0:w-1, 1:h-1] |= A[0:w-1, 0:h-2] A <<= 1 N[0:w-2, 1:h-1] |= A[1:w-1, 0:h-2] A >>= 7
И в параллельной версии, что характерно, время тоже перестаёт теряться.
Так что это мне напомнило? А вот была во времена 386’х такая техника: вместо y*320 брать y<<8 + y<<6. Сдвиги и сложение работали быстрее, чем операция умножения произвольных целых чисел (внутри процессора реализованная через те же сдвиги и сложения). Так и сейчас - быстрее сделать 8 сдвигов (уже целой матрицы поэлементно) и 8 побитовых or’ов (двух матриц поэлементно), чем свернуть матрицу с заданным ядром (которое, в общем случае, может быть произвольного размера и с произвольными весами).