Saturday, January 10, 2015

Parallel reduce: Hopac, Asyncs, Tasks and Scala's Futures

Tuomas Hietanen posted a parallel reduce function that uses TPL Tasks. I found it interesting to compare performance of this function with analogues implemented using F# Asyncs, Hopac Jobs and Scala Futures.
The author uses noop long-running reduce function to show that it's really run in parallel. In this blog post we are benchmarking another aspect of the implementations: how much extra cost is introduced by a particular parallezation mechanism (library) itself.

We translate the original code almost as is to Tasks and Hopac:


And Scala's Futures:


The results (Core i5, 4 cores):

  • Sequential List.reduce: Real: 00:00:00.014, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0 
  • Tasks: Real: 00:00:01.790, CPU: 00:00:05.678, GC gen0: 36, gen1: 10, gen2: 1 
  • Hopac: Real: 00:00:00.514, CPU: 00:00:01.482, GC gen0: 27, gen1: 2, gen2: 1 
  • Asyncs: Real: 00:00:37.872, CPU: 00:01:48.405, GC gen0: 90, gen1: 29, gen2: 4
  • Scala Futures: 4.8 seconds

(Hopac - 3.4 times faster, Asyncs - 21.1 times slower, Scala - 1.8 times slower)

Hopac is ~3.5 times faster than TPL. What's wrong with Asyncs? I don't know. Maybe they are not intended for highly concurrent scenarios. Or my code may not be the most efficient. Any ideas, guys?

Let's test the leaders on larger arrays:


(Hopac is 3.37 times faster, Scala is 1.5 times slower)


(Hopac is 5.25 times faster, Scala is 1.05 times slower)

Wednesday, January 7, 2015

Fibonacci: Hopac vs Async vs TPL Tasks on .NET and Mono

Hopac claims that its Jobs are much more lightweight that F# Asyncs. There are many benchmarks on Hopac github repository, but I wanted to make a simple and straightforward benchmark and what could be simpler that parallel Fibonacci algorithm? :) (actually there's a more comprehensive  benchmark in the Hopac repository itself, see Fibonacci.fs)

Sequential Fibonacci function is usually defined as

So write a parallel version in Hopac where each step is performed in a Job and all these Jobs are (potentially) run in Parallel by Hopac's scheduler

An equivalent parallel algorithm written using F# Asyncs

...and using TPL Tasks

All three functions create *a lot* of parallel jobs/asyncs/tasks. For example, for calculating fib (34) they create ~14 million of jobs (this is why Fibonacci was chose for this test). To make them work efficiently we will use the sequential version of fib for small N, then switch to parallel version

Now we can run both of the function with different "level"s in order to find on which value the functions starts to perform good (x-axis: level, y-axis: time (ms),  blue line: the sequential function, orange line: hopac/async/tasks function):

Hopac
Async
Tasks


Hopac reaches performance equivalent to the sequential implementation at level = 9, Async - at level = 17 and Tasks at level = 11.

If we modify the code so we can count how many jobs/asyncs are created during the calculation


We get the following results (n = 42): 

* Sequential, Real: 00:00:01.849, CPU: 00:00:01.840, GC gen0: 0, gen1: 0, gen2: 0
* Hopac (level = 9) jobs: 28761996, Real: 00:00:01.700, CPU: 00:00:05.600, GC gen0: 89, gen1: 1, gen2: 0
* Async (level = 17) asyncs: 605898, Real: 00:00:01.515, CPU: 00:00:04.804, GC gen0: 4, gen1: 2, gen2: 0
* Tasks (level = 11) tasks: 5675789, Real: 00:00:01.813, CPU: 00:00:06.302, GC gen0: 18, gen1: 0, gen2: 0

So, Hopac was able to create and processed ~47x more jobs than Async and ~5x more jobs than Tasks. Hopac is impressive and F# Asyncs are frustrating.  

PS: Rewriting the async version without async computation explicit expression, like this

does not improve performance at all. 

Running on Mono (Ubuntu 14.10 x64, mono 3.10)

* Sequential, Real: 00:00:02.637, CPU: 00:00:02.636, GC gen0: 0, gen1: 0
* Hopac (level = 17) jobs: 629133Real: 00:00:02.447, CPU: 00:00:06.106, GC gen0: 26, gen1: 1
* Async (level = 21) asyncs: 92375Real: 00:00:02.845, CPU: 00:00:05.590, GC gen0: 86, gen1: 3
* Tasks (level = 33) tasks: 143Real: 00:00:14.111, CPU: 00:00:03.782, GC gen0: 0, gen1: 0

Hopac can handle ~6.8x more jobs than F# Async. I'm not sure if F# asyncs performs very well on Mono or it's because everything works extremely slowly there. What about TPL, it's obviously broken on Mono (official Hopac Fibonacci benchmark does not even run TPL version on mono: Fibonacci.fs#L233).

Update 10.09.2017 - use BenchmarkDotNet


n = 30, level = 15

 Method |     Mean |     Error |    StdDev |
------- |---------:|----------:|----------:|
    Fib | 8.208 ms | 0.0432 ms | 0.0383 ms |
   HFib | 1.860 ms | 0.0045 ms | 0.0042 ms |
   AFib | 4.921 ms | 0.0330 ms | 0.0292 ms |
   TFib | 2.229 ms | 0.0184 ms | 0.0172 ms |

n = 20, level = 0

 Method |         Mean |      Error |       StdDev |
------- |-------------:|-----------:|-------------:|
    Fib |     68.21 us |   1.258 us |     1.177 us |
   HFib |    356.21 us |   7.180 us |    11.595 us |
   AFib | 31,815.44 us | 636.249 us | 1,524.413 us |
   TFib |  1,623.25 us |  32.206 us |    33.073 us |