О современных процессорах и несовременных алгоритмах

В продолжение разговора, который кратко звучал на highload (в вопросах и ответах) и чуть подробнее - когда я с той же презентацией был в Mail.ru.

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

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

Плохо тут сразу два места: деления (все еще медленные) и зависимость между инструкциями (которая мешает локально векторизовать, впрочем векторизацию в общем случае тут вообще трудно применить т.к. каналы в данных перемежаются "произвольно". Ну то есть не вполне произвольно, но паттернов возможных много). Ну и в лоб не параллелится (на крупном уровне), впрочем для дисперсии объединения есть простая формула и это несущественно.

Посмотрел я на это дело - и спрограммировал в два прохода. Прямо вот по классике, одним проходом считаем среднее, вторым проходом - сумму квадратов отклонений. По компенсированной (в смысле точности) формуле, хотя на практике разницы не вижу.

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

Я собственно к тому клоню, что два прохода по памяти - могут оказаться лучше одного прохода, но с плохим (для расчетов, векторизации) телом цикла. Или, как минимум, не хуже.

Update: в первой версии этого поста было написано, что скорость работы 1- и 2-проходного варианта - одинакова. Это действительно было так пока я не заметил слона - порядок обхода памяти был неудачный. Замена на удачный - ускорила однопроходный вариант (с делением и зависимостью команд) в ~1.3 раза, а двухпроходный - втрое.