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

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

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

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

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

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

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


c division integer-division strength-reduction
person J.S.    schedule 25.10.2010    source источник
comment
Есть ли какие-либо ограничения на значения a и n?   -  person The Archetypal Paul    schedule 25.10.2010
comment
В каком контексте вы вызываете функцию?   -  person GManNickG    schedule 25.10.2010
comment
@JR, я не вижу проблемы в сдвиге - это одна инструкция. Это развод, на который нужно время   -  person The Archetypal Paul    schedule 25.10.2010
comment
Если a - 64-битное целое число, вы должны объявить его как таковое. unsigned long гарантированно будет иметь только 32 бита. Используйте для этого uint64_t или uint_least64_t. Для 1 << n, если ваш n может когда-либо перейти на 31, у вас может быть неопределенное поведение. Вместо этого используйте UINT64_C(1) << n.   -  person Jens Gustedt    schedule 26.10.2010

Ответы (2)


arrow_upward
13
arrow_downward

Поскольку вы можете сдвинуть только 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 ++ оптимизирует деление констант на сдвиги по значению степени двойки? для подробностей.

person Michael Burr    schedule 25.10.2010
comment
Интересная идея. Возможно, я смогу написать этот код, а затем извлечь параметры снижения прочности в таблицу. - person J.S.; 25.10.2010
comment
Стоит попробовать, но вы торгуете непредсказуемым прыжком с разницей между инструкциями сдвиг + деление и эквивалентным делением с уменьшенной силой. Есть идеи, когда это хороший компромисс? - person Steve Jessop; 25.10.2010
comment
+1, имеет смысл; хотя вы, вероятно, захотите протестировать это, чтобы подтвердить, что косвенные и / или условные переходы, необходимые для реализации switch(), на самом деле быстрее, чем целочисленное деление ... - person David Gelhar; 25.10.2010
comment
Вы даже можете установить значение по умолчанию, чтобы вернуться к общим случаям. - person GManNickG; 25.10.2010
comment
@ J.S .: не имеет значения, каким a может быть - поскольку n ограничено меньшим, чем количество бит в unsigned int, у вас есть ограниченное количество делителей. - person Michael Burr; 25.10.2010
comment
Я согласен с тем, что ветвление может не ускорить процесс, так что сравнение тестов в порядке. Если это не сработает, есть еще одно возможное решение, которое я постараюсь опубликовать позже (к сожалению, сегодня день переезда ...). - person Michael Burr; 25.10.2010
comment
@Paul: Я добавил ссылку на то, что деление на константы может быть оптимизировано компилятором. - person Michael Burr; 25.10.2010
comment
@MB, PDF-файл hackersdelight просвещает. Эти методы должны хорошо работать здесь ... - person The Archetypal Paul; 25.10.2010
comment
Вы делаете << на int. Это плохо, поскольку на платформе с 32-битной int это приведет к неопределенному поведению. Используйте 1UL << something вместо 1 << something. - person Jens Gustedt; 25.10.2010
comment
@JG, нам сказали, что n от 10 до 25 или около того, так что здесь не проблема. - person The Archetypal Paul; 25.10.2010
comment
Кроме того, небольшая помощь могла бы записать (1 << n) + 1 как (1ul << n) | 1ul, поскольку все значения выражения заканчиваются на 1 - person Ed.C; 25.10.2010
comment
@Jens: Операция << была в исходной спецификации - она ​​не является неопределенной, если значение n не больше или равно ширине продвинутого левого операнда. Поскольку он находится в исходной функции, я предположил, что значение n будет подходящим. - person Michael Burr; 25.10.2010
comment
@ Ed.C: Я не уверен, что это могло бы помочь. - person Michael Burr; 25.10.2010
comment
Вероятно, ничего, но это практическое правило - по возможности использовать бинарные операторы вместо арифметических. - person Ed.C; 25.10.2010
comment
Этот переключатель почти наверняка намного медленнее, чем разделение на современном оборудовании. Вместо этого вы должны составить таблицу операций умножения-сдвига-сложения, которые компилятор генерирует для каждой, а затем использовать n в качестве индекса в этой таблице и применять их самостоятельно. - person R.. GitHub STOP HELPING ICE; 26.10.2010

arrow_upward
9
arrow_downward

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

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

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

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

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

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

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

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

person Peer Stritzinger    schedule 25.10.2010