Performance of seq<int> vs Lazy<LazyList<int>> in F#
f#, hamming-numbers, infinite, seq
Solution
Ganesh is right in that you're evaluating the sequence multiple times. `Seq.cache` will help improve performance, but you get much better performance out of `LazyList` because the underlying sequence is only ever evaluated once then cached, so it can be traversed much more rapidly. In fact, this is a good example of where `LazyList` should be used over a normal `seq`.
It also looks like there is some significant overhead introduced by your use of `Seq.map` here. I believe the compiler is allocating a closure each time it's called there. I changed your `seq` based code to use `seq`-expressions there instead, and it's about 1/3 faster than the original for the first 40 numbers in the sequence:
let rec hamming: seq<int> = seq {
yield 1
let xs = seq { for x in hamming do yield x * 2 }
let ys = seq { for x in hamming do yield x * 3 }
let zs = seq { for x in hamming do yield x * 5 }
yield! xs -|- ys -|- zs
}
My ExtCore library includes a `lazyList` computation builder which works just like `seq`, so you can simplify your code like this:
// 2-way merge with deduplication
let rec (-|-) (xs: LazyList<'T>) (ys: LazyList<'T>) =
let x = LazyList.head xs
let y = LazyList.head ys
let xstl = LazyList.skip 1 xs
let ystl = LazyList.skip 1 ys
if x < y then lazyList { yield x; yield! xstl -|- ys }
elif x > y then lazyList { yield y; yield! xs -|- ystl }
else lazyList { yield x; yield! xstl -|- ystl }
let rec hamming : LazyList<uint64> = lazyList {
yield 1UL
let xs = LazyList.map ((*) 2UL) hamming
let ys = LazyList.map ((*) 3UL) hamming
let zs = LazyList.map ((*) 5UL) hamming
yield! xs -|- ys -|- zs
}
[<EntryPoint>]
let main argv =
let watch = Stopwatch.StartNew ()
hamming
|> LazyList.take 2000
|> LazyList.iter (printf "%d, ")
watch.Stop ()
printfn ""
printfn "Elapsed time: %.4fms" watch.Elapsed.TotalMilliseconds
System.Console.ReadKey () |> ignore
0 // Return an integer exit code
(NOTE: I also made your `(-|-)` function generic, and modified `hamming` to use 64-bit unsigned ints because 32-bit signed ints overflow after a bit). This code runs through the first 2000 elements of the sequence on my machine in ~450ms; the first 10000 elements takes ~3500ms.
Problem
There is a well known solution for generating an infinite stream of Hamming numbers (i.e. all positive integers `n` where `n = 2^i * 3^j * 5^k`). I have implemented this in two different ways in F#. The first method uses `seq<int>`. The solution is elegant, but the performance is terrible. The second method uses a custom type where the tail is wrapped in `Lazy<LazyList<int>>`. The solution is clunky, but the performance is amazing. Can someone explain why the performance using `seq<int>` is so bad and if there is a way to fix it? Thanks. Method 1 using `seq<int>`. ``` // 2-way merge with deduplication let rec (-|-) (xs: seq<int>) (ys: seq<int>) = let x = Seq.head xs let y = Seq.head ys let xstl = Seq.skip 1 xs let ystl = Seq.skip 1 ys if x < y then seq { yield x; yield! xstl -|- ys } elif x > y then seq { yield y; yield! xs -|- ystl } else seq { yield x; yield! xstl -|- ystl } let rec hamming: seq<int> = seq { yield 1 let xs = Seq.map ((*) 2) hamming let ys = Seq.map ((*) 3) hamming let zs = Seq.map ((*) 5) hamming yield! xs -|- ys -|- zs } [<EntryPoint>] let main argv = Seq.iter (printf "%d, ") <| Seq.take 100 hamming 0 ``` Method 2 using `Lazy<LazyList<int>>`. ``` type LazyList<'a> = Cons of 'a * Lazy<LazyList<'a>> // Map `f` over an infinite lazy list let rec inf_map f (Cons(x, g)) = Cons(f x, lazy(inf_map f (g.Force()))) // 2-way merge with deduplication let rec (-|-) (Cons(x, f) as xs) (Cons(y, g) as ys) = if x < y then Cons(x, lazy(f.Force() -|- ys)) elif x > y then Cons(y, lazy(xs -|- g.Force())) else Cons(x, lazy(f.Force() -|- g.Force())) let rec hamming = Cons(1, lazy(let xs = inf_map ((*) 2) hamming let ys = inf_map ((*) 3) hamming let zs = inf_map ((*) 5) hamming xs -|- ys -|- zs)) [<EntryPoint>] let main args = let a = ref hamming let i = ref 0 while !i < 100 do match !a with | Cons (x, f) -> printf "%d, " x a := f.Force() i := !i + 1 0 ```