How we made Haskell search strings as fast as Rust

About (1).

The exact versions they used are specified by the stack.yaml file.

In this case, see https://stackage.org/lts-13.10

Stack has a feature that lets you automatically added bounds to a hackage upload based on the stack.yaml. (However, I personally do not recommend using this feature, as those bounds usually end up being overly restrictive. Manually-written bounds are better.)

The graph looks a lot like GraphViz output. Not sure about the charts, however.

It's LaTeX, tikz, and pgfplots for the images. Complied with xelatex to pdf and pdf2svg to svg. The rest is custom HTML and CSS. We use the Hakyll static site generator.

As always, I will bitch about the colour of the text being grey (#333) instead of black. Hurts readability, doesn't improve design.

I particularly appreciate how the text in the diagrams matches the font (& font size) of the body text. Almost nobody does that and it looks great.

> Also kudos to the authors to use mean instead of average in the graphs.

What do you mean? "Mean" with no qualification usually denotes arithmetic average (or mean).

> even Python with a naive implementation is good enough. There is nothing naive about their implementation. 1) It uses C FFI (as many low level python functions do) 2) It uses a suboptimal but still not naive algo.

Just because it isnt identical in implementation to the other languages doesn't mean its much simpler. Its fast because enough people cared to make it that way - it wasn't by some accident

> Firstly, the program spends most of its time in the heavily-optimized str.find function, which is implemented in C.

I'm not going to outright call this "cheating", but most of the time, virtually unconditionally, when Python is fast it's because it isn't Python, it's C.

It definitely feels worth noting that Python is radically slower than other languages, and the main "tool" it provides for improving performance is to rely on another language entirely.

> Also kudos to the authors to use mean instead of average in the graphs.

For benchmarks much better option would be geometric mean. Because the relation of the results values not the difference.

https://dl.acm.org/citation.cfm?id=5673

That is a fragile benchmark. For simple scripts where you rely exclusively on python procedures that are written in C python is often very fast.

Once you start working on that data using procedures actually written I python performance is usually far from stellar.

I have had that happen to me many times. Back in the guile 2.0 days I tried porting some utils to python based on preliminary benchmarks that were often an order of magnitude faster than my guile ones, but when the logic was implemented the difference was gone. Then guile 2.2 (and now guile 3) happened and everything got magically faster, even though less and less of the runtime is written in C.

As I wrote elsewhere that depends on the string type used: https://www.reddit.com/r/haskell/comments/b0l93l/how_we_made...

I wondered about this and poked at the internals of ByteString (suitable for ffi) and Text. Turns out Text could allow ffi by changing a single function (newByteArray to newAlignedPinnedByteArray).

Presumably creating lots of small strings is a typical use case for Text so losing compacting gc hurts. ByteString on the other hand is more used with binary data and is designed for ffi use.

Nobody's perfect, but BurntSushi isn't someone who typically does things by half measures.

I recommend reading https://blog.burntsushi.net/ripgrep/

I've read masters theses that were significantly less thorough and well-researched.

There is definitely some room. As usual, it depends. I'm away from the computer, so I haven't had a chance to look and see if the OP's benchmarks are published. So it's hard for me to say anything specific at the moment.

In the literature, there are generally two different variants of Aho-Corasick. The traditional formulation follows failure transitions during search, which comes with overhead. In effect, it's an NFA since search can traverse through multiple states for each byte of input that it sees. The other variant is the "advanced" form, which is just effectively turning the NFA into a DFA by precomputing all of the failure transitions into a single table. This can be quite a bit faster depending on the workload, but obviously uses more memory and takes more time to build. My library supports the DFA version, but it had a bug (which has now been fixed) which prevented the OP from effectively benchmarking it.

The OP hints that some substantial number of samples use a very small number of patterns. Sometimes only one. In that case, it probably wouldn't be best to use Aho-Corasick at all. Instead, it should use an optimized single substring search algorithm, such as Two Way. Even for multiple patterns, if there aren't that many of them, it might be better to use Teddy from Hyperscan.

