I'm trying to figure out counter-intuitive performance differences between Python, Cython and pure C with regex matching.

There is a small sample program that takes a source text file (17 KB), a dictionary of 2000 words, creates a regex with those words (word1|word2|...), and finds all instances of said dictionary in the source file.

First, I've done a pure Python implementation which looks like this:

def scanFile(filename, patterns):
   pattern_regex = re.compile('|'.join(patterns))
   pageContent = open(filename).read()
   matchingPatterns = set()
   for matchObj in pattern_regex.finditer(pageContent):
      matchingPatterns.add(matchObj.group(0))

   return matchingPatterns

Then, I've tried optimising this by reimplementing the same with Cython, on top of regex.h rather than Python's re module.

cdef extern from "regex.h" nogil:
   ctypedef struct regmatch_t:
      int rm_so
      int rm_eo
   ctypedef struct regex_t:
      pass
   int REG_EXTENDED
   int regcomp(regex_t* preg, const char* regex, int cflags)
   int regexec(const regex_t *preg, const char *string, size_t nmatch, regmatch_t pmatch[], int eflags)
   void regfree(regex_t* preg) 

def matchPatterns(bytes pageContent, bytes regex):
   cdef set matchingPatterns = set()
   cdef regex_t regex_obj
   cdef regmatch_t regmatch_obj[1]
   cdef int regex_res = 0
   cdef int current_str_pos = 0

   regcomp(&regex_obj, regex, REG_EXTENDED)
   regex_res = regexec(&regex_obj, pageContent[current_str_pos:], 1, regmatch_obj, 0)
   while regex_res == 0:
      matchingPatterns.add(pageContent[current_str_pos + regmatch_obj[0].rm_so: current_str_pos + regmatch_obj[0].rm_eo])
      current_str_pos += regmatch_obj[0].rm_eo
      regex_res = regexec(&regex_obj, pageContent[current_str_pos:], 1, regmatch_obj, 0)

   regfree(&regex_obj)
   return matchingPatterns

Performance, however, turned out to be precisely the other way around: Cython+regex.h takes about 2.34 sec and Python takes 0.92 sec.

After running a bit of profiling and custom commented out code, I confirmed the suspicion that it's down to regexec which takes 10s of milliseconds on each invocation.

Just to make sure it's not Cython that's at fault, prepared a standalone C unit test which uses the same inputs and regex.h, and it also showed worse results than Python (about 1.60 sec, i.e. 60% slower than Python).

So, with all of that, I'd be thankful for any insight into why regexec has such a poor performance.

I'm running this on Python 2.7.10, gcc 4.9.2, Cython 0.22, and the platform is Cygwin/Windows. I had a similar discrepancy when running the same on Ubuntu.