The Impossible Optimization, and the Metaprogramming to Achieve It

Join the discussion

• Hacker News
• To tie this specific example to a larger framework: In scala land, Tiark Rompf's Lightweight Modular Staging system handled this class of metaprogramming elegantly, and the 'modular' part included support of multiple compilation targets. The idea was that one could incrementally define/extend DSLs that produce an IR, optimizations in that IR, and code generation for chunks of DSLs. Distinctions about stage are straight-forward type-signature changes. The worked example in this post is very similar to one of the tutorials for that system: https://scala-lms.github.io/tutorials/regex.html

  Unfortunately, so far as I can tell:

  - LMS has not been updated for years and never moved to scala 3. https://github.com/TiarkRompf/virtualization-lms-core

  - LMS was written to also use "scala-virtualized" which is in a similar situation

  There's a small project to attempt to support it with virtualization implemented in scala 3 macros, but it's missing some components: https://github.com/metareflection/scala3-lms?tab=readme-ov-f...

  I'd love to see this fully working again.

  by abeppu
• 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.

  by Panzerschrek
• > can compilers really execute general code at compile-time?

  Cue the smug Lisp weenies laughing quietly in the background.

  by lisper
• > Mojo, D, Nim, and Zig can do it, and C++ as of C++20. There are likely some other languages that can do it, but these are the only ones that can truly run normal run-time code at compile time

  Pretty sure Julia can do it.

  by Archit3ch
• 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<'0', '9'>;
    using onenine   = Range<'1', '9'>;
    using digits    = Some<digit>;
    using integer   = Seq<Opt<Atom<'-'>>, Oneof<Seq<onenine, digits>, digit>>;
    using fraction  = Seq<Atom<'.'>, digits>;
    using exponent  = Seq<Atoms<'e', 'E'>, Opt<sign>, digits>;
    using number    = Seq<integer, Opt<fraction>, Opt<exponent>>;
  

  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...

  by aappleby
• > Eliminate redundant matrix operations (like two transposes next to each other)

  In 2016, I was trying to construct orthogonal irreducible matrix representations of various groups (“irreps”). The problem was that most of the papers describing how to construct these matrices used a recursive approach that depended on having already constructed the matrix elements of a lower dimensional irrep. Thus the irrep dimension n became quite an annoying parameter, and function calls were very slow because you had to construct the irrep for each new group element from the ground up on every single call.

  I ended up using Julia’s @generated functions to dynamically create new versions of the matrix construction code for each distinct value of n for each type of group. So essentially it would generate “unrolled” code on the fly and then use LLVM to compile that a single time, after which all successive calls for a specific group and irrep dimension were extremely fast. Was really quite cool. The only downside was that you couldn’t generate very high dimensional irreps because LLVM would begin to struggle with the sheer volume of code it needed to compile, but for my project at the time that wasn’t much of a concern.

  by Xcelerate
• The language here is Mojo, which the article seems to assume you know and doesn't say enough for you to deduce until half way through and after multiple code examples. I don't know how you're supposed to know this as even the blog it's on is mostly about Vale. From the intro I was expecting it to be about C++.
  by omnicognate