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)

Comments

Thorium said…
This comment has been removed by the author.
January 13, 2015 at 4:15 PM
Thorium said…
.NET Tasks and Async are more for IO-bound operations than for CPU-bound; for concurrency rather than parallelism. So maybe it is not the fastest thing, while it is quite easy. If you open async-tasks dll method with ILDASM / ILSpy / Reflector, you notice that it will cause some overhead.

For high-parallelism use e.g. Array.Parallel.
January 13, 2015 at 5:03 PM
Thorium said…
Hmm... With thread-blocking Sleep(30) in the aggregate function I tried to simulate that what if your combinator is more complex than just (+)
E.g. for array with just 5000 items:

Array.reduce (fun c -> fun x -> System.Threading.Thread.Sleep(30);x+c) a
Real: 00:02:36.232

reduceParallelTasks (fun c -> fun x -> System.Threading.Thread.Sleep(30);x+c) a
Real: 00:00:06.730

reduceParallelAsync (fun c -> fun x -> System.Threading.Thread.Sleep(30);x+c) a
Real: 00:00:05.361

reduceParallelHopac (fun c -> fun x -> System.Threading.Thread.Sleep(30);x+c) a
Real: 00:00:20.032
January 13, 2015 at 7:04 PM
Unknown said…
The main reason for the existence of the Job monad is to make it possible to not block a native thread. So what your test does is that explicitly does the one thing, blocks the thread running the job, that you should not do.
January 18, 2015 at 5:42 AM
Vasily said…
Try reduceParallelHopac (fun c -> fun x -> Timer.Global.timeOutMillis 30;x+c) a
January 19, 2015 at 4:33 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

STM: F# vs Haskell

STM is a very nice parallel programming model used intensively in Haskell and Clojure. There's a F# implementation which can be found in FSharpx library. Today I'm going to test performance of both the Haskell and the F# STMs. The test is very simple - read a couple TVars, check their equality, then write them back incremented by 1, repeat a million times. First, the Haskell code: So, it took about 170 ms. OK, now F#: It took about 1,6 seconds which is an order of magnitude slower than the Haskell result. It's rather frustrating.
Read more