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
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
___
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
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
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
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
___
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
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
___
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
___
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
___
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
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
___
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
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:
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',
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
___
16 matches
Mail list logo
