64 bit integer math and bitwise operation benchmarks

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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)