Building even faster interpreters in Rust | Hacker News Reader

Building even faster interpreters in Rust

blog.cloudflare.com

45 pointsthesephist25 comments

So... just use regular expressions when working with regular expressions?

No, that SIMD is good for string matching and Rust regex crate (written by burntsushi for 'ripgrep') makes very good use of it and is thus a nice library for implementing quick matchers.

Thanks for the kind words, but note that it is actually the other way around! I wrote ripgrep for the regex engine. ;-) The initial version of ripgrep was just a kind of benchmarking tool that I used for the regex engine.

Results from the benchmarks game suggests the performance of the Regex crate and calling PCRE2 from Python are about indistinguishable. The results also suggest CloudFlare could have achieved a 35% improvement using boring technology like the crusty old GCC.

PL evangelism and marketing are fine, but these blogs about Rust that come out 2-3 times a week and always make it to the HN or Lobsters front page seem a bit contrived.

You may feel this, but I find these articles to be a high-light of HN. Optimization adventures are stuff I learn from and actually use. That it's in Rust makes sense as it does offer new ways to do things (in this particular article, the Rust aspect wasn't particular important, but it's a follow up to one where it was).

C and C++ articles are ignored, though, which is where most high-performance work is done. This isn't an optimization article that incidentally mentions Rust. It's a Rust-evangelism article that incidentally mentions optimization. HN has been a dumping ground for Rust content marketers for almost a decade now.

C and C++ articles are obviously not ignored. You might be running into the notice-dislike bias (https://hn.algolia.com/?dateRange=all&page=0&prefix=true&sor...), which leads people to overgeneralize about this kind of thing.

https://hn.algolia.com/?dateRange=all&page=0&prefix=true&sor...

Please see my reply to you downthread: https://news.ycombinator.com/item?id=24601088. You've broken the site guidelines badly and normally we'd be banning an account for doing this.

> C and C++ articles are ignored

I don't see many such articles on HN, but is that because they are ignored, or because there aren't many submitted?

> This isn't an optimization article that incidentally mentions Rust. It's a Rust-evangelism article that incidentally mentions optimization

I'm not sure we read the same article - I don't use Rust, but I followed along with the article just fine. It seemed to me much more about SIMD and string matching algorithms

HN articles that show up are the ones that got the most votes so it stands to reason it what people wants to read.

I'm sure that I'm not surprising you when I say that there are members of the Rust community, paid and otherwise, who brigade forums, like this one. You probably know a few by name.

I don't think "the people have spoken, and they want Rust!" I think you have a small number of very obsessive people who treat a programming language's popularity of all things as a crusade. JetBrains publishes the data from their developer surveys, and you can see the last one that very few people use Rust at all, and of those, very few, less than 1 in 8, have ever used it for actual work. If you look at surveys from previous years, you can see very little user retention. Why does nobody keep using the most-loved lang for more than a year?

Because it's just a sham, like how a decade ago everyone was 'learning' Haskell and writing blogs about Monads and how FP was the secret sauce for their next-big-thing. It's exhausting. We've had non-stop but-what-about-Rust since, what, 2011?

This horse is dead.

You've broken the site guidelines badly with this and other comments. That's a bannable offense on HN. I'm not going to ban you, because you've also posted quite good comments, but if you do this again, we will have to. Please review https://news.ycombinator.com/newsguidelines.html and stick to the rules.

Rust is at the top of the hype cycle heap these days. The programming language in that position always gets undue attention on internet forums. HN has seen it happen more than once over the years, including with Go, Node, and so on. Forum readers like to read about shiny newness, and it's natural to they want to read about languages they don't use yet, especially when they find them exciting and want to believe the "this time is different" story.

That bias may be a problem in the software world (I personally think it is), but it's not evidence of brigading, and you can't make up stories about that here, and particularly not attack others personally about it (https://news.ycombinator.com/item?id=24596207). If you think you're seeing actual evidence of manipulation, please follow the guidelines and email hn@ycombinator.com so we can investigate.

You probably could get same optimization in FORTRAN, but so what?

Rust is just a more modern, better and more approachable programming language than C and C++, and people care about it more and prefer to get their little system programming lessons in it.

Using the benchmark game to judge the performance of regex engines for a specific task for anything other than what the benchmark game is doing is a serious mistake.

And I say this as the person who wrote the only non-PCRE regex engine that appears in the top 20 entries of the regex-redux benchmark.

Besides, if people want to use PCRE2 from Rust, then it's as simple as using a crate (which I also wrote): https://docs.rs/pcre2

This is the brigading I'm talking about. Every thread anywhere on HN or lobsters where anyone gives Rust anything but blind praise, you , Klabnik, Skade, Matklad or one of the entourage write walls of text like lunatics.

Let it go. Even by your own reasoning, reading anything into the Cloudfront article would be a mistake, right? Yet, here it is on the front page. Dutifully upvoted.

Personal attacks will get you banned here. No more of this, please, and please see https://news.ycombinator.com/item?id=24601088 also.

The "Two-way string-matching algorithm" gets a brief mention. I'm familiar with KMP and BM, and have implemented various others over the years, but I've never heard of this one. Anyone know what kind of situations you might choose two-way string matching over Boyer-Moore, for example?

Two-Way is quite old, but you're right that it is lesser known that BM and KMP. You'll find Two-Way implemented most commonly in environments where either allocation is undesirable or where you want as quick initialization as possible. Namely, Two-Way uses constant space, regardless of the size of your needle, where as BM generally requires space proportional to the size of your needle (and thus, allocation or some fixed upper limit on the needle size).

These kind of conditions occur in libc implementations where the library interfaces don't provide separate initialization and search phases; all you get is a substring search routine. (The interface is limiting; you can never avoid the overhead of constructing the searcher for a particular needle, even if you are using the same needle to search many different short haystacks.)

Whether one is better than the other is hard to say. Substring search routines these days are dominated by vector instructions and how effective you use them in the common cases.

KMP is basically never used. I can't think of a single place where it is used off the top of my head.

Word "Interpreter" and "fast" don't belong together in my brain :).

Probably why I love native binaries.

I had the good fortune to have Ole Caprani as my 2nd year teacher at the university and he really drilled home the message that it's all the same the whole way down. The more you understand the whole stack, the more you realize that even the CPU is just an interpreter for it's own language (the ISA).

A sufficiently smart interpreter for a language can be faster than a native binary as the former has the freedom to adapt to dynamic conditions. This is the essential point of JITs. It beats ahead of time compilation when dynamic conditions do change but slowly enough to amortize the overhead of adapting to it.

Please show me just one example of such an interpreter. You chose the architecture and the operating system. I'll follow up with a C compiled native and see who's faster at doing the same thing.

Synthesis kernel by massalin comes to mind. not sure if there is a modern equivalent. pretty sure lisp systems like SBCL can do things like function specialization and loop unrolling at runtime but I haven't tried.

Try it and put GitHub link. For bench-marking purposes do a simple project of calculating first million prime numbers. I'll do the same in C using your chosen algorithm.

That's not a particularly good representative of real applications, but I'll be happy to do the study for you. Let me introduce you to my consulting fees.

There's nothing inherent that would make JIT interpreted languages slower than AOT compiled languages. In fact JITs can apply optimizations that are difficult to do AOT.

The only reason why interpreted languages are usually much slower is semantics of the language itself. And maybe JITing itself, but that tends to get amortized rather quickly.

I would argue that a runtime that makes heavy use of JIT compilation ceases to really be an "interpreter".

Reply on news.ycombinator.com