Тесты 64-битной целочисленной математики и побитовых операций

Я пытаюсь почувствовать разницу в производительности между целочисленным умножением по сравнению с побитовыми операциями...

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

На типичном 64-битном процессоре сколько примерно побитовых операций может выполняться на одну 64-битную инструкцию умножения целых чисел?


person tbischel    schedule 03.08.2010    source источник
comment
Оглядываясь назад, я мог бы сравнить его с некоторыми фальшивыми множителями... создание реальных функций хеширования может занять значительное время, потому что множители хеширования находятся путем угадывания и проверки.   -  person tbischel    schedule 05.08.2010


Ответы (3)


http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math/

Это дает общее сравнение... не указывает 64-битную или 32-битную... но я буду использовать это как основу.

person tbischel    schedule 04.08.2010

Может быть, 10 битных операций на умножение, но это не так просто.

Вы можете наложить их друг на друга: выполняйте умножение, пока выполняете битовые операции. Таким образом, самое быстрое решение может включать в себя выполнение обоих.

person Charles    schedule 04.08.2010

Я рекомендую прочитать: http://www.intel.com/Assets/PDF/manual/248966.pdf

(Краткий рассказ: PDF про оптимизацию под процессоры Intel. Наверное для ваших целей очень близко к общему случаю)

person Slartibartfast    schedule 05.08.2010