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



Update 3 Dec 2017: Rust's regex crate updated and code cleanup, F# run on .NET Core 2.0:

F#


Rust


Rust version now performs 2x faster, F# is slower on case sensitive and faster on case insensitive on Core:

All results so far:


Case sensitive Case insensitive
F# 6,57 9,56
Scala 3,50 3,20
Rust 2,97 3,02
DMD 6,90
LDC 6,60
Elixir 56,00
Hakell 20,00
Nemerle 3,80 7,10
Nemerle PEG 4,10 4,20

I removed Elixir from the chart as it's a clear outsider and its results make the chart read harder:

Comments

Anonymous said…
To be fair, regular expressions are known to be a bit of a weak spot in Rust currently. Efforts are in progress to improve the implementation, but they're still a work in progress, performance-wise.
Anonymous said…
Nice post. Did you compile Rust code with optimizations (--release flag in cargo)?
Vasily said…
@V: yes, of course I ran it via `cargo run --release`. In debug mode it runs ~30 times slower (!), 177 seconds vs 6 seconds.
jneem said…
Could you make the full input file available? I'm trying to improve rust's regex performance, and it would be nice to have more benchmarks to analyze.
Vasily said…
it is here https://drive.google.com/open?id=0B8HLQUKik9VtUWlOaHJPdG0xbnM
Anonymous said…
It would be interesting to see memory usage..
Unknown said…
What compilation flags did you use for D?
Unknown said…
D supports a variant of stdio.readln that re-uses the buffer, what's the performance like if you change it to that?
Unknown said…
Answering my own question, for D using readln(buf) shaves half a second off the D time on my laptop.
Unknown said…
FYI, the Rust version also allocates a new string per line.
kozzi11 said…
My results:

D(LDC): 5.778s
D(GDC): 5.612s
D(DMD): 5.267s
scalac: 5.748s
rustc: 9.287s
Anonymous said…
I posted a faster version on the dlang forums, you can find it here if you want to give it a whirl:

https://paste.ee/p/Bb1Ns

you may need to alter the filename on line 10, you appear to be on Windows and I adjusted it for my Linux OS.

It runs twice as fast as the original ctRegex implementation in your blog post for me. The output is the same, feel free to verify.

Elapsed: 3187
~/regex 3.17s user 0.04s system 99% cpu 3.217 total

Elapsed: 6283
~/regex2 6.15s user 0.14s system 99% cpu 6.307 total


compiled with ldc -O3 -release -boundscheck=off -singleobj regex.d
dmd version is ~70% slower now
Bye.
raichoo said…
I took the liberty to modify the Haskell example to use ByteString instead of constantly packing
and unpacking Text. This now runs in about 5 seconds on my laptop. https://gist.github.com/raichoo/3ae8dd14699b1f731916
Unknown said…
FYI, running this on the latest Rust regex library (0.1.51) gives a 2-3x boost.
KubuS said…
I bet .NET is converting all strings to UPPER-CASE or lower-case before comparison instead of comparing strings on char/ASCII code level.
Elixir code should not be placed directly inside defmodule, when you don't want compile time execution. Besides, comparing a compile time of Elixir code with run times for other languages is unfair.
Besides, take a look at https://github.com/elixir-lang/flow for best practices of parallel computations in Elixir.
Vasily said…
I updated results on:

* the latest Rust compiler and regex crate
* F# 4.1 on .NET Core 2.0

Rust is not the leader, F# results is somewhat better.
Vasily said…
Typo, Rust is _now_ the leader.
rmouniak said…
Nice post, Thanks for sharing Get more update at
.Net Online Course
Janu said…
Thanks for sharing such informative guide on .Net technology. This post gives me detailed information about the .net technology. I am working as trainer in leading IT training academy offering Dot Net Training in Chennai and i use your guide









Dot Net Training in Chennai | Dot Net Training in anna nagar | Dot Net Training in omr | Dot Net Training in porur | Dot Net Training in tambaram | Dot Net Training in velachery

Cyberz Pc said…
Wow, that is appealing studying. i am glad i found this and were given to artifice in it. I preferred it loads. thanks for the colossal and precise data. Prezi Crack
Cyberz Pc said…
It changed into wondering if I may want to use this write-taking area regarding my supplementary website, notable thanks. Wifi Password Hacker
Jobi Johnson said…
This comment has been removed by the author.

Popular posts from this blog

Haskell: performance

STM: F# vs Haskell