I was wondering why I get such disparate results between apparently equal algorithms in C# and F#.
F# code variants:
open System
{ 1I..(bigint (Int32.MaxValue / 100)) } |> Seq.sum
let mutable sum = 0I
for i in 1I..(bigint (Int32.MaxValue / 100)) do
sum <- sum + i
sum
let sum = ref 0I
for i in 1I..(bigint (Int32.MaxValue / 100)) do
sum := !sum + i
sum
Full F# code (4s):
[<EntryPoint>]
let main argv =
let sw = new Stopwatch()
sw.Start()
printfn "%A" ({ 1I..(bigint (Int32.MaxValue / 100)) } |> Seq.sum)
sw.Stop()
printfn "took %A" sw.Elapsed
Console.ReadKey() |> ignore
0
Full C# code (22s):
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Start();
BigInteger sum = new BigInteger(0);
BigInteger max = new BigInteger(Int32.MaxValue / 100);
Console.WriteLine(max);
for (BigInteger i = new BigInteger(1); i <= max; ++i)
{
sum += i;
}
sw.Stop();
Console.WriteLine(sum);
Console.WriteLine(sw.Elapsed);
Console.ReadKey();
}
The F# code takes more than 22s on any of its variants (I assumed different implementations would yield different running times but that doesn't seem to be the case). On the other hand, the C# code seems to be way faster. Both yield the same final sum result, so I guess the algorithms are equivalent. I double checked and the F# code seems to be compiled with the --optimize+
flag.
Am I doing something wrong?
Converting the F# code from
{ 1I..(bigint (Int32.MaxValue / 100)) } |> Seq.sum;;
Real: 00:00:14.014, CPU: 00:00:14.196, GC gen0: 1743, gen1: 0
to
let mutable t = 1I
let mutable res = 0I
let max = bigint (Int32.MaxValue / 100)
while t < max do
res <- res + t
t <- t + 1I;;
Real: 00:00:05.379, CPU: 00:00:05.450, GC gen0: 748, gen1: 0
Approxiamately triples the speed, and is also closer to the original C# code.
The most likely reason is that both {...}
and for i in ...
create a dummy seq
. By removing this, you avoid the seq
overhead.
EDIT
For some reason F# is generating a ridiculous amount of IL for this code, and is using a really weird comparison.
If we explicitly force the comparison, the speed doubles (which is a little ridiculous)
This code gets pretty much exactly the same speed as the C# for me (on mono).
let mutable t = 1I
let mutable res = 0I
let max = (bigint (Int32.MaxValue / 100));;
while System.Numerics.BigInteger.op_GreaterThan(max,t) do
res <- res + t;t<-System.Numerics.BigInteger.op_Increment(t)
printfn "%A" res
but is unnecersarrily verbose.
I will probably file a compiler bug about this.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With