one-more-re-nightmare

one-more-re-nightmare is a regular expression engine that uses the technique presented in Regular-expression derivatives revisited to interpret and compile regular expressions. We use a few tricks to make matching quite fast:

• We use a deterministic finite automaton to have O(n) runtime.
• We run the Common Lisp compiler to generate machine code, rather than interpreting a DFA or bytecode, or jumping through closures (like CL-PPCRE does).
• We generate specialised code for each array type, so everything is inlined.
• If you use the one-more-re-nightmare-simd system on SBCL 2.1.10 or newer with AVX2, we even use vectorised scanning of constant prefixes of regular expressions.

Thanks to Gilbert Baumann for suggesting I use derivatives to compile regular expressions, and then for informing me of how to handle submatching properly, and my discrete mathematics teachers for formally introducing me to finite state machines.

Please see the reference book for how to use one-more-re-nightmare, or an article on the history and theory involved.

While the syntax is admittedly wonky (but somewhat more like how regular expressions are presented in papers), one-more-re-nightmare makes its best effort to implement POSIX semantics for matching (as described in the specification for how regcomp works and regular expression definitions). Any behaviour contrary to POSIX is a bug.

A lousy benchmark

CL-USER> (let ((s (make-string 1000000 :initial-element #\a)))
           (setf (aref s 333333) #\b)
           (setf (aref s 555555) #\c)
           (the-cost-of-nothing:bench
            (all-string-matches "ab|ac" s)))

CL-USER> (let ((s (make-string 1000000 :initial-element #\a)))
           (setf (aref s 333333) #\b)
           (setf (aref s 555555) #\c)
           (the-cost-of-nothing:bench
            (cl-ppcre:all-matches-as-strings "ab|ac" s)))

Note that, by nature of calling the Common Lisp compiler, one-more-re-nightmare will take longer to compile a regular expression, so it is better suited for many matching operations with few expressions. It does cache compiled expressions when using the high-level interface, so the initial cost may amortize well over many calls; and constant regular expression strings are compiled at compile-time, with no runtime overhead whatsoever.

engine	SBCL	Clozure CL	SBCL with AVX2	ditto, SIMPLE-BASE-STRING
o-m-r-n	0.57ms	2.93ms	0.18ms	55µs
compilation time	4.65ms	3.76ms	6.82ms	6.43ms
cl-ppcre	22.8ms	45.3ms	22.8ms	21.6ms
break even after	209kchars	88.7kchars	301kchars	305kchars