5 ms·

Building even faster interpreters in Rust

45 points by thesephist 6y ago

jakearmitage 6y ago
So... just use regular expressions when working with regular expressions?
- dullgiulio 6y ago
  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.
  - sk2020 6y ago
    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.
    - FullyFunctional 6y ago
      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).
      - sk2020 6y ago
        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.
        FullyFunctional 6y ago
        HN articles that show up are the ones that got the most votes so it stands to reason it what people wants to read.
        sk2020 6y ago
        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.
        dang 6y ago
        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 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 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.
    - dpc_pw 6y ago
      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.
    - burntsushi 6y ago
      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 https://docs.rs/pcre2
      - sk2020 6y ago
        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.
        dang 6y ago
        Personal attacks will get you banned here. No more of this, please, and please see https://news.ycombinator.com/item?id=24601088 https://news.ycombinator.com/item?id=24601088 also.
  - burntsushi 6y ago
    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.
unnouinceput 6y ago
Word "Interpreter" and "fast" don't belong together in my brain :). Probably why I love native binaries.
- FullyFunctional 6y ago
  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.
  - unnouinceput 6y ago
    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.
    - voldacar 6y ago
      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.
      - unnouinceput 6y ago
        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.
        FullyFunctional 6y ago
GordonS 6y ago
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?
- burntsushi 6y ago
  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.

45 points by thesephist 6y ago

jakearmitage 6y ago

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

dullgiulio 6y ago
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.
- sk2020 6y ago
  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.
  - FullyFunctional 6y ago
    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).
    - sk2020 6y ago
      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.
      - FullyFunctional 6y ago
        HN articles that show up are the ones that got the most votes so it stands to reason it what people wants to read.
        sk2020 6y ago
        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.
        dang 6y ago
        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 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 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.
  - dpc_pw 6y ago
    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.
  - burntsushi 6y ago
    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 https://docs.rs/pcre2
    - sk2020 6y ago
      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.
      - dang 6y ago
        Personal attacks will get you banned here. No more of this, please, and please see https://news.ycombinator.com/item?id=24601088 https://news.ycombinator.com/item?id=24601088 also.
- burntsushi 6y ago
  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.

unnouinceput 6y ago

Word "Interpreter" and "fast" don't belong together in my brain :). Probably why I love native binaries.

FullyFunctional 6y ago
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.
- unnouinceput 6y ago
  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.
  - voldacar 6y ago
    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.
    - unnouinceput 6y ago
      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.
      - FullyFunctional 6y ago

GordonS 6y ago

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?

burntsushi 6y ago
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.