Optimize case-insensitive regular expressions

[serhiy-storchaka]

BPO	30285
Nosy	@rhettinger, @ezio-melotti, @serhiy-storchaka
PRs	bpo-30285: Optimize case-insensitive matching and searching #1482

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2017-05-09.20:37:56.796>
created_at = <Date 2017-05-05.17:02:59.161>
labels = ['expert-regex', '3.7', 'library', 'performance']
title = 'Optimize case-insensitive regular expressions'
updated_at = <Date 2017-05-09.20:37:56.795>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2017-05-09.20:37:56.795>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2017-05-09.20:37:56.796>
closer = 'serhiy.storchaka'
components = ['Library (Lib)', 'Regular Expressions']
creation = <Date 2017-05-05.17:02:59.161>
creator = 'serhiy.storchaka'
dependencies = []
files = []
hgrepos = []
issue_num = 30285
keywords = []
message_count = 3.0
messages = ['293127', '293174', '293348']
nosy_count = 4.0
nosy_names = ['rhettinger', 'ezio.melotti', 'mrabarnett', 'serhiy.storchaka']
pr_nums = ['1482']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue30285'
versions = ['Python 3.7']

[serhiy-storchaka]

Matching and searching case-insensitive regular expressions is much slower than matching and searching case-sensitive regular expressions. Case-insensitivity requires converting every character in input string to lower case and disables some optimizations. But there are only 2669 cased characters (52 in ASCII mode). For all other characters in the pattern we can use case-sensitive matching.

Results of microbenchmarks:

$ ./python -m timeit -s "import re; p = re.compile(r'(?ai) +x'); s = ' '*10000+'x'"  "p.match(s)"
Unpatched:  5000 loops, best of 5: 47.1 usec per loop
Patched:    20000 loops, best of 5: 17.6 usec per loop

$ ./python -m timeit -s "import re; p = re.compile(r'(?i) +x'); s = ' '*10000+'x'"  "p.match(s)"
Unpatched:  2000 loops, best of 5: 109 usec per loop
Patched:    20000 loops, best of 5: 17.6 usec per loop

$ ./python -m timeit -s "import re; p = re.compile(r'(?ai)[ \t]+x'); s = ' '*10000+'x'"  "p.match(s)"
Unpatched:  500 loops, best of 5: 537 usec per loop
Patched:    5000 loops, best of 5: 84.2 usec per loop

$ ./python -m timeit -s "import re; p = re.compile(r'(?i)[ \t]+x'); s = ' '*10000+'x'"  "p.match(s)"
Unpatched:  500 loops, best of 5: 608 usec per loop
Patched:    5000 loops, best of 5: 84.1 usec per loop

$ ./python -m timeit -s "import re; p = re.compile(r'(?ai)/x'); s = ' '*10000+'/x'"  "p.search(s)"
Unpatched:  1000 loops, best of 5: 226 usec per loop
Patched:    20000 loops, best of 5: 13.4 usec per loop

$ ./python -m timeit -s "import re; p = re.compile(r'(?i)/x'); s = ' '*10000+'/x'"  "p.search(s)"
Unpatched:  1000 loops, best of 5: 284 usec per loop
Patched:    20000 loops, best of 5: 13.4 usec per loop

$ ./python -m timeit -s "import re; p = re.compile(r'(?ai)[/%]x'); s = ' '*10000+'/x'"  "p.search(s)"
Unpatched:  500 loops, best of 5: 483 usec per loop
Patched:    1000 loops, best of 5: 279 usec per loop

$ ./python -m timeit -s "import re; p = re.compile(r'(?i)[/%]x'); s = ' '*10000+'/x'"  "p.search(s)"
Unpatched:  500 loops, best of 5: 549 usec per loop
Patched:    1000 loops, best of 5: 279 usec per loop

The patch also optimizes searching some complex case-sensitive patterns. This is a side effect, I'll provide more comprehensive optimization in other issue.

$ ./python -m timeit -s "import re; p = re.compile(r'([xy])'); s = ' '*10000+'x'"  "p.search(s)"
Unpatched:  500 loops, best of 5: 633 usec per loop
Patched:    1000 loops, best of 5: 250 usec per loop

$ ./python -m timeit -s "import re; p = re.compile(r'((x|y)z)'); s = ' '*10000+'xz'"  "p.search(s)"
Unpatched:  500 loops, best of 5: 716 usec per loop
Patched:    1000 loops, best of 5: 250 usec per loop

[rhettinger]

This seems like a great idea.

[serhiy-storchaka]

New changeset 6d336a0 by Serhiy Storchaka in branch 'master':
bpo-30285: Optimize case-insensitive matching and searching (bpo-1482)
6d336a0