Performance of seq<int> vs Lazy<LazyList<int>> 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

Bouffant

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.

Profit

I'm surprised that a seq-comprehension is so much faster than Seq.map. I also tried to get this to work with F# PowerPack, but I haven't been successful so far. – Bouffant

@fysx Use my ExtCore library - it contains an updated (and maintained) version of the LazyList code from the F# PowerPack. It also has a lazyList builder which greatly simplifies writing this kind of code. – Profit

@fysx The seq-comprehension is usually faster because it can be better optimized by the compiler. Seq.map isn't inherently slow, but in this case there's a lot of overhead because the code is repeatedly evaluating the sequence, and the compiled code has to allocate a closure each time Seq.map is called. – Profit

I used the Package Manager Console and 'Install-Package ExtCore'. Without main, but only (-|-) and hamming, I get "This expression was expected to have type LazyList<'a> but here has type LazyList<uint64>" for hamming. I'm using Visual Studio 2013. I tried specifying the types, but generally there's some type mismatch between lazyList and hamming. Sad. – Bouffant

@fysx That's odd -- I have no problem compiling the code above, even if I comment out main. Would you mind opening an issue on the ExtCore github page about this? I'd like to help you solve the problem and it'd be easy to move the discussion there. – Profit

My bad. I had both FSharp.PowerPack and ExtCore as references. Removing FSharp.PowerPack made it work. – Bouffant

LazyList is containined in ExtCore, a Nuget package for FSharp: github.com/jack-pappas/ExtCore – Ethelynethene

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.

Phrase

Sprinkling |> Seq.cache throughout after I use seq {...} does improve performance, but not substantially (especially if I compute much larger numbers in the sequence. I noticed https://mcmap.net/q/714122/-sequence-vs-lazylist, which seems to compliment your suggestion well. – Bouffant

For 1..100 it made it near-instantaneous compared to very slow. What's a typical number where your lazy lists still outperform it substantially? – Phrase

OK, I see it doesn't really work well for 1000 and 10000 is a dead loss even if I put Seq.cache on every single sequence. – Phrase

Try 1500. The LazyList version should be noticeably faster. – Bouffant

ExtCore includes a lazyList computation builder, so you need not build your own :) – Profit

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

Glimmer