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

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

16 голосов
/ 25 октября 2010

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

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

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

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

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

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

Ответы [ 2 ]

13 голосов
/ 25 октября 2010

Поскольку вы можете сдвинуть только 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);
    }
}

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

8 голосов
/ 25 октября 2010

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

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

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

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

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

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

Глава 10-9 Разделение без знака по делителям> = 1

...