Integer arithmetic performance 32 vs. 64-bit

4
votes

I have 2 machines running F# 2.0 Interactive build 4.0.30319.1 on vs 2010. Several of my programs ran significantly slower on the faster machine. The problem appears to be that integer arithmetic performance on a 32-bit Windows is significantly slower than 64 Windows.

On the slightly slower Windows 7 64-bit machine (the program is listed below):

primeCount = 1270607
Real: 00:00:07.553, CPU: 00:00:07.519, GC gen0: 0, gen1: 0, gen2: 0

On the slightly faster Windows XP SP2 machine :

primeCount = 1270607
Real: 00:00:32.800, CPU: 00:00:32.796, GC gen0: 0, gen1: 0, gen2: 0

So the 32-bit version takes more than 4 times as long as the 64-bit version. I am assuming that there is not a significant difference due to the different operating systems, othen than the word length that is supported.

Program:

let isPrime(n) =
    if n < 2 then false
    elif (n % 2) = 0 then                   // take care of even case
        if n = 2 then true
        else false
    else                                    // n is odd
        let ms = int(sqrt(float(n)))
        let rec isPrimeUtil(m) =
            if m > ms then true
            elif n % m = 0 then false
            else isPrimeUtil(m + 2)
        isPrimeUtil(3)

let nums = [1 .. 20000000]
let pcountref = ref 0                       // # of primes found

let primeCount =
    pcountref := 0
    for x in nums do
        if (isPrime x) then incr pcountref

do primeCount
printfn "primeCount = %d" !pcountref

Send the program to interactive. #time;; Then to measure the elapsed time for processing, and not the generation of the range nums, select the line

let pcountref = ref 0

and all subsequent lines and send to interactive.

3
performancef#
Where does BigInteger come in? The code you've shown certainly doesn't use it... - ildjarn
oops! you are correct. The issue seems to be 64 vs 32 bit arithmetic. - DougT
@DougT - int is 32 bits on 32 bit and 64 bit - John Palmer
FSI is 32 bit, so you're running 32bit versions on both your machines. Check System.IntPtr.Size*8 in FSI on the 64 bit machine. I'm pretty sure the answer will be 32. - John Reynolds
> System.IntPtr.Size*8;; val it : int = 32 - DougT

3 Answers

3
votes

I think the more likely explanation is that the 64 bit JIT performs tail call optimizations which the 32 bit JIT does not. THe isPrimeUtil function could be optimised

Note that the given example doesn't use BigInteger anyway, there is also room for algorithmic improvements - a sieve will run much faster

1
votes

float is 64 bit, so the sqrt(float(n)) call is probably your performance sink. (And would explain why the 64 bit machine handles it much better.)

Try float32 if you don't need / the precision.

See : http://msdn.microsoft.com/en-us/library/dd233210.aspx

I don't have a 32 bit machine to test, but on my 64 bit machine just testing the sqrt code takes a reasonable chunk of time.

let nums = [1 .. 20000000]

let ans = List.map (fun n -> int(sqrt(float(n))) nums

Gives a real time of 5.120s - which is a significant chunk of your execution time.

0
votes

These results make sense. BigNum implementations often use a machine integer until they detect overflow, and then switch to a more complex representation. 64-bit integers can hold much larger values than 32-bit integers. Your test program is probably spending much more of the test doing fast machine arithmetic when it's running on 64-bit.