Как я могу уменьшить силу деления на 2^n + 1?

Question

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

На этом пути я делю на 2^n+1, где n является переменной. По сути, я хочу оптимизировать эту функцию, чтобы удалить оператор деления:

unsigned long compute(unsigned long a, unsigned int n)
{
    return a / ((1 << n) + 1);
}

Если бы я делил на 2^n, я бы просто заменил div на shift-вправо на n. Если бы я делил на константу, я бы позволил силе компилятора уменьшить это конкретное деление, вероятно превратив его в умножение и некоторые сдвиги.

Есть ли подобная оптимизация, которая применима к 2^n+1?

Изменить: здесь может быть произвольным 64-разрядным целым числом. n принимает только несколько значений от 10 до, скажем, 25. Я, конечно, могу предварительно вычислить некоторые значения для каждого n, но не для a.

Answer 1

Так как вы можете только сдвинуть int так много мест, вы можете поместить все эти случаи в выбор одного из нескольких делений по константе:

unsigned long compute(unsigned long a, unsigned int n)
{
    // assuming a 32-bit architecture (making this work for 64-bits 
    // is left as an exercise for the reader):
    switch (n) {
        case  0: return a / ((1 << 0) + 1);
        case  1: return a / ((1 << 1) + 1);
        case  2: return a / ((1 << 2) + 1);

            // cases 3 through 30...

        case 31: return a / ((1 << 31) + 1);
    }
}

Так что теперь каждое деление является константой, которую компиляторы обычно сводят к серии инструкций умножения / сдвига / добавления (как уже упоминалось). См. Оптимизирует ли компилятор a c/ C++ константное деление по степени двойки на сдвиги? для деталей.

Answer 2

Вы можете заменить целочисленное деление на константу умножением (по модулю слова) на магическое число и сдвиг.

Магические числа могут быть предварительно рассчитаны для известных констант.

Поскольку n не может принимать много значений, например, 0..31, "легко" предварительно рассчитать эти магические числа для всех n и сохранить их в таблице с 32 элементами.

Javascript Страница для расчета магических чисел

Хороший компилятор может вычислить магические числа и заменить целочисленное деление умножением и сдвигом, если делитель постоянен во время компиляции. В зависимости от того, как остальная часть кода структурирована вокруг критичного к производительности кода, вы можете использовать макро или встроенные трюки, чтобы развернуть все возможные значения n и позволить компилятору выполнить поиск магических чисел (аналогично ответу с переключателем, но я бы поместил больше кода в константную область, иначе это может быть сделкой, которая не стоит того - ветвление может также снизить производительность)

Подробное описание вместе с кодом для расчета магических чисел можно найти в книге Генри С. Уоррена-младшего "Книга Хакерского восторга" (настоятельно рекомендуется иметь книгу!), Стр. 180 и далее.

Ссылка на Google Книги для соответствующей главы:

Глава 10-9 Беззнаковое деление на делители>= 1