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.
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.
Reading a bit closer, you seem to track how much work is being done in Horspool on each character comparison, and then fall back to the linear KMP if the work budget is exhausted.
This will first massively slow down the Horspool scan, and then once you have done all that work, you rescan it all from the start with KMP if it is doing too much.
One little fix might be to only add to the work counter and compare it outside of the main character comparison loop.
But it would be better to use the linear version of Hashchain. It also uses KMP to make it linear, but it is fully integrated and you would not need to track the work or restart scanning at all. And its a lot faster than Horspool anyway!
Not OP, but I went through this last week. I (ok, codex) optimized a hot path in some Java code from ~350ms to ~60ms, which made a substantial difference in "is this whole business going to work".
My Java profiling knowledge is... let's call it "antique". I was really not looking forward to ramping back up for this work. Turns out, I didn't have to do any of it. The LLM chose the tools (flight recorder) and even built a JMH (also new to me) harness to experiment with different algorithms.
About half of the optimizations were things that I would have figured out on my own; the other half were definitely "wow" moments.
The whole thing was done in a couple hours, with just a few back-and-forths. Sans AI, it would have taken a week, with nowhere near the same gain. I'm impressed.
"Figure out how to make this process fast" is really a perfect activity for LLMs. And the prompt doesn't really have to be much more sophisticated than that.
* Using spherical points instead of trig to calculate distance between two geo locations.
* Packing data to minimize memory bandwidth consumption. Converting arrays of objects to multiple arrays of their component parts I sort of expected; bitshifting to pack and unpack multiple values into a `long` I did not.
Maybe other people would find these obvious, but I don't usually have to optimize at this level. My mental model of the relative speed of some CPU operations was a little out of date.
JMH as the framework to write microbenchmarks. It takes care of dealing with JIT warmup, etc. It's the standard way to write rigorous Java microbenchmarks.
async-profiler (https://github.com/async-profiler/async-profiler) for profiling. Java has a problem where many profilers are based on safepoints, which are biased toward particular program points. async-profiler is not biased in this way.
Java Flight Recorder for memory allocation data.
One thing I've observed in all of this is that it's really useful to have expertise in the programming language and ecosystem you're writing in, otherwise it's all Greek to you and you can't really guide the agent to do the right thing. I have opinions about e.g. profilers and I can point the agent to one that I think is more accurate than other options.
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.
> What I’m wondering now is can we reliably evolve python and have codex act as an extremely unreliable transpiler to the rust.
Why you even start with Python at this point? Just write the Rust version straight up instead of porting things?
Personally I used to use dynamic languages for most things, because development and maintenance is so much faster and easier, particularly for larger projects (granted you know how to work with those sort of languages), but now when the LLM writes most of the code, I'm able to work as fast with Rust as with I used to be able to do with Clojure or other dynamic languages.
It's becoming increasingly evident this is not how things are going to shake out. Even without frontier models, running Qwen 3.8 27B has demonstrated for me and others a "good enough" competency at general programming. Additionally, large open weight models have proven themselves as viable alternatives and we're still in the early years of dedicated hardware
I'm not saying developing with LLMs is the same as network engineering. The point being that almost all professions have some point of failures, that sometimes when we work, that single point is broken, yet we need to continue working anyway. Same goes for every professional almost.
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.