ocaml and int64

Ludovic Coquelle

Jon Harrop
 Sylvain Le Gall

Jon Harrop
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20080402 (09:44) 
From:  Sylvain Le Gall <sylvain@l...> 
Subject:  Re: ocaml and int64 
On 02042008, Jon Harrop <jon@ffconsultancy.com> wrote: > On Wednesday 02 April 2008 01:54:54 Ludovic Coquelle wrote: >> Hi, >> >> I wrote a direct translation of a simple algo from F# to ocaml. >> (details can be found here: >> http://khigia.wordpress.com/2008/03/30/ocamlvsfforbigintegersurprisin >>gperformancetest/ ) >> >> The compile F# program (12s) is much faster than Ocaml (30s), probably >> because the algo do integer arithmetic with Int64 module (thanks to David >> for this info). >> >> Have someone here face this kind of problem (optimizing a code doing >> arithmetic on big integer)? >> Any advice to improve the Ocaml code (without changing the algo)? > > Get a 64bit machine. ;) > > There are some performance pitfalls in your code (which takes 21s on my > machine): > > . OCaml makes no attempt to optimize integer div and mod so avoid these at all > costs. In this case, use bitwise ANDs and shifts. > > . Int64 is boxed by default and your use of recursion is likely to worsen this > effect. > > Optimizing for these, the following code takes only 4.6s, which is 4.6x faster > than your original: Nice speed up... But without changing the algo, replace seq_length by: let limit_int = (max_int / 3)  1 ;; let limit_int64 = Int64.of_int max_int ;; let rec seq_length_int x n = match x with  0 > (n + 1)  1 > seq_length_int 0 (n + 1)  x when x mod 2 = 0 > seq_length_int (x / 2) (n + 1)  _ > if x < limit_int then seq_length_int ((3 * x) + 1) (n + 1) else seq_length_int64 (Int64.of_int x) n and seq_length_int64 x n = match x with  0L > (n + 1)  1L > seq_length_int64 0L (n + 1)  x when x %% 2L = 0L > let nx = x // 2L in if Int64.compare nx limit_int64 < 0 then seq_length_int (Int64.to_int nx) (n + 1) else seq_length_int64 nx (n + 1)  _ > seq_length_int64 (Int64.succ (3L ** x)) (n + 1) ;; let seq_length = seq_length_int64 ;; Give you a 19x speed up on 32 bit machine. On 64 bit machine this should lead to nearly native performance (i.e. beat F# more than you think). The trick is very simple: switch to "int" as soon as you can, only use boxed integer when you cannot do anything else (in my case the limit is when we go from 64bit to 31bit integer, but on 64bit machine this will be when you go from 64bit to 63bit integer i.e. you will always compute using "int" which will be native perf). You can explain the perf gain by doing some statistic on 3n + 1, n / 2, to see how much time is spend under max_int... and explain the speedup ;) Applying the ">>>" trick of Dr. Harrop doesn't really improve perf here (even if it is a good idea). Regards, Sylvain Le Gall ps: for the sake of writing better code, there is a way to write the code in a more generic way, but i am too lazy pps: gildor@peta:~/tmp/ocamltest/eul14$ time ./eul14 837799 real 1m11.870s user 1m11.324s sys 0m0.428s (with seq_length_int/seq_length_int64) gildor@peta:~/tmp/ocamltest/eul14$ time ./eul14 837799 real 0m3.736s user 0m3.676s sys 0m0.052s