Why is List.allPairs much slower than List.collect+map?

General
1 
> let numbers = [1 .. 10000];;

> let t1 =
    (numbers, numbers)
    ||> List.allPairs
    |> List.map (fun (x, y) -> x + y);;
Real: 00:00:24.137, CPU: 00:00:24.390, GC gen0: 1411, gen1: 496, gen2: 8

> let t2 =
    numbers
    |> List.collect (fun x ->
        numbers |> List.map (fun y -> x + y));;
Real: 00:00:13.730, CPU: 00:00:13.734, GC gen0: 1022, gen1: 360, gen2: 1
val t2 : int list =
  [2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22;
   23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40; 41;
   42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57; 58; 59; 60;
   61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74; 75; 76; 77; 78; 79;
   80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96; 97; 98;
   99; 100; 101; ...]

> t1 = t2;;
Real: 00:00:03.298, CPU: 00:00:03.296, GC gen0: 1148, gen1: 1, gen2: 0
val it : bool = true

I expected List.allPairs would be faster than (or, at least, comparable to) List.collect+map, but the results show the contrary: allPairs is ~2x slower. Am I missing something?

FYI, source code for List.collect and List.allPairs is found at https://github.com/dotnet/fsharp/blob/master/src/fsharp/FSharp.Core/local.fs .

2

I would guess that’s because the first one allocates N*N pairs, in addition to 2*N*N list elements which they both allocate.

3

That’s very odd comparing.

List.allPairs creates pairs and this operation costs something by itself. Then you additional performs map.

In the second case you just skipping step of creating pairs.

That’s why you got such results.

Try to compare something like this:

List.allPairs numbers numbers

vs

List.collect(fun x -> numbers |> List.map (fun y -> x,y)) numbers

List.allPairs numbers numbers
|> List.map (fun (x, y) -> x+y)

vs

List.collect(fun x -> numbers |> List.map (fun y -> x+y)) numbers 
|> List.map id
4

I misunderstood the purpose of List.allPairs. :exploding_head:

Now I’m replacing where allPairs+map is used with

let crossMap mapper source1 source2 =
    source1 |> List.collect (fun x ->
        source2 |> List.map (fun y ->
            mapper x y))

Thanks.