This patch speeds up the textwrap module, so that it
takes O(n) time to process n chunks rather than the
O(n^2) time that textwrap previously took.

This makes textwrap much faster for large texts (for
example, the patched version runs textwrap.fill('foo' *
100000) 80 times faster than the unpatched version).

Logged In: YES 
user_id=1039782

I assign the Copyright for this patch to the Python Software
Foundation.

Logged In: YES 
user_id=2772

I didn't benchmark the speed increase, but I verified that
on my system 'test_textwrap.py' still completes
successfully.  I also looked at the patch and found the
change to be straightforward.  However, I wonder if the
speed increase would be nearly as great if 
collections.deque was used instead of the reversed list. 
Unfortunately, the textwrap module seems to intend
portability with older versions of Python, which would not
work if the collections module is used.

Logged In: YES 
user_id=1039782

Personally, I need linear running time for this module, so I 
contributed the patch in the hope that others would find it 
useful.  The practical result is that parsing a 5 MB unwrapped 
text file takes an order of seconds with the patch, and > 10 
minutes without the patch (3 GHz Pentium).

If the code is written with a deque or queue, there would be a 
similar speed incease, since deque operations are O(1).  Is 
the patch not 'clean enough' code-wide?  (I could recode it to 
use collections.deque or else a simple dummy queue if 
collections is not available).

Logged In: YES 
user_id=1188172

I've applied the original patch, ensured the test suite ran
and measured the same speedup as Connelly.

Looks like a sound addition.
Another option is, as he said, using collections.deque or an
substitute class for compatibility.

Logged In: YES 
user_id=80475

Applied as Lib/textwrap.py 1.38.