Journal · 2008
FIRE/J: Optimizing Regular Expression Searches with Generative Programming
Vassilios Karakoidas, Diomidis Spinellis
A regular expression engine for Java that compiles each expression into its own class file and runs it as JVM bytecode, instead of interpreting an automaton — fast enough, in the paper's benchmarks, to beat the C library.
- Published in
- Software: Practice and Experience, Vol. 38, No. 6, pp. 557--573, 2008
- Citations
- 17 on Google Scholar, read 5 September 2026 — 11 of 30 by count
- Cite as
- KD08
The idea
A regular expression has two phases: build an automaton, then run it over the input. Almost every engine runs the second phase by interpreting the automaton it built in memory. FIRE/J removes the interpreter. Each expression is translated into a tailor-made class file, compiled straight to JVM bytecodes and loaded; matching is then a run through generated code. The framing is generative programming — a regular expression is a domain-specific language, and the engine compiles it into the host language rather than interpreting it.
Contributions
- The techniques for eliminating run-time automaton interpretation by compiling the automaton, at run time, into a portable virtual-machine representation.
- An engine that stays portable across machine architectures — the output is bytecode, not native code — and POSIX-compatible.
- The observation that this approach, combined with the VM's own just-in-time compilation, can outrun the traditional C library. Compiling to a VM is not a compromise between portability and speed here; the two compilations compose.
What it measured
On the paper's IPv4 benchmark, FIRE/J's bytecode back-end matched in 0.1 µs, its Java-source back-end in 0.2 µs, dk.brics.automaton in 0.3 µs and the Java SDK's own engine in 3.5 µs — a factor of 35 over the platform engine, measured on a 2.8 GHz Pentium 4 with 512 MB of memory running Linux 2.6.16.
Where it sits
The engine is FIRE/J, whose page carries the architecture, the 2026 rerun of these measurements and the limits — it is a DFA engine, so backreferences and lookaround are out of scope, and compilation costs far more than the JDK's does. The work began as the MSc dissertation.
Written from the paper itself — the PDF linked above. The 0.1/0.2/0.3/3.5 µs figures are the paper's own; the 2026 measurements quoted on the FIRE/J page are separate and marked as such there.