alt Hacker NewsI've been working on a similar agentically engineered regex project called SafeRE:
https://github.com/eaftan/safere
https://eaftan.github.io/safere-intro/
Mine is for Java and is intended to be production grade. The first goal is to guarantee linear-time behavior to prevent ReDoS attacks. My collaborator and I have recently been optimizing it to try to surpass native RE2 in performance.
It turns out optimizations are incredibly well suited for an agentic loop. You've got concrete acceptance criteria (must show a meaninging improvement on a benchmark case, must pass tests). The agent is really, really good at using tools like a profiler and disassembler, better than I am (and I've been doing this for 20 years). It also papers over things that would take me a while to learn, like how the in-incubation Vector (SIMD) API works in Java. I understand the concept but it would take me a while to understand Java's implementation. The agent can just read the docs and go.
The key is creating a good benchmark suite and ensuring the agent doesn't ship optimizations that are too narrow or too focused on the benchmark cases. You also need a really strong test suite to make sure you're not regressing correctness. SafeRE has billions of tests; a subset of several million run on CI, and the others run on-demand.
Replies
This sounds very interesting. Which JVM profiler do you use?
This, 100%. I’ve rewritten some hydrology code in rust using codex sol to first a) profile and create comprehensive tests of the python, b) create full benchmark suites, c) create full scientific benchmark suites, then d) port to rust using a few different techniques.
It works, it’s at least 5x faster, sometimes much more, and memory use is like 10x less and even less in cases where lots of map tiles are involved.
This shit rules.
What I’m wondering now is can we reliably evolve python and have codex act as an extremely unreliable transpiler to the rust.
Looks nice!
One little thing I spotted is you use Boyer Moore Horspool for fast literal search. This is actually not linear in the worst case, although it is almost always sublinear. Worst case would be a literal composed of the same character searching a text of the same character, where it becomes quadratic.
You can actually search strings with character classes using Horspool if you want to, and I have some enhancements to basic Horspool which could maybe help. My library, byteseek [1], implements these.
I also have a much faster algorithm, HashChain [2] which also has a guaranteed linear time version. This was published in the Symposium for Experimental Algorithmics in 2024.
[1] https://github.com/nishihatapalmer/byteseek
[2] https://github.com/nishihatapalmer/HashChain