Faster compiling of charset regexpes #63528

Activity

1. serhiy-storchaka commented on Oct 21, 2013

   

   serhiy-storchaka

   on Oct 21, 2013

   MemberAuthor

   More actions

   Here is a patch which speed up compiling of regular expressions with big charsets.

   Microbenchmark:
   $ ./python -m timeit "from sre_compile import compile; r = '[%s]' % ''.join(map(chr, range(256, 2**16, 255)))" "compile(r, 0)"

   Unpatched (but with fixed bpo-19327): 119 msec per loop
   Patched: 59.6 msec per loop

   Compiling regular expressions with big charset was main cause of slowing down importing the email.message module (bpo-11454).
2. serhiy-storchaka

   self-assigned this

   on Oct 21, 2013
3. serhiy-storchaka

   added

   stdlibStandard Library Python modules in the Lib/ directoryStandard Library Python modules in the Lib/ directory

   topic-regex

   performancePerformance or resource usagePerformance or resource usage

   on Oct 21, 2013
4. serhiy-storchaka commented on Oct 24, 2013

   

   serhiy-storchaka

   on Oct 24, 2013

   MemberAuthor

   More actions

   Here is a more complex patch which optimizes charset compiling. It affects small charsets too. Big charsets now supports same optimizations as small charsets. Optimized bitmap now can be used even if the charset contains category items or non-bmp characters.

   $ ./python -m timeit "from sre_compile import compile; r = '[0-9]+'"  "compile(r, 0)"
   Unpatched: 1000 loops, best of 3: 457 usec per loop
   Patched: 1000 loops, best of 3: 368 usec per loop
   $ ./python -m timeit "from sre_compile import compile; r = '[ \t\n\r\v\f]+'"  "compile(r, 0)"
   Unpatched: 1000 loops, best of 3: 490 usec per loop
   Patched: 1000 loops, best of 3: 413 usec per loop
   $ ./python -m timeit "from sre_compile import compile; r = '[0-9A-Za-z_]+'"  "compile(r, 0)"
   Unpatched: 1000 loops, best of 3: 760 usec per loop
   Patched: 1000 loops, best of 3: 527 usec per loop
   $ ./python -m timeit "from sre_compile import compile; r = r'[^\ud800-\udfff]*'"  "compile(r, 0)"
   Unpatched: 100 loops, best of 3: 2.07 msec per loop
   Patched: 1000 loops, best of 3: 1.44 msec per loop
   $ ./python -m timeit "from sre_compile import compile; r = '[\u0410-\u042f\u0430-\u043f\u0404\u0406\u0407\u0454\u0456\u0457\u0490\u0491]+'"  "compile(r, 0)"
   Unpatched: 100 loops, best of 3: 8.24 msec per loop
   Patched: 100 loops, best of 3: 2.13 msec per loop
   $ ./python -m timeit "from sre_compile import compile; r = '[%s]' % ''.join(map(chr, range(256, 2**16, 255)))"  "compile(r, 0)"
   Unpatched: 10 loops, best of 3: 119 msec per loop
   Patched: 10 loops, best of 3: 24.1 msec per loop
5. serhiy-storchaka

   changed the title [-]Faster compiling of big charset regexpes[/-] [+]Faster compiling of charset regexpes[/+] on Oct 24, 2013
6. serhiy-storchaka commented on Oct 25, 2013

   

   serhiy-storchaka

   on Oct 25, 2013

   MemberAuthor

   More actions

   Updated patch addresses Antoine's comments. One my bug fixed.
7. python-dev commented on Oct 27, 2013

   

   python-devmannequin

   on Oct 27, 2013

   Mannequin

   More actions

   New changeset d5498d9d9bb0 by Serhiy Storchaka in branch 'default':
   Issue bpo-19329: Optimized compiling charsets in regular expressions.
   http://hg.python.org/cpython/rev/d5498d9d9bb0
8. serhiy-storchaka commented on Oct 27, 2013

   

   serhiy-storchaka

   on Oct 27, 2013

   MemberAuthor

   More actions

   Thank you Antoine for your review.
9. serhiy-storchaka

   closed this as completedon Oct 27, 2013
10. python-dev commented on Oct 31, 2014

    

    python-devmannequin

    on Oct 31, 2014

    Mannequin

    More actions

    New changeset ebd48b4f650d by Serhiy Storchaka in branch '2.7':
    Backported the optimization of compiling charsets in regular expressions
    https://hg.python.org/cpython/rev/ebd48b4f650d
11. ezio-melotti

    transferred this issue fromon Apr 10, 2022