Phil Trelford's Array
POKE 36879, 255

Seq vs Streams

November 17, 2014 23:22 by phil

Last week Gian Ntzik gave a great talk at the F#unctional Londoners meetup on the Nessos Streams library. It’s a lightweight F#/C# library for efficient functional-style pipelines on streams of data.

The main difference between LINQ/Seq and Streams is that LINQ is about composing external iterators (Enumerable/Enumerator) and Streams is based on the continuation-passing-style composition of internal iterators, which makes optimisations such as loop fusion easier.

The slides (using FsReveal) and samples are available on Gian’s github repository.

Simple Streams

Gian started the session by live coding a simple implementation of streams in about 20 minutes:

type Stream<'T> = ('T -> unit) -> unit

let inline ofArray (source: 'T[]) : Stream<'T> =
   fun k ->
      let mutable i = 0
      while i < source.Length do
            k source.[i]
            i <- i + 1          

let inline filter (predicate: 'T -> bool) (stream: Stream<'T>) : Stream<'T> =
   fun k -> stream (fun value -> if predicate value then k value)

let inline map (mapF: 'T -> 'U) (stream: Stream<'T>) : Stream<'U> =
   fun k -> stream (fun v -> k (mapF v))

let inline iter (iterF: 'T -> unit) (stream: Stream<'T>) : unit =
   stream (fun v -> iterF v)

let inline toArray (stream: Stream<'T>) : 'T [] =
   let acc = new List<'T>()
   stream |> iter (fun v -> acc.Add(v))
   acc.ToArray()

let inline fold (foldF:'State->'T->'State) (state:'State) (stream:Stream<'T>) =
   let acc = ref state
   stream (fun v -> acc := foldF !acc v)
   !acc

let inline reduce (reducer: ^T -> ^T -> ^T) (stream: Stream< ^T >) : ^T
      when ^T : (static member Zero : ^T) =
   fold (fun s v -> reducer s v) LanguagePrimitives.GenericZero stream

let inline sum (stream : Stream< ^T>) : ^T
      when ^T : (static member Zero : ^T)
      and ^T : (static member (+) : ^T * ^T -> ^T) =
   fold (+) LanguagePrimitives.GenericZero stream

and as you can see only about 40 lines of code.

Sequential Performance

Just with this simple implementation, Gian was able to demonstrate a significant performance improvement over F#’s built-in Seq module for a simple pipeline:

#time // Turns on timing in F# Interactive

let data = [|1L..1000000L|]

let seqValue = 
   data
   |> Seq.filter (fun x -> x%2L = 0L)
   |> Seq.map (fun x -> x * x)
   |> Seq.sum
// Real: 00:00:00.252, CPU: 00:00:00.234, GC gen0: 0, gen1: 0, gen2: 0

let streamValue =
   data
   |> Stream.ofArray
   |> Stream.filter (fun x -> x%2L = 0L)
   |> Stream.map (fun x -> x * x)
   |> Stream.sum
// Real: 00:00:00.119, CPU: 00:00:00.125, GC gen0: 0, gen1: 0, gen2: 0

Note for operations over arrays, the F# Array module would be more appropriate choice and is slightly faster:

let arrayValue =
   data
   |> Array.filter (fun x -> x%2L = 0L)
   |> Array.map (fun x -> x * x)
   |> Array.sum
// Real: 00:00:00.094, CPU: 00:00:00.093, GC gen0: 0, gen1: 0, gen2: 0

Also LINQ does quite well here as it has a specialized overloads including one for summing over int64 values:

open System.Linq

let linqValue =   
   data
      .Where(fun x -> x%2L = 0L)
      .Select(fun x -> x * x)
      .Sum()
// Real: 00:00:00.058, CPU: 00:00:00.062, GC gen0: 0, gen1: 0, gen2: 0

However with F# Interactive running in 64-bit mode Streams take back the advantage (thanks to Nick Palladinos for the tip):

let streamValue =
   data
   |> Stream.ofArray
   |> Stream.filter (fun x -> x%2L = 0L)
   |> Stream.map (fun x -> x * x)
   |> Stream.sum
// Real: 00:00:00.033, CPU: 00:00:00.031, GC gen0: 0, gen1: 0, gen2: 0

Looks like the 64-bit JIT is doing some black magic there.

Parallel Performance

Switching to the full Nessos Streams library, there’s support for parallel streams via the ParStream module:

let parsStreamValue =
   data
   |> ParStream.ofArray
   |> ParStream.filter (fun x -> x%2L = 0L)
   |> ParStream.map (fun x -> x + 1L)
   |> ParStream.sum
// Real: 00:00:00.069, CPU: 00:00:00.187, GC gen0: 0, gen1: 0, gen2: 0

which demonstrates a good performance increase with little effort.

For larger computes Nessos Streams supports cloud based parallel operations against Azure.

Overall Nessos Streams looks like a good alternative to the Seq module for functional pipelines.

Nessos LinqOptimzer

For further optimization Gian recommended the Nessos LinqOptimizer:

An automatic query optimizer-compiler for Sequential and Parallel LINQ. LinqOptimizer compiles declarative LINQ queries into fast loop-based imperative code. The compiled code has fewer virtual calls and heap allocations, better data locality and speedups of up to 15x

The benchmarks are impressive:

cs-ssq

Reactive Extensions (Rx)

One of the questions in the talk and on twitter later was, given Rx is also a push model, how does the performance compare:


Clearly the Nessos Streams library and Rx have different goals (data processing vs event processing), but I thought it would be interesting to compare them all the same:

open System.Reactive.Linq

let rxValue =
   data
      .ToObservable()
      .Where(fun x -> x%2L = 0L)
      .Select(fun x -> x * x)
      .Sum()      
      .ToEnumerable()
      |> Seq.head
// Real: 00:00:02.895, CPU: 00:00:02.843, GC gen0: 120, gen1: 0, gen2: 0

let streamValue =
   data
   |> Stream.ofArray
   |> Stream.filter (fun x -> x%2L = 0L)
   |> Stream.map (fun x -> x * x)
   |> Stream.sum
// Real: 00:00:00.130, CPU: 00:00:00.109, GC gen0: 0, gen1: 0, gen2: 0

In this naive comparison you can see Nessos Streams is roughly 20 times faster than Rx.

Observable module

F# also has a built-in Observable module for operations over IObservable<T> (support for operations over events was added to F# back in 2006). Based on the claims on Rx performance made by Matt Podwysocki I was curious to see how it stacked up:

let obsValue =
   data
   |> Observable.ofSeq
   |> Observable.filter (fun x -> x%2L = 0L)
   |> Observable.map (fun x -> x * x)
   |> Observable.sum
   |> Observable.first
// Real: 00:00:00.479, CPU: 00:00:00.468, GC gen0: 18, gen1: 0, gen2: 0

As you can see Observable module comes off roughly 5 times faster.

Note: I had to add some simple combinators to make this work, you can see the full snippet here: http://fssnip.net/ow

Summary

Nessos Streams look like a promising direction for performance of functional pipelines, and for gaining raw imperative performance the Nessos LINQOptimizer is impressive.


Tags:
Categories: F# | C# | .Net
Actions: E-mail | Permalink | Comments (2) | Comment RSSRSS comment feed

Progressive F# Tutorials London 2014

November 10, 2014 13:36 by phil

Last week saw the fourth instalment of the annual Progressive F# Tutorials hosted at Skills Matter in London, with 8 sessions over 2 days and 2 tracks, to a full house.

2014 has been another exciting year in the F# community, with F# specific talks featuring heavily at major conferences, user groups popping up across the globe and F# sitting comfortably in the TIOBE top 20.

Day 1

Don Syme Jérémie Chassaing Scott Wlaschin
Mark Seemann Mathias Brandewinder F# Panel

Don Syme kicked off the day with a keynote on The F# Way To Reconciliation.

Then on the advanced track Jérémie Chassaing introduced CQRS with F# (code samples). Meanwhile on the beginner track Scott Wlaschin introduced DDD and F# (slides).


In the afternoon Mathias Brandewinder lead the advanced track with Treasures, Traps and F#. While on the beginner track Mark Seemann introduced Outside-In TDD with F#.

After some beer and pizza, we rounded off the day with a panel of experts including Kit Eason, Mathias Brandewinder, Ross McKinlay, Rich Minerich and Eirik Tsarpalis.

Day 2

Paddy, Don & JérémieRobert PickeringAndrea Magnorsky


F# DinnerMichael NewtonSean & Tomas

In the morning Robert Pickering and Robin Neatherway introduced Xamarin and Cross Platform Apps (code samples). While Don Syme and Tomas Petricek guided us through Calling and Extending the F# Compiler (code samples).

The afternoon saw Andrea Magnorsky take us through Gaming with F#. At the same time Michael Newton covered Metaprogramming in F#.


F# Hackathon

The fun continued into Saturday with a return to Skills Matter for an F# Hackathon. I brought along my 8yo Sean who, with a little help from Tomas Petricek, managed to compose some 3D men in F# interactive:

Functional 3D Men

let cylinder = 
   Fun.translate (0.0, 0.0, -0.2)
    ( Fun.color Color.DarkGray Fun.cylinder $
      Fun.translate (0.0, 0.0, 0.5) 
         (Fun.scale (2.0, 2.0, 0.2) 
            (Fun.color Color.DarkGray Fun.cylinder)) ) 

let head = 
   Fun.translate (0.0, 0.0, 0.8) 
      (Fun.scale (1.2, 1.2, 1.2) 
         (Fun.color Color.PeachPuff Fun.sphere))

let body = 
   Fun.cube
   |> Fun.color Color.DarkGoldenrod
   |> Fun.scale (0.5, 1.5, 3.0)
   |> Fun.translate (0.0, 0.0, 3.0) 
   
let arm = 
 ( ( Fun.cylinder
     |> Fun.color Color.DarkGoldenrod
     |> Fun.scale (0.3, 0.3, 2.0) ) $
   ( Fun.sphere
     |> Fun.translate (0.0, 0.0, 1.6)
     |> Fun.scale (0.5, 0.5, 0.5)
     |> Fun.color Color.PeachPuff ) )
   |> Fun.rotate (45.0, 0.0, 0.0)
   |> Fun.translate (0.0, -1.2, 2.3)

let arms = 
   arm $
   (Fun.rotate (0.0, 0.0, 180.0) arm)   

let feet = 
   Fun.cube
   |> Fun.scale (0.6, 0.6, 0.1)
   |> Fun.translate (0.0, 0.0, 7.0)

let leg = 
   Fun.cylinder
   |> Fun.color Color.DarkGoldenrod
   |> Fun.scale (0.5, 0.5, 3.0)
   |> Fun.translate (0.0, 0.0, 5.0)

let legs = 
  (Fun.translate (0.0, 0.3, 0.0) (leg $ feet)) $
  (Fun.translate (0.0, -0.3, 0.0) (leg $ feet))

let man = 
   head $
   cylinder $ 
   body $
   arms $
   legs 
  
[ for x in -10.0 .. 5.0 .. 10.0 do
   for y in -10.0 .. 5.0 .. 10.0 do
    yield Fun.translate (x, y, 0.0) man ]
|> Seq.reduce ($)

Meanwhile Anthony Brown managed to get F# code running on the PS Vita!

F# eXchange 2015

Want to join the dots of the F# landscape? Eager to hear from those driving innovation in F# or how F# is being used in various industries? Then join us for the F# exchange this April! Featuring a days of talks, demos and discussions, the F# eXchange will bring the world's top F# experts and practioners together with the amazing, passionate and fast growing F# community to learn and share skills, exchange ideas and meet like minded people. Don't miss it!

Book by December 31st for the early bird discount.


Tags:
Categories: F#
Actions: E-mail | Permalink | Comments (0) | Comment RSSRSS comment feed

Loewensberg re-animated

November 2, 2014 05:51 by phil

Verena Lowensburg was a Swiss painter and graphic designer, assocciated with the concrete art movement. I came across some of her work while searching for pieces by Richard Paul Lohse.

Again I’ve selected some pieces and attempted to draw them procedurally.

Spiral of circles and semi-circles

Based on Verena Loewensburg’s Unititled, 1953

Loewensberg step-by-step[4]

The piece was constructed from circles and semi-circles arranged around 5 concentric rectangles drawn from the inside-out. The lines of the rectangles are drawn in a specific order. The size of each circle seems only to be related to the size of it’s rectangle. If a placed circle would overlap an existing circle then it is drawn as a semi-circle

Shaded spiral

Again based on Verena Loewensburg’s Unititled, 1953

Loewensberg colors

Here I took the palette of another one of Verena’s works.

Four-colour Snake

Based on Verena Loewensburg’s Untitled, 1971

Loewensberg snake[4]

The original piece reminded me of snake video game.

Rotating Red Square

Based on Verena Loewensburg’s Untitled, 1967 

Loewensberg square rotating

This abstract piece was a rotated red square between blue and green squares.

Multi-coloured Concentric Circles

Based on Verena Loewensburg’s Untitled, 1972

Loewensberg circles shakeup

This piece is made up of overlapping concentric circles with the bottom set clipped with a rectangle. region. The shape and colour remind me a little of the Mozilla Firefox logo.

Method

Each image was procedurally generated using the Windows Forms graphics API inside an F# script. Typically a parameterized function is used to draw a specific frame to a bitmap which can be saved out to a an animated gif.

I guess you could think of each piece as a coding kata.

Scripts

Have fun!


Tags:
Categories: F#
Actions: E-mail | Permalink | Comments (0) | Comment RSSRSS comment feed