F# performance difference between tail recursion and Seq library

Question

I have this code in F# which finds the smallest positive number that is evenly divisible by all of the numbers from 1 to 20. It takes 10 seconds to complete.

let isDivisableByAll num (divisors: int[]) = Array.forall (fun div -> num % div = 0) divisors

let minNumDividedBy (divisors: int[]) =  
    let rec minNumDividedByAll stopAt acc = 
        if acc >= stopAt then 0
        else if isDivisableByAll acc divisors then acc
        else minNumDividedByAll stopAt (acc + 1)
    minNumDividedByAll 400000000 1

minNumDividedBy [|1..20|]

So, I thought I could make it more elegant, because I prefer less code and wrote the following.

let answer = { 1..400000000 } 
            |> Seq.tryFind (fun el -> isDivisableByAll el [|1..20|])

It took 10 minutes! I couldn't explain the huge difference, since sequences are lazy. In an effort to investigate, I wrote an imperative loop.

let mutable i = 1
while i < 232792561 do
    if isDivisableByAll i [|1..20|] then
        printfn "%d" i
    i <- i + 1

It took 8 minutes. Therefore, it's not the sequence's fault either, right? So, why is the initial function so fast? It can't be avoiding building up the stack, due to tail recursion, can it? Because I wouldn't expect a considerable stack if any, being built in the slow examples either.

It doesn't make much sense to me, can someone tell me?

Thank you.

Echoism

In the second example, you're allocating a new array on every iteration. Over that many iterations it has to add up. Try creating the array first and then running the iterations. – Clitoris

lazy = not fast :-) – Flump

Of course, there is a far simpler way to do this with an algorithmic change. – Coles

The iterative loop still generates a whole bunch of arrays - I think it will be much quicker if you move the [|1..20|] outside the loop. – Coles

Answer 1

As Fyodor Soikin commented, making a new array [|1..20|] for each iteration in the seq solution is the main culprit. If I define the array once and pass it in, I can run it in 10 seconds, compared to 27 seconds for the recursive solution. The remaining disparity must be down to the extra machinery needed around for a lazy sequence, compared to recursion that is tail-call optimised into a for loop.

Making the isDivisableByAll an inline function makes a significant difference for the recursive solution (down to 6 seconds). It doesn't seem to affect the seq solution.

Initial

Oh my god I thought I had tried moving the array comprehension out, but obviously I hadn't. Thank you. – Echoism

One could imagine F# would create an efficient for loop for the Seq expression but currently it doesn't do so. Instead a Seq is created and as @Initial says the overhead of enumerating over it probably explains the difference (2 virtual calls and F# Seq implementations doesn't seem to be as effective as LINQ). That said by changing how you compute the answer you can use Seq and produce the answer in less than 1 ms. – Imputable

You could try to use Nessos Streams and see how that compares. – Imputable

Answer 2

If I understand correctly, you are trying to find how many numbers between 1 and 400000000 (inclusive) are divisible by all the numbers from 1 to 20. I made my own crude version of it:

let factors = Array.rev [| 2 .. 20 |]

let divisible f n =
    Array.forall (fun x -> n % x = 0) f

let solution () =
    {1 .. 400000000}
    |> Seq.filter (divisible factors)
    |> Seq.length

This solution takes over 90 seconds to run where I tested it. But I came to realize that it is a variation of Euler problem number 5, where we learn that 2520 is the first number divisible by all the numbers from 1 to 10. Using this fact, we can create a sequence of multiples of 2520, and test only the numbers from 11 to 19, as the multiples are guaranteed to be divisible by all the numbers from 1 to 10, and 20 as well:

let factors = Array.rev [| 11 .. 19 |]

let divisible f n =
    Array.forall (fun x -> n % x = 0) f

let solution () =
    Seq.initInfinite (fun i -> (i + 1) * 2520)
    |> Seq.takeWhile (fun i -> i <= 400000000)
    |> Seq.filter (divisible factors)
    |> Seq.length

This solution takes 0.191 seconds.

If you don't know about Euler problem number 5, you can even algorithmically compute sequences with elements that are multiples of a given starting value. We feed the algorithm a sequence of numbers divisible by all numbers from 2 to n - 1, and it computes the first number divisible by all numbers from 2 to n. This is iterated through until we have a sequence of multiples of the first number divisible by all the factors we want:

let narrowDown m n s =
    (s, {m .. n})
    ||> Seq.fold (fun a i ->
            let j = Seq.find (fun x -> x % i = 0) a
            Seq.initInfinite (fun i -> (i + 1) * j))

let solution () =
    Seq.initInfinite (fun i -> i + 1)
    |> narrowDown 2 20
    |> Seq.takeWhile (fun i -> i <= 400000000)
    |> Seq.length

This solution runs in 0.018 seconds.

Kodiak

Thank you. To avoid filtering and limiting it, you can write it as: let solution () = Seq.initInfinite (fun i -> (i + 1) * 2520) |> Seq.tryFind (divisible factors) – Echoism

Seq.tryFind does not compute the exact same thing we want here: it provides the first element that fulfills the predicate, or None if it does not exist. What we need here, however, is the number of elements in the sequence (which happens to be 1). – Kodiak

This idea is generalizable so no prior knowledge is required – Imputable

Sorry, dumetrulo, I didn't realize you misunderstood my intention. That's exactly what I wanted, the first element that satisfies the condition. I was not trying to find how many numbers, but the actual number. Anyway, it doesn't matter, the post wasn't even about the most effective euler 5 solution, it was more specific. But thank you for your input, it was clever. – Echoism

OK, in that case the task is equivalent to Euler problem number 5, and you can indeed use Seq.find or Seq.tryFind instead of Seq.filter to get the result. – Kodiak