Live data from Hacker News

The Impossible Optimization, and the Metaprogramming to Achieve It

verdagon.dev

11–20 of 28 posts

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

#11
post #9

Gave me a smile to see the shout out to LISP in there. Reading this take on it, it feels like a JIT compiler could also accomplish a fair bit of this? I'm also reminded of the way a lot of older programs would generate tables during build time. I'm assuming that is still fairly common?

Yes, this is all straightforward with Lisp macros. Beyond that, you can call the compile function in Common Lisp and do all this at run time too.

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

#12

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

https://bur.gy/2022/05/27/what-makes-julia-delightful.html confirms your hunch

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

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

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

#14
post #3

Depending on the userbase of the site, simply checking for @gmail.com at the end, I'd bet, would result in a quick win, as well as restricting the username's alphabet to allowed Gmail characters. The other optimization I'd guess at would be to async/thread/process the checking before and after the @ symbol, so they can run in parallel (ish). Extra cpu time, but speed > CPU cycle count for this benchmark.

[Rehashing an old comment] In the math department, we had a Moodle the students in the first year of my university in Argentina. When we started like 15 years ago, the emails of the students and TA were evenly split in 30% Gmail, 30% Yahoo!, 30% Hotmail and 10% others (very aproxímate numbers). Now the students have like 80% Gmail, 10% Live/Outlook/Hotmail and 10% others/Yahoo. Some of the TA are much older, so perha…

Maybe I am old, but I like to keep as much communication as possible going through the university email. It just feels more official somehow.

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

#15
post #9

Gave me a smile to see the shout out to LISP in there. Reading this take on it, it feels like a JIT compiler could also accomplish a fair bit of this? I'm also reminded of the way a lot of older programs would generate tables during build time. I'm assuming that is still fairly common?

In fact, there's https://github.com/telekons/one-more-re-nightmare for CL.

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

#16
post #3

Depending on the userbase of the site, simply checking for @gmail.com at the end, I'd bet, would result in a quick win, as well as restricting the username's alphabet to allowed Gmail characters. The other optimization I'd guess at would be to async/thread/process the checking before and after the @ symbol, so they can run in parallel (ish). Extra cpu time, but speed > CPU cycle count for this benchmark.

[Rehashing an old comment] In the math department, we had a Moodle the students in the first year of my university in Argentina. When we started like 15 years ago, the emails of the students and TA were evenly split in 30% Gmail, 30% Yahoo!, 30% Hotmail and 10% others (very aproxímate numbers). Now the students have like 80% Gmail, 10% Live/Outlook/Hotmail and 10% others/Yahoo. Some of the TA are much older, so perha…

[deleted]

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

#17
post #3

Depending on the userbase of the site, simply checking for @gmail.com at the end, I'd bet, would result in a quick win, as well as restricting the username's alphabet to allowed Gmail characters. The other optimization I'd guess at would be to async/thread/process the checking before and after the @ symbol, so they can run in parallel (ish). Extra cpu time, but speed > CPU cycle count for this benchmark.

Tell us you used to work at Google, without telling us. "simply do X" is such a programmer fallacy at this point I'm surprised we don't have a catchy name for it yet, together with a XKCD for making the point extra clear.

Tell us you don't actually work with any Google engineers... blah blah blah

The trope is "At Google we..." and then casually mention "violating" the CAP theorum with Spanner or something.

It is simple, and I really do hope any first year CS student could extract a substring from a string. Have LLMs so atrophied our programming ability that extraction of a substring is considered evidence of a superior programmer?

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

#18

https://github.com/hanickadot/compile-time-regular-expressio...

FYI: This is a C++ template version of compile time regex class.

A 54:47 presentation at CppCon 2018 is worth more than a thousand words...

see https://www.youtube.com/watch?v=QM3W36COnE4

followup CppCon 2019 video at https://www.youtube.com/watch?v=8dKWdJzPwHw

As the above github repo mentions, more info at https://www.compile-time.re/

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

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

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

#20

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.
Post reply on HN