Optimize LazyList implementation

[jack-pappas]

Via the fsharp-opensource mailing list, Greg Chapman suggested a possible optimization for LazyList:

https://groups.google.com/forum/#!searchin/fsharp-opensource/lazy/fsharp-opensource/Zd221uJ0BGM/A1h8bJtv_c0J

I've noticed that both the PowerPack and ExtCore implementations of LazyList wrap a delay around the LazyLists produced by cons and consDelayed. It seems to me that this is unnecessary, since both functions are given the value which will be the head of the new LazyList (so there's no need to delay calculating it). To be specific, here's some code from the PowerPack:

let lzy f = { status = Delayed f }

let notlazy v = { status = Value v }

let consc x l = CellCons(x,l)
let cons x l = lzy(fun () -> (consc x l))

It seems to me that you could change cons to:

let cons x l = notlazy (consc x l)

without breaking anything or decreasing the laziness. Am I missing something?

[jack-pappas]

I took a bit of time to test this modification. I've significantly refactored the code since Greg's original post to fsharp-opensource, so his modification looks like this (using code from ExtCore 0.8.35):

/// Return a new list which contains the given item followed by the given list.
    static member internal Cons (value, list) : LazyList<'T> =
        // Preconditions
        checkNonNull "list" list

        // Original code
//        LazyList<_>.CreateLazy <| fun () ->
//            Cons (value, list)

        // Implementation suggested by issue #3.
        LazyList (Value (Cons (value, list)))

I compiled ExtCore both with and without the suggested optimization, in both Debug and Release configurations. I ran the unit tests for the LazyList fixture using the NUnit GUI Runner several times for each combination, and recorded the running time for each test run (in seconds).

---

Compiled in Debug configuration:

Original	Modified
6.6624	5.2342
5.9453	6.1713
5.5763	6.8233
5.7023	5.6503
5.4343	5.4683
5.4283	5.6393
5.5753	5.3663
6.2723	5.6673
	5.4863
	6.1563
	5.5833
	5.8903

Statistics

	Avg.	Min.	Max.
Original	5.8246	5.4283	6.6624
Modified	5.7614	5.2342	6.8233

---

Compiled in Release configuration:

Original	Modified
2.1211	2.0631
2.2691	2.3281
2.2641	2.2961
2.2600	2.2991
2.2700	2.3051
2.0471	2.2411
2.2821	2.2871
2.2411	2.3031
2.4271	2.2681
2.2901	2.2751

Statistics

	Avg.	Min.	Max.
Original	2.2472	2.0471	2.4271
Modified	2.2666	2.0631	2.3281

---

It looks like the optimization provides a small but consistent improvement for the Debug configuration. The Release results aren't as clear-cut -- the average and minimum running time of the unit tests is roughly the same (the original is faster by <1%), but the optimization does seems to improve the maximum running time.

Based on these results, it's difficult to definitively say whether it's worth incorporating this optimization. To get a better comparison of the performance gains to be had, it would be useful to construct some benchmarks with longer running times and larger lists. Once these are constructed, it would also be good to compare the memory usage and GC impact of the optimization; it seems that the optimized version would provide more improvement in these areas, rather than improving execution speed (since the optimization avoids creating unnecessary closures).

One last note -- after making the optimization, all of the LazyList tests in the ExtCore.Tests project still pass, so it seems like this optimization preserves the expected laziness of the data structure.

[jack-pappas]

It may be worth revisiting this and re-performing the benchmark with BenchmarkDotNet on the latest .NET framework.