The implementation of encode and decode are slow, and scale nonlinearly
in the size of the message to be encoded/decoded.

 A simple fix is to use an array.array('c') and append to it, rather
than using string concatenation. This change makes the code more than an
order of magnitude faster.

Do you have a patch?
Also, detailed timing examples are welcome (you can e.g. use the
"timeit" module from the command line).

I can certainly generate a patch for you. What form would you like it
in, and against what source tree? Also, do you have a preference between
the use of array.array vs. standard arrays? (I don't know whether it's
good or bad to depend on "import array" in quoprimime.)

The patch must be against the SVN trunk, in standard unified diff ("svn
diff" does the trick).

What do you call standard arrays? Do you mean the builtin list type?
Storing one separate character per list element is a poor choice because
it will waste a lot of memory. The array.array type is more efficient
for this.

However, there are two other, more idiomatic ways of doing this:
- accumulate the chunks of encoded/decoded data into a list (but not
only 1-character strings...) and join() them at the end.
- or, use a StringIO object (from the cStringIO module)

Bonus points if you time all three possibilities and submit the fastest :-)

Yes, sorry, I meant "built-in list type" not "array". Your point about
using lists this way is valid, and is why I used array.array('c').
I will do as you suggest and try all three methods. I did time the
array.array approach vs. the one currently in the code and it was about
30 times faster.

Any news?

I re-wrote encode() to be simpler and faster.
My version runs about 10 times faster on a 30KB message.

I have tested it somewhat but not rigorously

see attached patch

3.2+ already use StringIO, there is no nonlinearity. On 2.7 I couldn't find the nonlinearity with the texts of up to 100 MB.

Therefore the path outdated as bugfix.

However it shows 20-30x speedup on 2.7. It would be worth port it to 3.4. This will be a significant enhancement (if the patch can preserve the current semantics).

Here is a patch for 3.4 based on Matt's patch with additional optimizations. It speeds up body_encode() and header_encode().

$ ./python -m timeit -s "from email.quoprimime import body_encode as encode; x = open('Lib/decimal.py').read()[:100000]"  "encode(x)"

Before patch: 1.12 sec per loop
After patch: 26.3 msec per loop

$ ./python -m timeit -s "from email.quoprimime import header_encode as encode; x = b'A'*100"  "encode(x)"

Before patch: 97.9 usec per loop
After patch: 23.7 usec per loop

For non-ascii data difference is even larger.

New changeset 4c5b1932354b by R David Murray in branch '3.3':
#20206, #5803: more efficient algorithm that doesn't truncate output.
http://hg.python.org/cpython/rev/4c5b1932354b

New changeset b6c3fc21286f by R David Murray in branch 'default':
Merge #20206, #5803: more efficient algorithm that doesn't truncate output.
http://hg.python.org/cpython/rev/b6c3fc21286f

I've reviewed this and applied it to both 3.3 and 3.4 in order to fix issue 20206.  Thanks, Serhiy.