Thursday, September 24, 2015

Regular expressions: Rust vs F# vs Scala

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.

Update 4 Jan 2016: Scala added:

Ok, it turns out that regex performance may depend on whether it's case sensitive or not. What's worse, I tested F# with case insensitive pattern, but Rust - for case sensitive. Anyway, as I've upgraded my machine recently (i5-750 => i7-4790K), I've rerun F# and Rust versions in both the regex modes and added Scala to the mix. First, case sensitive mode:
  • F# (F# 4.0, .NET 4.6.1) - 4.8 secs
  • Scala (2.11.7, Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_65) - 3.5 secs
  • Rust (1.7.0-nightly (bfb4212ee 2016-01-01) - 5.9 secs
Now, case insensitive:
  • F# (F# 4.0, .NET 4.6.1) - 15.5 secs
  • Scala (2.11.7, Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_65) - 3.2 secs
  • Rust (1.7.0-nightly (bfb4212ee 2016-01-01) - 6.1 secs

Although case sensitive patterns performs roughly the same on all the platforms, it's quite surprising that Rust is not the winner.

Scala is faster in case insensitive mode (?), Rust is slightly slower and now the question: what's wrong with .NET implementation?.. It performs more than 3 times slower that case sensitive and the others.

Update 4 Jan 2016: D added.

  • regex - 10.6 s (DMD), 7.8 s (LDC)
  • ctRegex! - 6.9 s (DMD), 6.6 s (LDC)

Update 6 Jan 2016: Elixir added:

It takes 56 seconds to finish.

Update 6 Jan 2016: Haskell added:

I takes 20 seconds.

Update 7 Jan 2016: Nemerle added:

It takes 3.8 seconds (case sensitive) and 7.1 seconds (case insensitive).

Update 8 Jan 2016: Nemerle PEG added:

It takes 4.1 seconds.

All results so far:

  Case sensitive Case insensitive
F# 4,80 15,50
Scala 3,50 3,20
Rust 5,90 6,10
DMD 6,90  
LDC 6,60  
Elixir 56,00  
Hakell 20,00  
Nemerle 3,80 7,10
Nemerle PEG 4,10 4,20