I’m the author of Makeup (a library for syntax highlighting of source code) and ExDocMakeup (a markdown processor that can be used with ExDoc that uses Makeup for syntax highlighting of code examples in the docs). It was a discussion around Makeup that initially prompted the development of NimbleParsec. Up until the most recent version, Makeup used to depend on the ExSpirit library by @OvermindDL1, which is much more flexible than NimbleParsec (as the discussion above shows), but much, much slower.

Using Benchee, I’ve prepared some benchmarks pitting the current version of Makeup (0.4.0) against the old version. I’ve gotten aproximately 10x speedups in both compilation time and runtime.

Here’s how to interpret the benchmarks below:

• Formatter performance: the part that takes up a list of tokens and converts it into an HTML fragment
• Lexer: the part that reads the raw source code and produces a list of tokens
• Lexer compilation time: this was done by invoking the Elixir compiler at runtime on the relevant file. This is a good proxy measure of the “real” compilation process (it’s pretty cool that’s so easy to compile code at runtime in Elixir - never us this in production, though!)

The most important number is the “Lexer + Formatter”, because that’s what the user will do most of the time. The benchmarks use a fake elixir file with about 250 lines written by the authors of the python library Pygments (which is similar to makeup) to demonstrate most of the syntax rules.

ExSpirit (old version):

Name                                                              ips        average  deviation         median         99th %
Formatter performance                                          124.40        8.04 ms    ±97.25%          15 ms          16 ms
Reading file from disk + Lexer + Formatter (end to end)          7.29      137.24 ms     ±7.99%         140 ms         172 ms
Lexer performance                                                7.18      139.33 ms     ±9.72%         140 ms         157 ms
Lexer + Formatter                                                6.83      146.43 ms    ±10.56%         141 ms         187 ms
Lexer compilation time                                         0.0355       28156 ms     ±0.00%       28156 ms       28156 ms

NimbleParsec (new version):

Name                                                              ips        average  deviation         median         99th %
Formatter performance                                          620.02        1.61 ms    ±32.96%        1.60 ms        3.20 ms
Lexer performance                                              108.31        9.23 ms     ±4.86%        9.40 ms        9.40 ms
Lexer + Formatter                                               94.72       10.56 ms    ±69.37%          15 ms          16 ms
Reading file from disk + Lexer + Formatter (end to end)         92.32       10.83 ms    ±66.61%          15 ms          16 ms
Lexer compilation time                                           0.26     3812.50 ms     ±0.01%     3812.50 ms        3813 ms

The secret to the Formatter’s performance improvements was to use iolists whenever possible instead of binaries after a suggestion by @josevalim I’d never have thought that the difference would be so great. It turns out that concatenating strings on the BEAM is very slow and requires lots of copying. @josevalim has been extremely helpful in suggesting improvements to the lexer, answering questions about NimbleParsec and giving useful tips on how to increase performance of my library.

Performance improvements in the lexer were mainly due to the use of NimbleParsec (and to an obsessive amount of microbenchmaking). The performance of my lexer is now pretty much the same as the performance of the Elixir formatter, which means there are probably very little gains to be had. Makeup is quite similar to the Elixir formatter in that it parses files and prints a beautified version of the output. It was also written by people which are probably smarter than me and which have some actual knowledge of the internals of the BEAM.

This newest version of Makeup itself is not yet ready for prime time. You can help by running it on examples of real elixir code, inspecting the output and submitting an issue with examples tha look wrong. Such examples can be included in the test suite, which sadly doesn’t cover all syntax rules yet (and may never cover all rule combinations, that’s why it’s important to run it on real code to spot issues).

All of this will be easier after I’ve updated the docs with more useful information.

From my experience in the last few days, NimbleParsec seems to be ready to be used for real projects. It’s the ideal option for those who need to parse context-free languages, and with some postprocessing steps it can be used to help parse some context-sensitive ones. I don’t believe I’ve found any bug while using it for Makeup.

Thanks to @josevalim for writing this great library and for all the help and to @OvermindDL1 who’s written ExSpirit, without which Makeup would have never been written. Although quite slow, ExSpirit is way faster than almost anything out there and is still the only Elixir parser library that supports parsing context-sensitive languages.

If you’ll only take away one thing from this post, take this: string concatenation is slow. Iolists are the secret sauce that will make your programs go fast. Don’t replace your code without benchmarking it, though. Performance on the BEAM is weird, don’t trust your instincts from other languages.

defmodule NimbleParsec do
  @moduledoc "README.md"
             |> File.read!()
             |> String.split("<!-- MDOC !-->")
             |> Enum.fetch!(1)

Where has this been my whole life?

+++

Yeah definitely should be outputting IOlists, even with ExSpirit. ^.^;

I’m really curious about when it will be able to parse context-sensitive languages, then it can fully replace ExSpirit and I can deprecate it (less stuff for me to manage/update, the better!).

Heh thanks, it was birthed because I needed it and nothing else out supported the features I needed. ^.^

I really want NimbleParsec to replace it, needs a few more features to be able to do that though.