Performance of seq vs Lazy> in F#

Question

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

Answer 1

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.

Answer 2

Your seq for hamming is re-evaluated from the beginning on each recursive call. Seq.cache is some help:

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
    } |> Seq.cache

However as you point out the LazyList is still much better on large inputs, even if every single sequence is cached.

I'm not entirely certain why they differ by more than a small constant factor, but perhaps it's better to just focus on making the LazyList less ugly. Writing something to convert it to a seq makes processing it much nicer:

module LazyList =
    let rec toSeq l =
        match l with
        | Cons (x, xs) ->
            seq {
                yield x
                yield! toSeq xs.Value
            }

You can then use your simple main directly. It's also not really necessary to use mutation to process the LazyList, you could just do so recursively.

The definition doesn't look so bad though the lazy and Force() do clutter it up a bit. That looks marginally better if you use .Value instead of .Force(). You could also define a computation builder for LazyList similar to the seq one to recover the really nice syntax, though I'm not sure it's worth the effort.

Answer 3

Here is a sequence base version with better performance.

let hamming =
    let rec loop nextHs =
        seq {
            let h = nextHs |> Set.minElement
            yield h
            yield! nextHs 
                |> Set.remove h 
                |> Set.add (h*2) |> Set.add (h*3) |> Set.add (h*5) 
                |> loop
            }

    Set.empty<int> |> Set.add 1 |> loop