[issue17812] Quadratic complexity in b32encode
Roundup Robot added the comment: 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 -- nosy: +python-dev ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Serhiy Storchaka added the comment: That is why I proposed two patches. -- versions: +Python 3.3 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Changes by Serhiy Storchaka storch...@gmail.com: -- assignee: - serhiy.storchaka resolution: - fixed stage: patch review - committed/rejected status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Serhiy Storchaka added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Serhiy Storchaka added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Antoine Pitrou added the comment: Using a bytearray, rather than accumulating into a list, may reduce memory consumption. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Serhiy Storchaka added the comment: Thank you Antoine. Here are updated patches. -- Added file: http://bugs.python.org/file30308/base32_fix_2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Changes by Serhiy Storchaka storch...@gmail.com: Added file: http://bugs.python.org/file30309/base32_optimize_2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Changes by Serhiy Storchaka storch...@gmail.com: Removed file: http://bugs.python.org/file29971/base32_fix.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Changes by Serhiy Storchaka storch...@gmail.com: Removed file: http://bugs.python.org/file29972/base32_optimize.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Changes by Antoine Pitrou pit...@free.fr: -- versions: -Python 3.3 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Serhiy Storchaka added the comment: I think 3.3 needs a fix. The quadratic complexity is a bug. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Antoine Pitrou added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
New submission from Serhiy Storchaka: 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. -- components: Library (Lib) files: base32_fix.patch keywords: patch messages: 187527 nosy: pitrou, serhiy.storchaka priority: normal severity: normal stage: patch review status: open title: Quadratic complexity in b32encode type: performance versions: Python 3.3, Python 3.4 Added file: http://bugs.python.org/file29971/base32_fix.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Serhiy Storchaka added the comment:
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(101) 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(101))
decode(data)
Results:
First patch Second patch
b32encode1.25 sec 486 msec
b32decode2.08 sec 835 msec
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue17812
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17812] Quadratic complexity in b32encode
Changes by Serhiy Storchaka storch...@gmail.com: Added file: http://bugs.python.org/file29972/base32_optimize.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17812 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
