Performance tuning in F# scripts / F# interactive

Question

I need to convert an arbitrary integer (that is, bigint) into its digits, so I can access them by index.

I found myself wo(a)ndering, though, between two possible implementations of the algorithm:

open System

let toDigits (x:bigint) =
    x.ToString() 
    |> Seq.map (fun c -> (int c) - (int '0'))
    |> Seq.toArray

let toDigits' (x:bigint) =
    seq {
        let x' = ref x
        while !x' <> 0I do
            yield (int (!x' % 10I))
            x' := !x' / 10I
    } |> Seq.toArray |> Seq.rev

Which one is fastest I mumbled? To help me answer the question, I devised a simple profile method

let profile f times = 
    let x = ref 0
    while !x < times do
        incr x
        f (bigint !x) |> ignore

that when conflated with F# Interactive's #time yielded the following output:

> profile toDigits 10000000;;
Real: 00:00:11.609, CPU: 00:00:11.606, GC gen0: 825, gen1: 1, gen2: 0
val it : unit = ()
> profile toDigits' 10000000;;
Real: 00:00:28.891, CPU: 00:00:28.844, GC gen0: 1639, gen1: 3, gen2: 0
val it : unit = ()

This clearly showed toDigit's superiority. I'd like to know why, though, so I'm asking my fellow F# overflowers what should I do from this point on.

In a typical Java program I'd just fire up a profiler (jvisualvm, for instance) and have it tell me which were the hot methods in some kind of CPU Sampling view. I guess this would work exactly the same way were I developing with .fs files in a regular project. As I'm in F# Interactive I'm a bit lost. Should I attach the .NET profiler (in this case, ANTS Memory Profiler) to F# Interactive? Is there any special workflow for this kind of software development?

Answer 1

In a typical Java program I'd just fire up a profiler (jvisualvm, for instance) and have it tell me which were the hot methods in some kind of CPU Sampling view. I guess this would work exactly the same way were I developing with .fs files in a regular project. As I'm in F# Interactive I'm a bit lost.

Using fsx files and F# Interactive doesn't mean that you should abandon compiling projects completely. I would change Build Action in File Properties to Compile in order to compile fsx files directly. We need to use conditional compilation at some places e.g.

#if INTERACTIVE
#time "on";;
#endif

The advantages of compiling the code are:

• You can use Visual Studio profilers to get statistics about hot spots in programs.
• You can decompile programs using ILSpy. Sometimes ILs or even equivalent C# code can give you insights on how the programs behave.

As the code evolves, you can consider moving core functions to fs files and keep quick profiling functions in fsx files.

Back to your example, an improvement of toDigits' is to avoid using references:

let toDigits'' (x:bigint) =
    let rec loop x acc =
        if x <> 0I then
            loop (x/10I) (int(x%10I)::acc)
        else acc
    loop x [] |> List.toArray

Results show that toDigits'' is 1.5x faster than toDigits' and 1.5x slower than toDigits.

It's hard to beat toDigit since it doesn't use any arithmetic operations on bigint. One obvious drawback of toDigit is that it gives meaningless results on negative bigints.

Answer 2

Perhaps this is not the answer you were looking for, but in the world of functional programming the choice of right means (algorithm, data structures, ...) for the task may bring much more benefits, than whatever thorough OOP-like micro-level code analysis a .NET profiler may give.

To illustrate my point, in your demo cases the choice to operate with sequences in both toDigits and toDigits' functions is hard to justify. If we choose instead to stay within array space, than equivalent functionality can be expressed as

let toDigits'' (x: bigint) =
    x.ToString().ToCharArray() |> Array.map (fun c -> int(c) - int('0'))

Turning now to FSI-provided profiling we can observe

> profile toDigits 10000000;;
Real: 00:00:13.020, CPU: 00:00:13.000, GC gen0: 1649, gen1: 2, gen2: 0

> profile toDigits'' 10000000;;
Real: 00:00:02.334, CPU: 00:00:02.343, GC gen0: 604, gen1: 1, gen2: 0

So, we got 5.6 times speedup just due to a better choice of data structures to operate upon and FSI profiler serves just as a confirmation of this fact.