horrible performance of textwrap.wrap() with a long word

[inkerman]

BPO	22687
Nosy	@birkenfeld, @pitrou, @bitdancer, @serhiy-storchaka
Files	wordsplit_complexity.patch wordsplit_complexity2.patch wordsplit.patch wordsplit_2.patch wordsplit_3.patch

^{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 2015-03-24.20:05:10.991>
created_at = <Date 2014-10-21.16:45:26.428>
labels = ['performance']
title = 'horrible performance of textwrap.wrap() with a long word'
updated_at = <Date 2015-03-24.20:05:10.990>
user = 'https://bugs.python.org/inkerman'

bugs.python.org fields:

activity = <Date 2015-03-24.20:05:10.990>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2015-03-24.20:05:10.991>
closer = 'serhiy.storchaka'
components = []
creation = <Date 2014-10-21.16:45:26.428>
creator = 'inkerman'
dependencies = []
files = ['37179', '37180', '37188', '37190', '38149']
hgrepos = []
issue_num = 22687
keywords = ['patch']
message_count = 31.0
messages = ['229768', '229770', '230864', '231037', '231039', '231044', '231045', '231048', '231050', '231052', '231065', '231066', '231067', '231068', '231071', '231104', '231105', '231106', '231116', '231121', '231122', '231127', '231128', '231129', '231130', '231131', '231144', '231474', '234882', '236046', '239156']
nosy_count = 7.0
nosy_names = ['georg.brandl', 'pitrou', 'r.david.murray', 'python-dev', 'serhiy.storchaka', 'roippi', 'inkerman']
pr_nums = []
priority = 'low'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue22687'
versions = ['Python 3.5']

[inkerman]

Wrapping a paragraph containing a long word takes a lot of time:

$ time python3 -c 'import textwrap; textwrap.wrap("a" * 2 ** 16)'

real 3m14.923s
user 3m14.792s
sys 0m0.016s
$

A straightforward replacement is 5000 times faster:

$ time python3 -c '("".join(x) for x in zip(*[iter("a" * 2 ** 16)] * 70))'

real 0m0.053s
user 0m0.032s
sys 0m0.016s
$

Tested on Debian with python3.4 3.4.2-1 and python2.7 2.7.8-10.

[serhiy-storchaka]

This particular case is related to the behavior of the wordsep_re regular expression in worst case. When text contains long sequence of words characters which is not ended by a hypen, or long sequence of non-word and non-space characters (and in some other cases), computational complexity of this regular expression matching is quadratic. This is a peculiarity of current implementation of regular expression engine. May be it is possible to rewrite the regular expression so that quadratic complexity will gone, but this is not so easy.

The workaround -- use break_on_hyphens=False.

[serhiy-storchaka]

May be atomic grouping or possessive quantifiers (bpo-433030) will help with this issue.

[pitrou]

Here is a patch which solves the algorithmic complexity issue by using a different scheme: instead of splitting, match words incrementally.

[pitrou]

Actually, it is enough to change the regexp while still using re.split(). Updated patch attached.

[serhiy-storchaka]

Unfortunately there are two disadvantages:

1. wordsep_re and wordsep_simple_re are public attributes and user code can depend on this. Changing their is a way to customize TextWrapper.

2. This is slowdown common case (no abnormally long words):

$ ./python -m timeit -s 'import textwrap; s = "abcde " * 10**4' -- 'textwrap.wrap(s)'

Unpatched: 178 msec per loop
Patched: 285 msec per loop

First reason stopped me from writing a patch.

When change the way how to split words, I suggest to use undocumented re scanner.

[pitrou]

Are you sure? I get the reverse results here (second patch):

Unpatched:
$ ./python -m timeit -s 'import textwrap; s = "abcde " * 10**4' -- 'textwrap.wrap(s)'
10 loops, best of 3: 27 msec per loop

Patched:
$ ./python -m timeit -s 'import textwrap; s = "abcde " * 10**4' -- 'textwrap.wrap(s)'
10 loops, best of 3: 19.2 msec per loop

wordsep_re and wordsep_simple_re are public attributes and user code can depend on this. Changing their is a way to customize TextWrapper.

With my second patch, that shouldn't be a problem.

[serhiy-storchaka]

Oh, sorry, I tested your first patch. Your second patch is faster than current
code to me. But it changes behavior.

>>> textwrap.wrap('"1a-2b', width=5)
['"1a-', '2b']

With the patch the result is ['"1a-2', 'b'].

[pitrou]

Yes... but in both cases the result is nonsensical, and untested.

[serhiy-storchaka]

Possessive quantifiers (bpo-433030) is not a panacea. They allow to speed up regular expressions, but the complexity is still quadratic. Antoine's patch makes the complexity linear.

[serhiy-storchaka]

Current regex produces insane result.

$ ./python -c "import textwrap; print(textwrap.wrap('this-is-a-useful-feature', width=1, break_long_words=False))"
['this-', 'is-a', '-useful-', 'feature']

Antoine's regex produces more correct result for this case: ['this-', 'is-', 'a-', 'useful-', 'feature']. But this is not totally correct, one-letter word should not be separated. This can be easy fixed.

[pitrou]

But this is not totally correct, one-letter word should not be
separated.

Why not? I guess it depends on English's rules for word splitting, which I don't know.
In any case, this issue is not about improving correctness, only performance.

[serhiy-storchaka]

Why not? I guess it depends on English's rules for word splitting, which I
don't know.

I suppose this is common rule in many languages. And current code supports it (there is a special code in the regex to ensure this rule).

In any case, this issue is not about improving correctness,
only performance.

But the patch shouldn't add a regression.

$ ./python -c "import textwrap; print(textwrap.wrap('this-is-a-useful', width=1, break_long_words=False))"

Current code: ['this-', 'is-a-useful']
Patched: ['this-', 'is-', 'a-', 'useful']

Just use lookahead assertion to ensure that the hyphen is followed by at least two letters.

My previous message is about that current code is not always correct so it is acceptable to replace it with not absolutely equivalent code.