Issue #13159: Replace FileIO's quadratic-time buffer growth algorithm with a linear-time one.
Also fix the bz2 module, whose classes used the same algorithm.
diff --git a/Modules/_io/fileio.c b/Modules/_io/fileio.c
index b1d492b..be5c9f8 100644
--- a/Modules/_io/fileio.c
+++ b/Modules/_io/fileio.c
@@ -43,12 +43,6 @@
#define SMALLCHUNK BUFSIZ
#endif
-#if SIZEOF_INT < 4
-#define BIGCHUNK (512 * 32)
-#else
-#define BIGCHUNK (512 * 1024)
-#endif
-
typedef struct {
PyObject_HEAD
int fd;
@@ -565,15 +559,10 @@
}
}
#endif
- 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;
+ /* Expand the buffer by an amount proportional to the current size,
+ giving us amortized linear-time behavior. Use a less-than-double
+ growth factor to avoid excessive allocation. */
+ return currentsize + (currentsize >> 3) + 6;
}
static PyObject *
diff --git a/Modules/bz2module.c b/Modules/bz2module.c
index 3e55202..a671e8d 100644
--- a/Modules/bz2module.c
+++ b/Modules/bz2module.c
@@ -218,25 +218,14 @@
#define SMALLCHUNK BUFSIZ
#endif
-#if SIZEOF_INT < 4
-#define BIGCHUNK (512 * 32)
-#else
-#define BIGCHUNK (512 * 1024)
-#endif
-
/* This is a hacked version of Python's fileobject.c:new_buffersize(). */
static size_t
Util_NewBufferSize(size_t currentsize)
{
- 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;
+ /* Expand the buffer by an amount proportional to the current size,
+ giving us amortized linear-time behavior. Use a less-than-double
+ growth factor to avoid excessive allocation. */
+ return currentsize + (currentsize >> 3) + 6;
}
/* This is a hacked version of Python's fileobject.c:get_line(). */