homepage

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?

I've attached a patch that makes the suggested change to FileIO, and also
to _bz2.BZ2Compressor/Decompressor (which currently have the same issue).

The patch looks good to me, thanks.

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 

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 

Thank you :)

No problem :)