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: 629133, Real: 00:00:02.447, CPU: 00:00:06.106, GC gen0: 26, gen1: 1
* Async (level = 21) asyncs: 92375, Real: 00:00:02.845, CPU: 00:00:05.590, GC gen0: 86, gen1: 3
* Tasks (level = 33) tasks: 143, Real: 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 |

Comments

Vincenzo Ciancia said…
Thanks a lot, I replicated your tests using a core i9-9900k from 2019, and dotnet 6.0, and it seems like nowadays TPL is quite faster than Hopac. Can you confirm these findings (indeed with server GC enabled)?

I prepared a complete file here:

https://github.com/vincenzoml/VoxLogicA/blob/gpu-new/testHopacVsTPL.fs
April 7, 2022 at 7:31 PM
Post a Comment

Popular posts from this blog

Haskell: performance

It turned out that it's not Haskell who was slow in my previous Fibonacci test. It was my lack of Haskell knowledge. Haskell has two integral types - Int, which has bounds -2147483648..2147483647 and Integer, which is unbounded. Both types implement Integral type class, so out fib function can be defined in terms of this type class: OK, now we can test performance of the function parametrizing it with the two concrete types. Integer first: We get our previous result ~15 seconds which is rather slow. Now test it with Int type: Whoa! The Int type is ~6 times faster than Integer! And with result of 2.8 seconds Haskell's took the third position in our small rating :) Current list (in seconds): C# - 1.26 F# - 1.38 Nemerle - 1.45 Haskell - 2.8 Clojure - 9 Erlang - 17 Ruby - 60 Python - 120
Read more

Regular expressions: Rust vs F# vs Scala

Image
Let's implement the following task: read first 10M lines from a text file of the following format: then find all lines containing Microsoft namespace in them, and format the type names the usual way, like "Microsoft.Win32.IAssemblyEnum". First, F#: Now Rust: After several launches the file was cached by the OS and both implementations became non IO-bound. F# one took 29 seconds and 31MB of RAM at peak; Rust - 11 seconds and 18MB. The Rust code is as twice as long as F# one, but it's handling all possible errors explicitly - no surprises at runtime at all. The F# code may throw some exceptions (who knows what kind of them? Nobody). It's possible to wrap all calls to .NET framework with `Choice.attempt (fun _ -> ...)`, then define custom Error types for regex related code, for IO one and a top-level one, and the code'd be even longer then Rust's, hard to read and it would still give no guarantee that we catch all possible exceptions. Up...
Read more

Hash maps: Rust, F#, D, Go, Scala

Image
Let's compare performance of hashmap implementation in Rust, .NET, D (LDC) and Go. Rust: F#: As you can see, Rust is slower at about 17% on insersions and at about 21% on lookups. Update As @GolDDranks suggested on Twitter , since Rust 1.7 it's possible to use custom hashers in HashMap. Let's try it: Yes, it's significantly faster: additions is only 5% slower than .NET implementation, and lookups are 32% *faster*! Great. Update: D added LDC x64 on windows It's very slow at insertions and quite fast on lookups. Update: Go added Update: Scala added Compared to Scala all the other languages looks equally fast :) What's worse, Scala loaded all four CPU cores at almost 100% during the test, while others used roughly single core. My guess is that JVM allocated so many objects (each Int is an object, BTW), that 3/4 of CPU time was spend for garbage collecting. However, I'm a Scala/JVM noob, so I just could write the whole b...
Read more