[issue11740] difflib html diff takes extremely long

[Filip Gruszczyński]

Filip Gruszczyński <gruszczy at gmail.com> added the comment:

The culprit seems to be Differ._fancy_replace. There is a nasty quadratic loop there, that has pretty complex internal code. I have done a quick a fix, that makes example run below a second at the expense of not calling _fancy_replace for longer chunks and using _plain_replace instead.

Another solution for long chunks would be to split them into smaller parts and process separately. This way quadratic time will be smaller and we still can benefit from _fancy_helper logic.

----------
keywords: +patch
Added file: http://bugs.python.org/file21501/11740.patch

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue11740>
_______________________________________