Деление по модулю#опытным В прошлом посте в реализации скользящего среднего через ринг буффер используется формула
index = (index + 1) % maxSize. Делим по модулю на максимальный размер, чтобы текущий индекс не превысил его.
Но знаете ли вы, что
деление по модулю - это очень медленная операция?Сложение, вычитание и основные битовые операции выполняются условно за 1 такт. Сигнал просто проходит через сумматор и все. Умножение - за 3-4 за счет аппаратного умножителя (Wallace tree, carry-save adder).
А вот инструкция div выполняется за 10-50 тактов. На порядок больше. Почему так?Деление просто
не имеет быстрой аппаратной схемы. Чтобы получить
x / y, процессор выполняет
циклический алгоритм - обычно это модификации SRT division (назван по фамилиям Sweeney, Robertson, Tocher):
1. Сравнить старшие биты делимого и делителя.
2. Вычесть (или не вычесть) делитель.
3. Сдвинуть частичный остаток.
4. Повторить для следующего бита частного.
Условно, процессор делит в столбик.
Блок деления устроен итеративно: вместо одной комбинационной схемы процессор за несколько шагов вычисляет очередные биты частного.
Теоретически можно построить полностью комбинационную схему для деления, которая выдавала бы результат сильно быстрее. Но такая схема для 64-битных чисел потребовала бы много транзисторов/много памяти и огромную площадь на кристалле.
Поскольку деление в реальных программах встречается относительно редко (по разным оценкам порядка 1% от всех инструкций), инженеры хардвара идут на компромисс: они делают блок деления компактным и последовательным, жертвуя скоростью ради экономии места на чипе для более важных блоков (например, кэш-памяти или блоков векторных инструкций AVX-512).
Вывод тут один: если вы паритесь за нано и микросекунды, то избегайте деления.
Но как?Есть несколько методик, которые применимы в общем и в данном конкретном случае:
1️⃣
Можно сделать параметр size шаблонным. Тогда компилятор сможет применить оптимизацию "умножения на магическое число" (метод Гранлунда-Монтгомери). Главная идея - если делитель является константой на этапе выполнения или компиляции цикла, деление n / d можно заменить математически эквивалентным выражением вида
(n * m) >> s, где m и s - предвычисленные константы. m - некое обратное число в модульной арифметике, а s - зависит от разрядности чисел при делении и их величины.
2️⃣ Если уж прям нельзя сделать шаблонным параметр, то тоже не страшно. maxSize же не меняется. Поэтому н
ам просто нужно самим сделать то, что делает компилятор. Условно, в конструкторе предрасчитать магические числа и потом использовать быстрое умножение. Для этого естественно есть библиотечки, типа
libdivide. Вот небольшой отрывок кода, как ей пользоваться:
int sum_of_quotients(const int *numers, int count, int d) {
int result = 0;
libdivide::divider<int> fast_d(d); //constructs an instance of libdivide::divider
for (int i=0; i < count; i++)
result += numers[i] / fast_d; //uses faster libdivide division
return result;
}
3️⃣
Можно ограничить пространство значений размера ринг буфера до степени двойки. Тогда деление по модулю можно заменить на супербыстрое битовое умножение:
index = (index + 1) & (maxSize - 1)
По сути просто оставляем только младшие разряды числа и предотвращаем переполнение.
4️⃣
Можно просто использовать условие:index++;
if (index >= maxSize) {
index = 0;
}
Предсказатель переходов здесь должен хорошо отрабатывать и латенси должно ощутимо снизиться.
Не во всех случаях подходит, но в этом работает прекрасно.
То есть проблему можно решить и можно(и нужно) даже побэнчмарчить, что быстрее по итогу.
Don't let the pipeline stall. Stay cool.
#performance #compiler #hardware