2

I'm trying to get a feel for the difference in performance between integer multiplication compared to bitwise operations...

I have two potential hashing algorithms acting on 64 bit keys, one which uses a single multiply, single right shift, and single mask, the other which involves several shift and mask operations... but I want to try and compare them before implementation since figuring out the magic hashing numbers will take some time to figure out.

On a typical 64 bit processor, approximately how many bitwise operations can execute per 64 bit integer multiplication instruction?

1
  • In retrospect, I could benchmark it with some fake multipliers... creating the real hashing functions may take a significant amount of time because the hashing multipliers are found by guess and check.
    – tbischel
    Aug 4, 2010 at 20:41

3 Answers 3

0

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

This gives a general comparison... doesn't specify 64 bit or 32 bit... but I'll use this as a baseline.

0

Maybe 10 bit operations per multiply, but it's not that simple.

You can overlay the two: do a multiplication while you do bit operations. So the fastest solution may involve doing both.

0

I recommend reading: http://www.intel.com/Assets/PDF/manual/248966.pdf

(Short story: PDF about optimizing for Intel processors. Probably for your purposes very close to the general case)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.