List, array comprehension implementation

[kerams]

List and array comprehensions appear to be implemented in terms of sequence computation expressions. Is there a specific reason why individual items aren't generated into ResizeArray, which would then be converted into the required collection?

let rec ofRa<'a> (ra: ResizeArray<'a>, index, acc) =
    if index = 0 then
        acc
    else
        ofRa (ra, index - 1, ra.[index - 1] :: acc)

[<MemoryDiagnoser>]
type Test () =
    [<Params(10, 100, 1000, 10000, 100000)>]
    member val Count = 0 with get, set

    [<Benchmark>]
    member x.List () = [ for i in 0 .. x.Count -> i ] 

    [<Benchmark>]
    member x.Array () = [| for i in 0 .. x.Count -> i |]

    [<Benchmark>]
    member x.ResizeArray () =
        let ra = ResizeArray ()
        for i in 0 .. x.Count do ra.Add i
        ra

    [<Benchmark>]
    member x.ResizeArrayToArray () =
        let ra = ResizeArray ()
        for i in 0 .. x.Count do ra.Add i
        ra.ToArray ()

    [<Benchmark>]
    member x.ResizeArrayToList () =
        let ra = ResizeArray ()
        for i in 0 .. x.Count do ra.Add i
        ofRa (ra, ra.Count, [])

Method	Count	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
List	10	224.80 ns	1.110 ns	1.039 ns	0.0648	-	-	544 B
Array	10	282.40 ns	1.746 ns	1.633 ns	0.0572	-	-	480 B
ResizeArray	10	55.10 ns	0.795 ns	0.743 ns	0.0258	-	-	216 B
ResizeArrayToArray	10	66.10 ns	0.917 ns	0.858 ns	0.0343	-	-	288 B
ResizeArrayToList	10	112.53 ns	1.897 ns	1.775 ns	0.0677	-	-	568 B
List	100	1,473.20 ns	5.194 ns	4.859 ns	0.4082	0.0095	-	3424 B
Array	100	1,435.52 ns	6.659 ns	5.560 ns	0.2155	-	-	1808 B
ResizeArray	100	266.71 ns	1.230 ns	1.151 ns	0.1411	0.0005	-	1184 B
ResizeArrayToArray	100	292.41 ns	0.448 ns	0.397 ns	0.1931	0.0005	-	1616 B
ResizeArrayToList	100	713.22 ns	3.153 ns	2.950 ns	0.5274	0.0095	-	4416 B
List	1000	14,171.53 ns	63.155 ns	55.985 ns	3.8452	0.7172	-	32224 B
Array	1000	13,736.88 ns	42.422 ns	35.424 ns	1.5106	0.0458	-	12648 B
ResizeArray	1000	2,260.70 ns	10.999 ns	10.289 ns	1.0033	0.0305	-	8424 B
ResizeArrayToArray	1000	2,494.23 ns	26.963 ns	25.221 ns	1.4877	0.0458	-	12456 B
ResizeArrayToList	1000	6,743.22 ns	101.222 ns	89.730 ns	4.8294	0.6027	-	40456 B
List	10000	154,911.71 ns	848.803 ns	793.971 ns	38.0859	14.1602	-	320224 B
Array	10000	119,750.13 ns	1,492.511 ns	1,396.096 ns	20.3857	5.0049	-	171624 B
ResizeArray	10000	23,069.41 ns	97.950 ns	91.623 ns	15.5945	5.1880	-	131400 B
ResizeArrayToArray	10000	25,548.04 ns	32.049 ns	29.979 ns	20.3857	5.0659	-	171432 B
ResizeArrayToList	10000	83,056.92 ns	1,385.099 ns	1,156.620 ns	53.8330	24.5361	-	451432 B
List	100000	2,574,300.07 ns	17,289.879 ns	16,172.963 ns	378.9063	187.5000	-	3200224 B
Array	100000	1,276,685.00 ns	9,572.855 ns	8,954.455 ns	398.4375	398.4375	398.4375	1449200 B
ResizeArray	100000	254,428.85 ns	186.175 ns	165.039 ns	285.6445	285.6445	285.6445	1048976 B
ResizeArrayToArray	100000	295,869.26 ns	972.164 ns	909.363 ns	399.9023	399.9023	399.9023	1449008 B
ResizeArrayToList	100000	2,206,971.22 ns	10,948.036 ns	10,240.799 ns	570.3125	285.1563	285.1563	4249008 B

For arrays, the benchmark is a landslide in favor of the latter approach. Lists would allocate a bit more in the end, but be around twice as fast given a reasonable amount of elements (I don't suppose list is the right choice for 100k elements, whatever the use case).

Going even further, with ranges like above, the item count is known in advance, so one could allocate an array of exactly the right size and feed items into that.

[cartermp]

Off the top of my head I can't see a reason why they would require emitting with a sequence, but I'm not sure which code is responsible for that (perhaps iLXGen?). Marking it as an improvement for now

[NinoFloris]

One of the goals of the resumable code rfc is (edit: enabling) faster list/array/seq builders

https://github.com/fsharp/fslang-design/blob/master/RFCs/FS-1087-resumable-code-and-task-builder.md#example-low-allocation-list-and-array-builders

[dsyme]

Is there a specific reason why individual items aren't generated into ResizeArray, which would then be converted into the required collection?

Seq.toArray does use a ResizeArray. But yes, in many cases we could avoid the allocation of the temporary IEnumerable and its overheads (including writing directly to an array when the size is known). Nino is right that's what FS-1087 is partly about.

[forki]

Yay

[dsyme]

Actually was done in #11592