[pcre-dev] Improve prefix search in JIT

Hi,

this mail is a summary of another performance optimization which was recently added to the JIT compiler. The new code is basically a simplified version of the Boyer–Moore string search algorithm, and its purpose is searching for fixed prefixes.

The first step is finding the longest fixed part of a pattern, which position is known. For example, the analysis of the /a.abcd.ab.*abcde/ pattern yields "abcd", since this string is longer than both "a" and "ab". Although "abcde" is even longer than "abcd", its position is unknown, which makes it unsuitable for prefix searching. Strings shorter than four characters are considered as too short, and the optimization is aborted. The analysis also detect the offset of the last character. The offset of 'd' is 5 in this particular case.

The next step is generating a table, which has 256 entries, one for each character in 8 bit mode. In 16 and 32 bit modes the entries are generated for character & 0xff codes (during runtime, only the last byte of a character is read). All entries contain the number of characters, which can be skipped when that particular character is read from the last character offset. In our example, the entry of 'd' will be zero, since this character can be part of a match. The entry of 'c' is one, 'b' is two, 'a' is three, and all other characters are four. Hence, if we read an 'e', we can advance the input pointer by four characters, and we don't need to spend CPU cycles to check the skipped characters.

I saw a nice performance progresson on my Snort benchmark set (using an x86-64 sytem). The total runtime was decreased to 40.8 seconds from 45.0 seconds, which is 9.4% speedup.

Regards,
Zoltan