CODEWITHSUNDEEP
performancef#sequence
FlyingHubert
FlyingHubert

Reputation: 35

F# performance bad compared to e.g. Java. What am I doing wrong?

I'm currently trying to get into programming with F#. Therefore I wrote a simple F# script to calculate PI in a very silly way. I've written this algorithm in many programming languages but this time it is pretty slow in execution and I don't know what I'm doing wrong. Compared to my Java Version this here is about 10-20 times slower (about 10-15 sek on my machine running in VS Code by pressing Alt+Enter) which is a lot (in my opinion).

The algorithms idea is to throw darts at an 1 by 1 square with an circle in it. The circle touches the edges of the square. If a dart hits the circle it gets counted. After all darts are thrown you just divide the dart hit count by the total number of darts and multiply by 4 to get PI.

I've tried many things to get my error but couldn't find it.

PS: I know that this method to calc Pi sucks. But this is not the point I try to make here.

open System

let random = Random(DateTime.Now.Millisecond)
let throwDart i = (random.NextDouble(), random.NextDouble())

let distance dart point = let (x1, y1), (x2, y2) = dart, point
                          (x2 - x1, y2 - y1)
let length distance = let (x, y) = distance
                      Math.Sqrt(x * x + y * y)

let isInside circle dartHit = 
        let (center, radius) = circle 
        distance center dartHit |> length  |> (fun x -> x < radius)

let circle = ((0.5, 0.5), 0.5)

let dartCount = 100000000

let dartSeqence = Seq.init dartCount throwDart
let pi = float(dartSeqence |> Seq.filter (isInside circle) |> Seq.length) / float(dartCount) * 4.0

Maybe someone has an idea what I am doing wrong. I hoped that F# would do well in this task because its a pretty simple and straight algorithm.

Thanks for the help in advance.

Update 1:

Hi after running my Java code again I was a bit disappointed, because I thought it was faster. This is the code running for approx. 4.4 sec on my machine:

import java.util.Random;

public class DartThrower{
    Random random;

    public DartThrower(){
        random = new Random();
    }
    public boolean throwDart(){
        double x = random.nextDouble();
        double y = random.nextDouble();
        // wenn Entfernung des Punktes vom Mittelpunkt (0.5|0.5) größer als 0.5 ist wird false ausgegeben
        boolean inTheCircle = Math.sqrt((0.5 - x) * (0.5 - x) + (0.5 - y) * (0.5 - y)) <= 0.5;  
        return inTheCircle;
    }
}

class PiCalculator{
    public static void main(String[] args){
        long start = System.currentTimeMillis();
        double hitCount = 0.0;
        double throwCount = 100000000L;
        DartThrower thrower = new DartThrower();

        for (long i = 0; i < throwCount; i++){
            boolean hit = thrower.throwDart();
            hitCount += hit ? 1 : 0;
        }
        double a = hitCount / throwCount;
        double pi = a * 4.0;
        System.out.println("Pi= " + pi);
        System.out.println("took " + (System.currentTimeMillis() - start) + "ms");
    }
}

I'm sorry, but I thought the time was under 1s - thats why I was talking about a 10-20 times faster execution. That's not correct! After I had relaized how wrong I was in the timing, I decided to add some Timestamps for both and got

So factor 3-4 between those two. This difference might by obsolete if I try to use @Tomas Petricek's performance updates. I'll try that and tell you the results.

Thanks for your help so far.

Upvotes: 1

Views: 213

Answers (1)

Tomas Petricek
Tomas Petricek

Reputation: 243051

You can make this about 2x faster by replacing the lazy sequence with a simple mutable variable and a for loop (there is nothing bad about this in performance critical F# code):

let mutable count = 0
for i in 0 .. dartCount do
  if isInside circle (throwDart i) then count <- count + 1
let pi = float count / float dartCount * 4.0

You can add a bit more performance (about 30% in my rough tests) by making the functions inline, which may eliminate some boxing of values as tuples:

let inline distance dart point = 
  let (x1, y1), (x2, y2) = dart, point
  (x2 - x1, y2 - y1)

let inline length distance = 
  let (x, y) = distance
  Math.Sqrt(x * x + y * y)

let inline isInside circle dartHit = 
  let (center, radius) = circle 
  length (distance center dartHit) < radius

With this, I do not see any obvious issues (but I may be missing something). It would be good to see your Java code for comparison, because there may be some subtle logic change that affects the performance.

Upvotes: 6

Related Questions