b32encode accumulates encoded data in a bytes object and this operation has quadratic complexity.

Here is a patch, which fixes this issue by accumulating in a list.

And here are other patch, which not only fixes an issue with quadratic complexity, but optimize b32encode and b32decode about 2.5 times.

Microbenchmarks:

./python -m timeit -r 1 -n 10 -s "from base64 import b32encode as encode; data = open('python', 'rb').read(1000001)"  "encode(data)"
./python -m timeit -r 1 -n 1 -s "from base64 import b32encode as encode, b32decode as decode; data = encode(open('python', 'rb').read(1000001))"  "decode(data)"

Results:
           First patch  Second patch
b32encode    1.25 sec     486 msec
b32decode    2.08 sec     835 msec

Note that without patches both tests run many minutes.

base32_fix.patch causes little (5%) performance degradation for small data (< KB), this is perhaps the cause for the use of string concatenation. However base32_optimize.patch speeds up about 3x for such data.

Note that without patches both tests run many minutes.

base32_fix.patch causes little (5%) performance degradation for small data (< KB), this is perhaps the cause for the use of string concatenation. However base32_optimize.patch speeds up about 3x for such data.

Using a bytearray, rather than accumulating into a list, may reduce memory consumption.

Thank you Antoine. Here are updated patches.

I think 3.3 needs a fix. The quadratic complexity is a bug.

Then I would recommend committing the simple patch in 3.3 and the more optimized one in 3.4. Both look fine to me, althgugh I haven't really examined the padding stuff.

New changeset 4b5467d997f1 by Serhiy Storchaka in branch '3.3':
Issue #17812: Fixed quadratic complexity of base64.b32encode().
http://hg.python.org/cpython/rev/4b5467d997f1

New changeset 1b5ef05d6ced by Serhiy Storchaka in branch 'default':
Issue #17812: Fixed quadratic complexity of base64.b32encode().
http://hg.python.org/cpython/rev/1b5ef05d6ced

That is why I proposed two patches.