[New-bugs-announce] [issue13159] _io.FileIO uses a quadratic-time buffer growth algorithm
Nadeem Vawda
report at bugs.python.org
Wed Oct 12 18:02:00 CEST 2011
New submission from Nadeem Vawda <nadeem.vawda at 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 <report at bugs.python.org>
<http://bugs.python.org/issue13159>
_______________________________________
More information about the New-bugs-announce
mailing list