Thursday, 7 May 2009

F# as a next-generation platform for high-performance interactive technical computing

We are now in the throws of writing a new book on F# called F# for Technical Computing that is due out in a few months. Amongst other things, we are generating diagrams for the book using our own F# for Visualization library and making extensive use of our F# for Numerics library and Microsoft's excellent Parallel Extensions to .NET Framework 3.5 June 2008 CTP in order to build a next-generation platform for high-performance interactive technical computing.

The following screenshot shows the real-time visualization of performance measurements over the array, list and set data structure implementations provided with the F# September 2008 CTP:



There are several interesting aspects to this F# program:

  • Individual benchmarks for a given data structure are executed in parallel in order to obtain results faster without artificially degrading the measurements for other data structures via GC load.
  • The parallelism is so effective that 90% CPU usage is sustained across all 8 cores.
  • Parallel threads update the visualizations concurrently in real time safe in the knowledge that F# for Visualization handles all thread-related issues automatically and efficiently.
  • The randomized algorithms in the benchmarks are fuelled by the high-performance Mersenne Twister implementation in our F# for Numerics library.
  • The entire program is under 80 lines of code.
  • The resulting high-fidelity diagrams are ideal for inclusion in quality printed literature such as our full-color books.

Here is the entire source code:

open FlyingFrog
open FlyingFrog.Graphics
open FlyingFrog.Graphics.Typeset
let log2 x =
log x / log 2.0
let plot_mem =
Plot([], (0., 20.), (-25., 0.0),
Labels=(Char 'n', Sub(Char 't', Text "mem")))
let plot_mem_rel =
Plot([], (0., 20.), (0., 20.0),
Labels=(Char 'n', Fraction(Sub(Char 't', Text "set"), Sub(Char 't', Text "array"))))
let plot_iter =
Plot([], (0., 20.), (-30., -20.0),
Labels=(Char 'n', Sub(Char 't', Text "iter")))
let plot_foldl =
Plot([], (0., 20.), (-30., -20.0),
Labels=(Char 'n', Sub(Char 't', Text "foldl")))
let plot_foldr =
Plot([], (0., 20.), (-30., -20.0),
Labels=(Char 'n', Sub(Char 't', Text "foldr")))
let tss =
[for plot in 1 .. 4 ->
[for i in 1 .. 3 ->
[for i in 0 .. 101 -> float i, infinity]]]
let iters = 4001
let inline time f n m =
let rand = Random.MersenneTwister()
let t = System.Diagnostics.Stopwatch.StartNew()
let mutable j = 0
while t.ElapsedMilliseconds < 100L do
for k=0 to j do
f (abs(rand.int()) % n) m
j <- j + 1 float t.ElapsedMilliseconds / 1e3 / float j
let inline run d f mem iter foldl foldr =
System.Threading.Parallel.For(0, iters, fun i' ->
let i = iters * i' % 101
let n = 2. ** (float i / 100. * 20.) > int
let m = f n
let t' = time mem n m > log2
if snd tss.[0].[d].[i] > t' then
tss.[0].[d].[i] <- log2(float n), t'
for f, tss in [iter, tss.[1]; foldl, tss.[2]; foldr, tss.[3]] do
let t' = (time f n m / float n) > log2
if snd tss.[d].[i] > t' then
tss.[d].[i] <- log2(float n), t'
if i' % 100 = 0 then
plot_mem.Data <- [for ts in tss.[0] -> Data ts]
plot_mem_rel.Data <-
[Data(Array.map2 (fun (i, ts) (_, ta) -> i, 2. ** ts / 2. ** ta)
tss.[0].[0] tss.[0].[2])]
plot_iter.Data <- [for ts in tss.[1] -> Data ts]
plot_foldl.Data <- [for ts in tss.[2] -> Data ts]
plot_foldr.Data <- [for ts in tss.[3] -> Data ts]
)
let inline array_mem x (a: _ array) =
let rec aux i =
i < Array.length a && (a.[i] = x aux(i+1))
aux 0
do
run 2 (fun n -> Array.init n (fun i -> float i))
(fun n m -> ignore(array_mem (float n) m))
(fun n m -> Array.iter ignore m)
(fun n m -> Array.fold_left ( + ) 0.0 m > ignore)
(fun n m -> Array.fold_right ( + ) m 0.0 > ignore)
run 0 (fun n -> set (seq {for i in 0 .. n-1 -> float i}))
(fun n m -> ignore(Set.mem (float n) m))
(fun n m -> Set.iter ignore m)
(fun n m -> Set.fold_left ( + ) 0.0 m > ignore)
(fun n m -> Set.fold_right ( + ) m 0.0 > ignore)
run 1 (fun n -> [for i in 0 .. n-1 -> float i])
(fun n m -> ignore(list_mem (float n) m))
(fun n m -> List.iter ignore m)
(fun n m -> List.fold_left ( + ) 0.0 m > ignore)
(fun n m -> List.fold_right ( + ) m 0.0 > ignore)
Run()
 

1 comment:

Art said...

Yes, a breakthrough.

Congratulations.