I have a large (gigabyte) file where an S-expression appears, and I want to skip to the end of the S-expression. The depth of the S-expression is limited to 2, so I tried using a Python regexp (b'\\((?:[^()]|\\((?:[^()]|)*\\))*\\)'). This turned out to consume too much RAM, and digging deeper I found that memory consumption of moderately complex regexps seems highly unpredictable if the match is large. For instance, the following four equivalent regexps all match a full ten megabyte string. The fourth one (arguably the most complex one) uses a reasonable amount (30M) of RAM, whereas the others consume one gigabyte: import re dot = b'[' + b''.join(b'\\x%02x' % (c,) for c in range(256)) + b']' assert re.match(b'(?:.|.)*', b'a'*10000000).end() > 1000000 assert re.match(b'(?:.|.|a)*', b'a'*10000000).end() > 1000000 assert re.match(b'(?:%s|%s)*' % (dot,dot), b'a'*10000000).end() > 1000000 assert re.match(b'(?:%s|%s|a)*' % (dot,dot), b'a'*10000000).end() > 1000000 (using Python 3.12.3) Is there a reasonable way to predict if the performance of a Python regexp can scale? And in particular, are there some design principles I can follow if I want to avoid performance pitfalls? (This question is specifically about the re module, because I prefer to use standard Python libraries; I suspect this would not be an issue if I switched to a third-party lib like regex) Continue reading...
