Description

assignee = None
closed_at = <Date 2011-10-13.14:01:59.975>
created_at = <Date 2011-10-12.16:02:00.072>
labels = ['expert-IO', 'performance']
title = '_io.FileIO uses a quadratic-time buffer growth algorithm'
updated_at = <Date 2011-10-13.14:01:59.973>
user = 'https://bugs.python.org/nadeemvawda'

activity = <Date 2011-10-13.14:01:59.973>
actor = 'nadeem.vawda'
assignee = 'nadeem.vawda'
closed = True
closed_date = <Date 2011-10-13.14:01:59.975>
closer = 'nadeem.vawda'
components = ['IO']
creation = <Date 2011-10-12.16:02:00.072>
creator = 'nadeem.vawda'
dependencies = []
files = ['23389']
hgrepos = []
issue_num = 13159
keywords = ['patch']
message_count = 7.0
messages = ['145403', '145418', '145443', '145448', '145449', '145450', '145453']
nosy_count = 6.0
nosy_names = ['pitrou', 'vstinner', 'nadeem.vawda', 'benjamin.peterson', 'stutzbach', 'python-dev']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue13159'
versions = ['Python 2.7', 'Python 3.2', 'Python 3.3']

Activity

1. nadeemvawda commented on Oct 12, 2011

   

   nadeemvawdamannequin

   on Oct 12, 2011

   MannequinAuthor

   More actions

   As mentioned in bpo-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?
2. nadeemvawda

   added

   topic-IO

   performancePerformance or resource usagePerformance or resource usage

   on Oct 12, 2011
3. nadeemvawda commented on Oct 12, 2011

   

   nadeemvawdamannequin

   on Oct 12, 2011

   MannequinAuthor

   More actions

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

   

   pitrou

   on Oct 12, 2011

   Member

   More actions

   The patch looks good to me, thanks.
5. python-dev commented on Oct 13, 2011

   

   python-devmannequin

   on Oct 13, 2011

   Mannequin

   More actions

   New changeset d18c80a8c119 by Nadeem Vawda in branch '3.2':
   Issue bpo-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 bpo-13159: Replace FileIO's quadratic-time buffer growth algorithm with a linear-time one.
   http://hg.python.org/cpython/rev/4a6709a071d0
6. python-dev commented on Oct 13, 2011

   

   python-devmannequin

   on Oct 13, 2011

   Mannequin

   More actions

   New changeset c1c434e30e06 by Nadeem Vawda in branch '2.7':
   Issue bpo-13159: Replace FileIO's quadratic-time buffer growth algorithm with a linear-time one.
   http://hg.python.org/cpython/rev/c1c434e30e06
7. pitrou commented on Oct 13, 2011

   

   pitrou

   on Oct 13, 2011

   Member

   More actions

   Thank you :)
8. nadeemvawda commented on Oct 13, 2011

   

   nadeemvawdamannequin

   on Oct 13, 2011

   MannequinAuthor

   More actions

   No problem :)
9. nadeemvawda

   closed this as completedon Oct 13, 2011
10. nadeemvawda

    self-assigned this

    on Oct 13, 2011
11. ezio-melotti

    transferred this issue fromon Apr 10, 2022

Issue actions