Performance

The concept behind FIRE/J is the creation of a fast regular expression engine. Its performance characteristics are analysed in the publication Vassilios Karakoidas and Diomidis Spinellis, FIRE/J - Optimizing Regular Expression Searches with Generative Programming, Software: Practice and Experience, 2007 (to appear) (PDF).

The main distribution of FIRE/J contains a mini-benchmark with other two regular expression engines, Automaton (dfa) and java.util.regex (nfa, aka sun, included in the JRE).

To invoke the mini-benchmark script run. java -jar fire-release.jar benchmark (do not forget to include the other libraries to the classpath).

Here are some results from my macbook pro (Dual 2 core duo, 2GB ram, Mac OS X 10.5, JRE 1.6):

Regex: ([0-9]{1,3}\.){3}[0-9]{1,3}[ \-]+.[0-9]{1,2}/[a-zA-Z]{3}/[0-9]{4}:[0-9]{2}:[0-9]{2}:[0-9]{2}[ ]\+[0-9]{4}.[ ].(GET|POST)[ ]
[a-zA-Z/~0-9.%]+[ ]HTTP/[1-9]\.[1-9]{1,2}.[ ][0-9]+[ ][0-9]+[ ].-.[ ].[a-zA-Z0-9./]+[ ]\(.+\)[ ][a-zA-Z/0-9]+[ ][a-zA-Z/.0-9]+.
Engine: fire Time: 496 msecs
Engine: automaton Time: 782 msecs
Engine: sun Time: 7291 msecs

Regex: [0-9]*
Engine: fire Time: 33 msecs
Engine: automaton Time: 94 msecs
Engine: sun Time: 462 msecs

Regex: (([01]?[0-9][0-9]?|2[0-4][0-9]|25[0-5])\.){3}([01]?[0-9][0-9]?|2[0-4][0-9]|25[0-5])
Engine: fire Time: 44 msecs
Engine: automaton Time: 87 msecs
Engine: sun Time: 975 msecs

Generated Code

Of course, the optimisation technique we used (code generation), has its vulnerability. The generated code size increases by analogy with the regular expression size. The bigger the regular expression, the bigger the resulting generated code, increasing the chances of cache misses and decreased performance.