[issue13159] _io.FileIO uses a quadratic-time buffer growth algorithm
Roundup Robot devn...@psf.upfronthosting.co.za added the comment: New changeset d18c80a8c119 by Nadeem Vawda in branch '3.2': Issue #13159: Replace FileIO's quadratic-time buffer growth algorithm with a linear-time one. http://hg.python.org/cpython/rev/d18c80a8c119 New changeset 4a6709a071d0 by Nadeem Vawda in branch 'default': Merge #13159: Replace FileIO's quadratic-time buffer growth algorithm with a linear-time one. http://hg.python.org/cpython/rev/4a6709a071d0 -- nosy: +python-dev ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13159 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13159] _io.FileIO uses a quadratic-time buffer growth algorithm
Roundup Robot devn...@psf.upfronthosting.co.za added the comment: New changeset c1c434e30e06 by Nadeem Vawda in branch '2.7': Issue #13159: Replace FileIO's quadratic-time buffer growth algorithm with a linear-time one. http://hg.python.org/cpython/rev/c1c434e30e06 -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13159 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13159] _io.FileIO uses a quadratic-time buffer growth algorithm
Antoine Pitrou pit...@free.fr added the comment: Thank you :) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13159 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13159] _io.FileIO uses a quadratic-time buffer growth algorithm
Nadeem Vawda nadeem.va...@gmail.com added the comment: No problem :) -- assignee: - nadeem.vawda resolution: - fixed stage: patch review - committed/rejected status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13159 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13159] _io.FileIO uses a quadratic-time buffer growth algorithm
New submission from Nadeem Vawda nadeem.va...@gmail.com:
As mentioned in issue 6715, the buffer growth strategy used by _io.FileIO
has quadratic running time if each reallocation is O(n). The code in
question is new_buffersize() from Modules/_io/fileio.c:
if (currentsize SMALLCHUNK) {
/* Keep doubling until we reach BIGCHUNK;
then keep adding BIGCHUNK. */
if (currentsize = BIGCHUNK)
return currentsize + currentsize;
else
return currentsize + BIGCHUNK;
}
return currentsize + SMALLCHUNK;
Is there a reason for this? One possible improvement would be to instead
use the same formula as list.resize() in Objects/listobject.c:
new_allocated = (newsize 3) + (newsize 9 ? 3 : 6);
which has amortized O(n) running time behaviour.
Your thoughts?
--
components: IO
messages: 145403
nosy: benjamin.peterson, nadeem.vawda, pitrou, stutzbach
priority: normal
severity: normal
stage: needs patch
status: open
title: _io.FileIO uses a quadratic-time buffer growth algorithm
type: performance
versions: Python 3.3
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue13159
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13159] _io.FileIO uses a quadratic-time buffer growth algorithm
Nadeem Vawda nadeem.va...@gmail.com added the comment: I've attached a patch that makes the suggested change to FileIO, and also to _bz2.BZ2Compressor/Decompressor (which currently have the same issue). -- keywords: +patch Added file: http://bugs.python.org/file23389/buffer-growth.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13159 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13159] _io.FileIO uses a quadratic-time buffer growth algorithm
Changes by Nadeem Vawda nadeem.va...@gmail.com: -- stage: needs patch - patch review ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13159 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13159] _io.FileIO uses a quadratic-time buffer growth algorithm
Changes by STINNER Victor victor.stin...@haypocalc.com: -- nosy: +haypo ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13159 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13159] _io.FileIO uses a quadratic-time buffer growth algorithm
Antoine Pitrou pit...@free.fr added the comment: The patch looks good to me, thanks. -- versions: +Python 2.7, Python 3.2 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13159 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
