Slow tail recursion in F #

Question

I have a F # function that returns a list of numbers starting at 0 in the skip pattern n, selects n, skips n, selects n ... to the limit. For example, this function for input 2 will return [2, 3, 6, 7, 10, 11...] .

I initially implemented this as a tailless function, as shown below:

 let rec indicesForStep start blockSize maxSize = match start with | i when i > maxSize -> [] | _ -> [for j in start .. ((min (start + blockSize) maxSize) - 1) -> j] @ indicesForStep (start + 2 * blockSize) blockSize maxSize 

Thinking that tail recursion is desirable, I reimplemented it using the battery list as follows:

 let indicesForStepTail start blockSize maxSize = let rec indicesForStepInternal istart accumList = match istart with | i when i > maxSize -> accumList | _ -> indicesForStepInternal (istart + 2 * blockSize) (accumList @ [for j in istart .. ((min (istart + blockSize) maxSize) - 1) -> j]) indicesForStepInternal start [] 

However, when I run this in fsi in Mono with parameters 1, 1 and 20 000 (ie it should return [1, 3, 5, 7...] up to 20 000), the tail recursive version is much slower than the first version ( 12 seconds compared to sub-second).

Why is the tail recursive version slower? Is it because of list concatenation? Is this compiler optimization? Did I really implement its tail recursively?

It also seems to me that I should use higher order functions for this, but I'm not sure how to do it.

Answer 1

As Dave points out, the problem is that you are using the @ operator to add lists. This is a more significant performance issue than tail recursion. In fact, tail recursion doesn't speed up the program too much (but it makes it work on large inputs, where the stack overflows).

The reason your second version is slower is because you add a shorter list (the one generated using [...] ) to the longer list ( accumList ). This is slower than adding a longer list to a shorter list (because the operation must copy the first list).

You can fix this by collecting the elements in the battery in the reverse order and then reversing it before returning the result:

 let indicesForStepTail start blockSize maxSize = let rec indicesForStepInternal istart accumList = match istart with | i when i > maxSize -> accumList |> List.rev | _ -> let acc = [for j in ((min (istart + blockSize) maxSize) - 1) .. -1 .. istart -> j] @ accumList indicesForStepInternal (istart + 2 * blockSize) acc indicesForStepInternal start [] 

As you can see, this shorter list (generated using [...] ) as the first argument to @ and on my machine it has similar performance with a non-recursive version. Note that understanding [ ... ] creates elements in the reverse order - so that they can be undone back at the end.

You can also write it all more beautifully using the syntax F # seq { .. } . You can completely eliminate the use of the @ operator, since it allows you to create individual elements with yield and make tail recursive calls with yield! :

 let rec indicesForStepSeq start blockSize maxSize = seq { match start with | i when i > maxSize -> () | _ -> for j in start .. ((min (start + blockSize) maxSize) - 1) do yield j yield! indicesForStepSeq (start + 2 * blockSize) blockSize maxSize } 

This is how I will write it. When you call it, you just need to add Seq.toList to evaluate the whole lazy sequence. The performance of this version is similar to the first.

EDIT With a fix from Daniel, the Seq version is actually a bit faster!

Answer 2

In F #, a list type is implemented as a separate list. Because of this, you get different performance for x @y and y @x if x and y have different lengths. This is why you see the difference in performance. (x @y) has an X.length runtime.

 // eg let x = [1;2;3;4] let y = [5] 

If you made x @y, then x (4 elements) will be copied to the new list, and its internal next pointer will be set to the existing list y. If you did y @x, then y (1 element) will be copied to the new list, and the next pointer will be set to the existing list x.

I would not use a higher order function for this. Instead, I would use a list.

 let indicesForStepTail start blockSize maxSize = [ for block in start .. (blockSize * 2) .. (maxSize - 1) do for i in block .. (block + blockSize - 1) do yield i ] 

Answer 3

It looks like an append list is a problem. Append is basically an O (N) operation to fit the size of the first argument. Having accumulated on the left, this operation takes O (N ^ 2) time.

As usual, this is done in the functional code, you need to copy the list in reverse order (by accumulating to the right), and then return the back link at the end.

In the first version, you avoid the problem of adding, but, as you point out, is not tail recursive.

In F #, perhaps the easiest way to solve this problem is through sequences. This is not a very functional view, but you can easily create an infinite sequence after your template and use Seq.take to get the elements you are interested in.