Pathological garbage collector behaviour

The F#.NET Journal just published an article about garbage collection:
"When performance is important in a garbage collected language such as F# it is useful to have some understanding of the costs of operations that the garbage collector performs. This article provides an introduction to garbage collection, an overview of the processes performed by generational garbage collectors for multithreaded programs and goes on to examine some F# programs that deliberately exhibit pathological behaviour and presents workarounds that alleviate or even eliminate the costs associated with garbage collection on .NET..."

To read this article and more, subscribe to The F#.NET Journal today!

Purely functional hash tries

The F#.NET Journal just published an article about purely functional data structures:
"Purely functional data structures such as the Set and Map collections provided by the F# standard library have many advantages over traditional imperative collections, particularly clarity due to the absence of mutation, but their performance can be much worse. Benchmarks have shown the F# Set and Map running up to 40× slower than the imperative HashSet and Dictionary collections provided by .NET. This article describes the design and implementation of a hash trie implementation of a set that is up to 7× faster to construct and up to 4.5× faster to search than the F# set..."

To read this article and more, subscribe to The F#.NET Journal today!

Taylor series expansion of cosine that is generic over number type

Taylor series expansion of cos(x) about x=0:

cosine(x) = 1 - x²/2! + x⁴/4! - x⁶/6! + ...

Let's start by writing a float-specific version in F#:

let cosine n x =
  let rec loop i q t c =
    if i=n then c else
      loop (i + 1) (q + 10 + 8*i) (-t * x * x / float q) (c + t)
  loop 0 2 1.0 0.0

For example, we can compute 1M terms of the expansion of x=0.1:

cosine 1000000 0.1

The best way to make this polymorphic in F# is to parameterize the function over the operators it uses and mark it as inline in order to remove the performance overhead of this parameterization:

let inline cosine zero one ofInt ( ~-. ) ( +. ) ( *. ) ( /. ) n x =
  let rec loop i q t c =
    if i=n then c else
      loop (i + 1) (q + 10 + 8*i) (-.t *. x *. x /. ofInt q) (c +. t)
  loop 0 2 one zero

Now we can compute 1M terms using float like this, which is just as fast as before:

cosine 0.0 1.0 float ( ~- ) (+) (*) (/) 1000000 0.1

But we can also do single-precision float:

cosine 0.0f 1.0f float32 ( ~- ) (+) (*) (/) 1000000 0.1f

And arbitrary-precision rational:

cosine 0N 1N BigNum.FromInt (~-) (+) (*) (/) 10 (1N / 10N)

And even symbolic:

type Expr =
  | Int of int
  | Var of string
  | Add of Expr * Expr
  | Mul of Expr * Expr
  | Pow of Expr * Expr

  static member (~-) f = Mul(Int -1, f)
  static member (+) (f, g) = Add(f, g)
  static member (*) (f, g) = Mul(f, g)
  static member (/) (f, g) = Mul(f, Pow(g, Int -1))

cosine (Int 0) (Int 1) Int (~-) (+) (*) (/) 3 (Var "x")

To make it faster, hoist the common subexpression -x*x out of loop.