base64.b85encode uses significant amount of RAM

[AbdealiLoKo]

Bug report

On the same string:

• b64encode: RAM: 604MB, CPU: 79%, Time taken: 1.18sec and gave a result
• b85encode: RAM: 6.9GB, CPU: 64%, Time taken: 45sec and crashed due to insufficient RAM (most likely)

b85encode takes up my entire RAM and crashes

On IPython:

In [1]: import base64

In [2]: contents = b'a' * 250 * 1024 * 1024

In [3]: %time len(base64.b64encode(contents).decode("ascii")) / 1024 / 1024
CPU times: user 489 ms, sys: 414 ms, total: 904 ms
Wall time: 974 ms
Out[3]: 333.33333587646484

In [4]: %time len(base64.b85encode(contents).decode("ascii")) / 1024 / 1024
Killed

Here is the GNU time stats:

$ /usr/bin/time /opt/python3.9/bin/python -c "import base64; print(len(base64.b64encode(b'a' * 250 * 1024 * 1024)) / 1024 / 1024)"
333.33333587646484
0.55user 0.39system 0:01.18elapsed 79%CPU (0avgtext+0avgdata 604008maxresident)k
0inputs+0outputs (0major+151155minor)pagefaults 0swaps

$ /usr/bin/time /opt/python3.9/bin/python -c "import base64; print(len(base64.b85encode(b'a' * 250 * 1024 * 1024)) / 1024 / 1024)"
26.08user 3.39system 0:45.86elapsed 64%CPU (0avgtext+0avgdata 6966080maxresident)k
512inputs+0outputs (2major+1756895minor)pagefaults 0swaps

I have gotten same results in Python 3.6, 3.7, 3.8, 3.9

Your environment

• CPython versions tested on: Python 3.9 installed with miniconda
• Operating system and architecture: CentOS 7, AWS t3.large machine

Linked PRs

• gh-101178: Add Ascii85, Base85, and Z85 support to binascii #102753
• gh-101178: refactor base64.b85encode to be memory friendly #112248
• gh-101178: Fix possible integer overflow in Ascii85 encoder with wrapcol=1 #144778
• gh-101178: Fix UB in binascii.b2a_ascii85 #148166

[sobolevn]

I can confirm, that this still happens on main:

» time ./python.exe -c "import base64; print(len(base64.b85encode(b'a' * 250 * 1024 * 1024)) / 1024 / 1024)"
312.5
./python.exe -c   160.32s user 74.28s system 87% cpu 4:29.26 total

Compare it to almost-instant 64 version (it uses binascii's C implementation):

» time ./python.exe -c "import base64; print(len(base64.b64encode(b'a' * 250 * 1024 * 1024)) / 1024 / 1024)"
333.33333587646484
./python.exe -c   0.91s user 0.26s system 98% cpu 1.187 total

[eendebakpt]

I looked into the implementation of b85encode (in _85encode). The memory problems are caused by the fact that internally copies of the data are made. The copies consist of small chuncks, where each chuck has the memory overhead of a python object.

• First with words = struct.Struct('!%dI' % (len(b) // 4)).unpack(b). There is a iter_unpack method in the Struct class, but it does not work as expected.
• And then with a list comprehension chunks = [ ... for word in words]. In the case padding=False we can replace this with a generator which would save memory. For padding=True we need to modify the last element of the list, which does not work for the generator.

The poor performance (compared to b64encode) is mainly due to the part (chars2[word // 614125] + chars2[word // 85 % 7225] + chars[word % 85]).

To make any significant gains an implementation in C seems the most worthwhile.