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