From a0d9dcfe97e824e25174a3bfc9116e505eac0a51 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Tue, 26 Jan 2010 14:12:35 -0800 Subject: Optimization in derivative-based regex engine. Exponential memory consumption behavior was observed when matching the input aaaaaa.... against the regex a?a?a?a?....aaaa.... The fix is to eliminate common subexpressions from the derivative for the or operator. --- ChangeLog | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) (limited to 'ChangeLog') diff --git a/ChangeLog b/ChangeLog index 7868167c..c1a37dc3 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,21 @@ +2010-01-26 Kaz Kylheku + + Optimization in derivative-based regex engine. + Exponential memory consumption behavior was observed when + matching the input aaaaaa.... + against the regex a?a?a?a?....aaaa.... + The fix is to eliminate common subexpressions + from the derivative for the or operator. + + * lib.c (memqual, mapcon): New functions + + * lib.h (memqual, mapcon): Declared. + + * regex.c (flatten_or, unflatten_or, + unique_first, reduce_or): New functions. + (reg_derivative): Apply reduce_or + to the constructed disjunction. + 2010-01-25 Kaz Kylheku Version 032 -- cgit v1.2.3