Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Impossible Optimization, and the Metaprogramming to Achieve It

verdagon.dev

Post reply on HN
Print view View original

21–28 of 28 posts

Re: The Impossible Optimization, and the Metaprogramming to Achieve It

#21

Post by aappleby »

I did something similar to this with C++ templates - it's Parsing Expression Grammar based, so not full regex, but enough for a lot of tasks:

  using sign      = Atoms;
  using digit     = Range;
  using onenine   = Range;
  using digits    = Some;
  using integer   = Seq>, Oneof, digit>>;
  using fraction  = Seq, digits>;
  using exponent  = Seq, Opt, digits>;
  using number    = Seq, Opt>;
and I've confirmed that it does all get inlined and optimized on -O3.

JSON parser example here - https://github.com/aappleby/matcheroni/blob/main/examples/js...

Re: The Impossible Optimization, and the Metaprogramming to Achieve It

#23

Post by jlokier »

convolvatron wrote: post #20
spectraldrift wrote: post #13

Having never heard of mojo before, I found this article fascinating. It provides a great example of how a toy regex parser works and an excellent explanation of why vanilla regex tends to be slow. It also presents a novel solution: compiling the regex into regular code, which can then be optimized by the compiler.

this is literally how 'lex' works. the one written in 1987 by Vern Paxson.

The original is 'lex', written in 1975 by Mike Lesk and Eric Schmidt.

Yes, that Eric Schmidt, CEO of Google.

1987 was the clone, 'flex' :-)

It did "compiling the regex into regular code, which can then be optimized by the compiler" before the C programming language as we know it was created. I think 'lex' was compiling regex to C before the C language even had 'struct' types, 'printf' or 'malloc'.

Re: The Impossible Optimization, and the Metaprogramming to Achieve It

#24

Post by cadamsdotcom »

Seems like an optimization that could be applied quite generally - as the author mentions at the end there’s lots of places this could be used.

The problem with applying this technique generally is the amount of code generated. But what if you can optimize that too.. perhaps share the common parts of the AST between the copies of the code that are generated, and overlay the changes with some datastructure.

Re: The Impossible Optimization, and the Metaprogramming to Achieve It

#26

Post by Panzerschrek »

For several years I have written a dedicated compiler for regular expressions. You basically pass a regular expression and get an object file containing optimized matching code. It uses LLVM library internally to perform optimizations and machine code generation. It should be generally faster to compile compared to solutions involving constexpr-based metaprogramming.

I am surprised, that there is no programming language doing similar stuff - having regular expressions which are compiled as native code instead of just using a runtime library like PCRE2. Implementing this in C++ or Rust should be relatively easy.

Re: The Impossible Optimization, and the Metaprogramming to Achieve It

#27

Post by lostmsu »

Panzerschrek wrote: post #26

For several years I have written a dedicated compiler for regular expressions. You basically pass a regular expression and get an object file containing optimized matching code. It uses LLVM library internally to perform optimizations and machine code generation. It should be generally faster to compile compared to solutions involving constexpr -based metaprogramming. I am surprised, that there is no programming lang…

.NET had this since 2.0 if not 1.0

Re: The Impossible Optimization, and the Metaprogramming to Achieve It

#28

Post by spectraldrift »

convolvatron wrote: post #20
spectraldrift wrote: post #13

Having never heard of mojo before, I found this article fascinating. It provides a great example of how a toy regex parser works and an excellent explanation of why vanilla regex tends to be slow. It also presents a novel solution: compiling the regex into regular code, which can then be optimized by the compiler.

this is literally how 'lex' works. the one written in 1987 by Vern Paxson.

So I'm only 40 years behind! It's amazing how early innovations like this seamlessly fade into the background and can be taken for granted by folks like myself.
Post reply on HN