homepage

➜

This issue tracker has been migrated to GitHub , and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Recipients
Author	gregory.p.smith
Date	2007年02月17日.23:39:24
SpamBayes Score
Marked as misclassified
Message-id
In-reply-to

Content
in short, the re module can degenerate to really really horrid performance. See this for how and why: http://swtch.com/~rsc/regexp/regexp1.html exponential decline instead of squared. I don't have a patch so i'm filing this bug as a starting point for future work. The Modules/_sre.c files implementation could be updated to use the parallel stepping Thompson approach instead of recursive backtracking. filing this as a bug until me or someone else comes up with a patch.

Content

in short, the re module can degenerate to really really horrid performance. See this for how and why:
 http://swtch.com/~rsc/regexp/regexp1.html
exponential decline instead of squared.
I don't have a patch so i'm filing this bug as a starting point for future work. The Modules/_sre.c files implementation could be updated to use the parallel stepping Thompson approach instead of recursive backtracking.
filing this as a bug until me or someone else comes up with a patch.

History
Date	User	Action	Args
2007年08月23日 16:12:35	admin	link	issue1662581 messages
2007年08月23日 16:12:35	admin	create