Message201032
sre_parse.parse_template uses string concatenation to accumulate characters.
def literal(literal, p=p, pappend=a):
if p and p[-1][0] is LITERAL:
p[-1] = LITERAL, p[-1][1] + literal
else:
pappend((LITERAL, literal))
This operation have quadratic calculation complexity for long replacement strings.
$ ./python -m timeit -n1 -r1 -s "from sre_parse import parse_template; repl = 'x'*100000" "parse_template(repl, '')"
1 loops, best of 1: 3.38 sec per loop
$ ./python -m timeit -n1 -r1 -s "from sre_parse import parse_template; repl = 'x'*200000" "parse_template(repl, '')"
1 loops, best of 1: 18.2 sec per loop
The proposed patch change amortized complexity to be linear. It also speeds up parsing shorter strings.
$ ./python -m timeit -n1 -r1 -s "from sre_parse import parse_template; repl = 'x'*100000" "parse_template(repl, '')"
1 loops, best of 1: 915 msec per loop
$ ./python -m timeit -n1 -r1 -s "from sre_parse import parse_template; repl = 'x'*200000" "parse_template(repl, '')"
1 loops, best of 1: 1.79 sec per loop |
|
Date |
User |
Action |
Args |
2013-10-23 14:36:02 | serhiy.storchaka | set | recipients:
+ serhiy.storchaka, pitrou, ezio.melotti, mrabarnett |
2013-10-23 14:36:02 | serhiy.storchaka | set | messageid: <1382538962.45.0.421817949827.issue19365@psf.upfronthosting.co.za> |
2013-10-23 14:36:02 | serhiy.storchaka | link | issue19365 messages |
2013-10-23 14:36:02 | serhiy.storchaka | create | |
|