diff options
| author | Nadeem Vawda <nadeem.vawda@gmail.com> | 2011-10-13 11:38:14 (GMT) |
|---|---|---|
| committer | Nadeem Vawda <nadeem.vawda@gmail.com> | 2011-10-13 11:38:14 (GMT) |
| commit | 72d6a13413d3dedf9979cfbd7bc41d58f52144b6 (patch) | |
| tree | d7a85107c3913d65df3250c2e82109e8998fbd19 /Modules/_bz2module.c | |
| parent | 55c991197b8dc971c1358b2b8e71fc9eaf3970c9 (diff) | |
| parent | d41a98bdd9076eeadf4d3ba6d8db287e26b89777 (diff) | |
| download | cpython-72d6a13413d3dedf9979cfbd7bc41d58f52144b6.zip cpython-72d6a13413d3dedf9979cfbd7bc41d58f52144b6.tar.gz cpython-72d6a13413d3dedf9979cfbd7bc41d58f52144b6.tar.bz2 | |
Merge #13159: Replace FileIO's quadratic-time buffer growth algorithm with a linear-time one.
Also fix the bz2 module, which suffered from the same problem.
Diffstat (limited to 'Modules/_bz2module.c')
| -rw-r--r-- | Modules/_bz2module.c | 16 |
1 files changed, 4 insertions, 12 deletions
diff --git a/Modules/_bz2module.c b/Modules/_bz2module.c index d329c14..b407df9 100644 --- a/Modules/_bz2module.c +++ b/Modules/_bz2module.c @@ -116,22 +116,14 @@ catch_bz2_error(int bzerror) #define SMALLCHUNK BUFSIZ #endif -#if SIZEOF_INT < 4 -#define BIGCHUNK (512 * 32) -#else -#define BIGCHUNK (512 * 1024) -#endif - static int grow_buffer(PyObject **buf) { + /* 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. */ size_t size = PyBytes_GET_SIZE(*buf); - if (size <= SMALLCHUNK) - return _PyBytes_Resize(buf, size + SMALLCHUNK); - else if (size <= BIGCHUNK) - return _PyBytes_Resize(buf, size * 2); - else - return _PyBytes_Resize(buf, size + BIGCHUNK); + return _PyBytes_Resize(buf, size + (size >> 3) + 6); } |