This article is fairly timely. I'm almost done a rewrite of my Aho-Corasick library. It will bring some small performance improvements (but more importantly a simpler API), and I hope to move the Teddy algorithm into it at some point.

As always, specific workloads can often have their performance improved quite a bit.

Let me start by saying that I am a big fan of BurntSushi’s work, and this post was by no means intended to detract from that. If anything, it set a high bar for us.

I don’t have much to add to BurntSushi’s reply. I studied the implementation briefly to take inspiration from when we decided to write our own, and there is no obvious low-hanging fruit. One small thing is that it uses a Vec of transitions per state. In Alfred–Margaret we pack all transition tables together in one array (with a separate array that maps state to start index), so it can use the cache more efficiently.

There are ways to do parallel automaton traversal with SIMD, but it only works for a very small number of states.

It's what Haskell's 'text' type uses internally. This stackoverflow question seems to discuss why that is the case:

https://stackoverflow.com/questions/23765903/why-is-text-utf...

> Because we use the Text type for strings in Haskell, which is an array of UTF-16 code units in native endianness, the benchmarks would take UTF-16 data as input.

Lazy data structures require allocation. GHC's lists use build/fold fusion to remove intermediate lists but that's basically just a less reliable way of converting to folds http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GH...

The other common fusion technique used in haskell is stream fusion which is very similar to the mutual-recursion-encoded-as-sum-type version in the blog post.

There is also indexing-based fusion which the Repa library uses. It allows more control over traversal order (think optimizing stencil codes) but requires regular arrays, e.g. no filtering.

There are some other research projects like specialized compiler passes via hermit but afaik nothing really production ready.

We only did this to fix the performance regression we observed after upgrading to GHC 8.6, but in hindsight I think it is cleaner anyway. With GHC 8.2 the list construction was eliminated, but the optimization turned out to be fragile.

It's really not a pity at all, considering that:

1. There is no write up of the Hyperscan algorithm of which you speak. I wrote up a part of Teddy, but I still don't understand the full algorithm. Hyperscan's code takes serious effort to understand. I spent days staring at Teddy and I still didn't get everything.

2. Aho-Corasick is reasonably simple to implement and does fairly decently for a large number of tasks.

3. Aho-Corasick is trivially portable.

I'm not that versed in Haskell myself, but is this really the case? I would think that expectations for low level optimization and general code are different.

Though, I suppose you could then say that if the rules are different for low level optimization, they may as well have imported an external library written in Rust.

The thesis of laziness by default isn't "everything should be lazy", just that there's some benefit to having strictness be something you add as necessary - maybe that it's easier to add strictness to something lazy than add laziness to something strict, that it gives you more abstraction power, or maybe increases surface area for optimizations.

Similarly, the existence of generators and zero-argument functions in Python doesn't undermine the idea that strictness by default could have benefits.

I don't think that's true at all. The goal here was to make it as fast as rust (which basically compiles down to 'straight' native code by default). Haskell, while also compiled, kind of runs on a virtual machine (the STG). It should be expected that a language with a different execution model will need some work to fit another one. Of course, one would expect the same work if you were trying to make rust run as fast as Haskell on a processor designed to execute STG expressions (of which there are none, but there could be, like the lisp machines of the past).

Either way, optimization in any language often requires annotations. The main benefit of Haskell though is still equational reasoning, which this does not obviate. You can get rid of all the annotations and your code will still run, be correct, and can be reasoned about

No one says "Haskell is great because it's fast". They say variants of "Haskell is great because it offers ultra-high-level abstraction, mathematically precise data types, static type-checking and inference, and still giving you the freedom to write nasty low-level preprocesser line noise when you need to be as fast as C"

The inline/noinline annotations on the inner functions we only had to add for GHC 8.6 though; on GHC 8.2 it was fast without these. (That turned out to be a downside, relying on a long chain of optimizations is fragile.)