Skip to content

Commit cceb782

Browse files
committed
pythongh-161478: Collect large compression outputs in blocks again, except with glibc
Since pythongh-139877, _BlocksOutputBuffer grows one PyBytesWriter with realloc(). On macOS and Windows, a large block grown with realloc() lands in memory the process has never touched (Windows also copies it), so every call faults in the output's pages again, and zlib, gzip, lzma and zstd decompression got up to 3x slower than in 3.14 from a few MiB of output, and on macOS the process kept the memory of every call. The first blocks (up to 1.34 MiB) still grow the writer. Later blocks are separate bytes objects, joined once at the end, as in 3.14, except on Linux with glibc in the default build, where realloc() grows a large block in place (mremap()) and the writer is faster. Platforms that were not measured, Android, and the free-threaded build (mimalloc copies on realloc()) get 3.14's behaviour. Tests: outputs at and around the block boundaries, for every module.
1 parent 3feccd1 commit cceb782

7 files changed

Lines changed: 340 additions & 19 deletions

File tree

‎Include/internal/pycore_blocks_output_buffer.h‎

Lines changed: 129 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -6,14 +6,17 @@
66
stream->next_out: point to the next output position.
77
stream->avail_out: the number of available bytes left in the buffer.
88
9-
It maintains a list of bytes object, so there is no overhead of resizing
10-
the buffer.
9+
The first blocks are written into a PyBytesWriter, which is returned as is
10+
when the output fits in them. Further blocks are separate bytes objects,
11+
joined once by _BlocksOutputBuffer_Finish(), except where the writer is
12+
known to grow in place (glibc). See OUTPUT_BUFFER_HEAD_SIZE.
1113
1214
Usage:
1315
1416
1, Initialize the struct instance like this:
15-
_BlocksOutputBuffer buffer = {.list = NULL};
16-
Set .list to NULL for _BlocksOutputBuffer_OnError()
17+
_BlocksOutputBuffer buffer = {.writer = NULL};
18+
This zeroes the other members too. _BlocksOutputBuffer_OnError()
19+
relies on .writer and .list being NULL.
1720
1821
2, Initialize the buffer use one of these functions:
1922
_BlocksOutputBuffer_InitAndGrow()
@@ -28,7 +31,8 @@
2831
5, Finish the buffer, and return a bytes object:
2932
_BlocksOutputBuffer_Finish()
3033
31-
6, Clean up the buffer when an error occurred:
34+
6, Clean up the buffer when an error occurred, including when
35+
_BlocksOutputBuffer_Finish() returned NULL:
3236
_BlocksOutputBuffer_OnError()
3337
*/
3438

@@ -53,23 +57,58 @@ typedef struct {
5357
Py_ssize_t max_length;
5458
// Number of blocks of bytes. Used to calculate next allocation size
5559
size_t num_blocks;
60+
// Blocks after the first OUTPUT_BUFFER_HEAD_SIZE bytes, as a list of
61+
// bytes objects. NULL while all the output is in the writer.
62+
PyObject *list;
63+
// Size of the writer's data once blocks are added to the list
64+
Py_ssize_t head_size;
5665
} _BlocksOutputBuffer;
5766

5867
static const char unable_allocate_msg[] = "Unable to allocate output buffer.";
5968

6069
/* In 32-bit build, the max block size should <= INT32_MAX. */
6170
#define OUTPUT_BUFFER_MAX_BLOCK_SIZE (256*1024*1024)
6271

63-
/* Block size sequence */
64-
#define KB (1024)
72+
/* Block size sequence. The first four blocks are the writer's head, see
73+
OUTPUT_BUFFER_HEAD_SIZE; the tests in test_zlib, test_gzip, test_bz2,
74+
test_lzma and test_zstd probe the boundaries of these sizes. */
75+
#define OUTPUT_BUFFER_BLOCK_1 (32*1024)
76+
#define OUTPUT_BUFFER_BLOCK_2 (64*1024)
77+
#define OUTPUT_BUFFER_BLOCK_3 (256*1024)
78+
#define OUTPUT_BUFFER_BLOCK_4 (1024*1024)
6579
#define MB (1024*1024)
6680
static const Py_ssize_t BUFFER_BLOCK_SIZE[] =
67-
{ 32*KB, 64*KB, 256*KB, 1*MB, 4*MB, 8*MB, 16*MB, 16*MB,
81+
{ OUTPUT_BUFFER_BLOCK_1, OUTPUT_BUFFER_BLOCK_2, OUTPUT_BUFFER_BLOCK_3,
82+
OUTPUT_BUFFER_BLOCK_4, 4*MB, 8*MB, 16*MB, 16*MB,
6883
32*MB, 32*MB, 32*MB, 32*MB, 64*MB, 64*MB, 128*MB, 128*MB,
6984
OUTPUT_BUFFER_MAX_BLOCK_SIZE };
70-
#undef KB
7185
#undef MB
7286

87+
/* The writer grows to at most this many bytes: the first four blocks of the
88+
sequence, 1.34 MiB. Up to there, returning the writer without a join
89+
beats separate blocks; from the 4 MiB block on, the blocks win (measured
90+
on macOS and Windows, see gh-161478). Later blocks go to the list, and so
91+
does every block after a larger initial size.
92+
93+
On macOS and Windows, a large block grown with realloc() lands in memory
94+
the process has never touched (on Windows, realloc() also copies it), so
95+
a writer that keeps growing faults in new pages on every call, which
96+
costs more than writing blocks once and joining them at the end, as the
97+
code before gh-139877 did. With glibc, realloc() grows a large block in
98+
place (mremap()), and there growing the writer is faster than joining
99+
blocks. Everything else gets the blocks: platforms that were not
100+
measured, and allocators that copy on realloc(): Android's, musl's, and
101+
mimalloc, the free-threaded build's object allocator (with
102+
PYTHONMALLOC=mimalloc on macOS, the growing writer regressed just like
103+
with the system allocator). */
104+
#if defined(__GLIBC__) && !defined(Py_GIL_DISABLED)
105+
# define OUTPUT_BUFFER_HEAD_SIZE PY_SSIZE_T_MAX
106+
#else
107+
# define OUTPUT_BUFFER_HEAD_SIZE \
108+
(OUTPUT_BUFFER_BLOCK_1 + OUTPUT_BUFFER_BLOCK_2 \
109+
+ OUTPUT_BUFFER_BLOCK_3 + OUTPUT_BUFFER_BLOCK_4)
110+
#endif
111+
73112
/* According to the block sizes defined by BUFFER_BLOCK_SIZE, the whole
74113
allocated size growth step is:
75114
1 32 KB +32 KB
@@ -130,6 +169,8 @@ _BlocksOutputBuffer_InitAndGrow(_BlocksOutputBuffer *buffer,
130169
buffer->allocated = block_size;
131170
buffer->max_length = max_length;
132171
buffer->num_blocks = 1;
172+
buffer->list = NULL;
173+
buffer->head_size = 0;
133174

134175
*next_out = PyBytesWriter_GetData(buffer->writer);
135176
return block_size;
@@ -161,6 +202,8 @@ _BlocksOutputBuffer_InitWithSize(_BlocksOutputBuffer *buffer,
161202
buffer->allocated = init_size;
162203
buffer->max_length = -1;
163204
buffer->num_blocks = 1;
205+
buffer->list = NULL;
206+
buffer->head_size = 0;
164207

165208
*next_out = PyBytesWriter_GetData(buffer->writer);
166209
return init_size;
@@ -209,19 +252,44 @@ _BlocksOutputBuffer_Grow(_BlocksOutputBuffer *buffer,
209252
return -1;
210253
}
211254

212-
if (PyBytesWriter_Grow(buffer->writer, block_size)) {
213-
PyErr_SetString(PyExc_MemoryError, unable_allocate_msg);
214-
return -1;
255+
if (buffer->list == NULL
256+
&& buffer->allocated <= OUTPUT_BUFFER_HEAD_SIZE - block_size)
257+
{
258+
// grow the writer
259+
if (PyBytesWriter_Grow(buffer->writer, block_size)) {
260+
PyErr_SetString(PyExc_MemoryError, unable_allocate_msg);
261+
return -1;
262+
}
263+
char *data = PyBytesWriter_GetData(buffer->writer);
264+
*next_out = data + buffer->allocated;
265+
}
266+
else {
267+
// add a block to the list
268+
if (buffer->list == NULL) {
269+
buffer->list = PyList_New(0);
270+
if (buffer->list == NULL) {
271+
PyErr_SetString(PyExc_MemoryError, unable_allocate_msg);
272+
return -1;
273+
}
274+
buffer->head_size = buffer->allocated;
275+
}
276+
PyObject *block = PyBytes_FromStringAndSize(NULL, block_size);
277+
if (block == NULL) {
278+
PyErr_SetString(PyExc_MemoryError, unable_allocate_msg);
279+
return -1;
280+
}
281+
if (PyList_Append(buffer->list, block) < 0) {
282+
Py_DECREF(block);
283+
PyErr_SetString(PyExc_MemoryError, unable_allocate_msg);
284+
return -1;
285+
}
286+
Py_DECREF(block); // the list holds it
287+
*next_out = PyBytes_AS_STRING(block);
215288
}
216-
217-
Py_ssize_t current_size = buffer->allocated;
218289

219290
// set variables
220291
buffer->allocated += block_size;
221292
buffer->num_blocks += 1;
222-
223-
char *data = PyBytesWriter_GetData(buffer->writer);
224-
*next_out = data + current_size;
225293
return block_size;
226294
}
227295

@@ -244,9 +312,50 @@ _BlocksOutputBuffer_Finish(_BlocksOutputBuffer *buffer,
244312
{
245313
PyObject *obj;
246314
assert(buffer->writer != NULL);
247-
obj = PyBytesWriter_FinishWithSize(buffer->writer,
248-
buffer->allocated - avail_out);
315+
if (buffer->list == NULL) {
316+
obj = PyBytesWriter_FinishWithSize(buffer->writer,
317+
buffer->allocated - avail_out);
318+
buffer->writer = NULL;
319+
return obj;
320+
}
321+
322+
Py_ssize_t num = PyList_GET_SIZE(buffer->list);
323+
if (num == 1
324+
&& avail_out == PyBytes_GET_SIZE(PyList_GET_ITEM(buffer->list, 0)))
325+
{
326+
// the one block was never written to: the writer holds all the data
327+
obj = PyBytesWriter_FinishWithSize(buffer->writer, buffer->head_size);
328+
buffer->writer = NULL;
329+
Py_CLEAR(buffer->list);
330+
return obj;
331+
}
332+
333+
// join the writer's data and the blocks into one bytes object
334+
Py_ssize_t size = buffer->allocated - avail_out;
335+
obj = PyBytes_FromStringAndSize(NULL, size);
336+
if (obj == NULL) {
337+
PyErr_SetString(PyExc_MemoryError, unable_allocate_msg);
338+
return NULL; // the caller calls _BlocksOutputBuffer_OnError()
339+
}
340+
char *dst = PyBytes_AS_STRING(obj);
341+
memcpy(dst, PyBytesWriter_GetData(buffer->writer), buffer->head_size);
342+
dst += buffer->head_size;
343+
344+
for (Py_ssize_t i = 0; i < num; i++) {
345+
PyObject *block = PyList_GET_ITEM(buffer->list, i);
346+
Py_ssize_t block_size = PyBytes_GET_SIZE(block);
347+
if (i == num - 1) {
348+
// the last block holds avail_out unused bytes
349+
block_size -= avail_out;
350+
}
351+
memcpy(dst, PyBytes_AS_STRING(block), block_size);
352+
dst += block_size;
353+
}
354+
assert(dst == PyBytes_AS_STRING(obj) + size);
355+
356+
PyBytesWriter_Discard(buffer->writer);
249357
buffer->writer = NULL;
358+
Py_CLEAR(buffer->list);
250359
return obj;
251360
}
252361

@@ -256,6 +365,7 @@ _BlocksOutputBuffer_OnError(_BlocksOutputBuffer *buffer)
256365
{
257366
PyBytesWriter_Discard(buffer->writer);
258367
buffer->writer = NULL;
368+
Py_CLEAR(buffer->list);
259369
}
260370

261371
#ifdef __cplusplus

‎Lib/test/test_bz2.py‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1324,6 +1324,50 @@ def test_bzlib_version(self):
13241324
self.assertStartsWith(bz2.bzlib_version, '%d.%d.%d' % v)
13251325

13261326

1327+
class OutputBufferTest(unittest.TestCase):
1328+
# Outputs at and around the boundaries of the internal output buffer's
1329+
# blocks (Include/internal/pycore_blocks_output_buffer.h): the first four
1330+
# (32 KiB, 64 KiB, 256 KiB and 1 MiB) are one buffer grown by realloc();
1331+
# the next one (4 MiB) is a separate block on most platforms.
1332+
HEAD = (32 + 64 + 256 + 1024) * 1024
1333+
SIZES = [HEAD - 1, HEAD, HEAD + 1,
1334+
HEAD + 4 * 1024 * 1024 - 1, HEAD + 4 * 1024 * 1024,
1335+
HEAD + 4 * 1024 * 1024 + 1]
1336+
# a pattern every codec compresses quickly: 256 varied bytes per 4 KiB
1337+
PATTERN = bytes(range(256)) + bytes(4096 - 256)
1338+
1339+
@classmethod
1340+
def data(cls, size):
1341+
return (cls.PATTERN * (size // len(cls.PATTERN) + 1))[:size]
1342+
1343+
@classmethod
1344+
def setUpClass(cls):
1345+
cls.compressed = {size: bz2.compress(cls.data(size), 1)
1346+
for size in cls.SIZES}
1347+
1348+
def test_decompress(self):
1349+
for size in self.SIZES:
1350+
with self.subTest(size=size):
1351+
data = self.data(size)
1352+
self.assertEqual(bz2.decompress(self.compressed[size]), data)
1353+
1354+
def test_decompressor(self):
1355+
for size in self.SIZES:
1356+
with self.subTest(size=size):
1357+
data = self.data(size)
1358+
compressed = self.compressed[size]
1359+
self.assertEqual(
1360+
BZ2Decompressor().decompress(compressed), data)
1361+
# max_length past the first blocks and short of the next one
1362+
max_length = self.HEAD + 100 * 1024
1363+
d = BZ2Decompressor()
1364+
first = d.decompress(compressed, max_length)
1365+
self.assertEqual(len(first), min(size, max_length))
1366+
rest = b'' if d.eof else d.decompress(b'')
1367+
self.assertEqual(first + rest, data)
1368+
self.assertTrue(d.eof)
1369+
1370+
13271371
class TestModule(unittest.TestCase):
13281372
def test_deprecated_module_attributes(self):
13291373
support.check_deprecated_module_attributes(

‎Lib/test/test_gzip.py‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1337,5 +1337,28 @@ def test_decompress_cannot_have_flags_compression(self):
13371337
self.assertEqual(out, b'')
13381338

13391339

1340+
class TestOutputBuffer(unittest.TestCase):
1341+
# Outputs at and around the boundaries of the internal output buffer's
1342+
# blocks (Include/internal/pycore_blocks_output_buffer.h): the first four
1343+
# (32 KiB, 64 KiB, 256 KiB and 1 MiB) are one buffer grown by realloc();
1344+
# the next one (4 MiB) is a separate block on most platforms.
1345+
HEAD = (32 + 64 + 256 + 1024) * 1024
1346+
SIZES = [HEAD - 1, HEAD, HEAD + 1,
1347+
HEAD + 4 * 1024 * 1024 - 1, HEAD + 4 * 1024 * 1024,
1348+
HEAD + 4 * 1024 * 1024 + 1]
1349+
# a pattern every codec compresses quickly: 256 varied bytes per 4 KiB
1350+
PATTERN = bytes(range(256)) + bytes(4096 - 256)
1351+
1352+
@classmethod
1353+
def data(cls, size):
1354+
return (cls.PATTERN * (size // len(cls.PATTERN) + 1))[:size]
1355+
1356+
def test_decompress(self):
1357+
for size in self.SIZES:
1358+
with self.subTest(size=size):
1359+
data = self.data(size)
1360+
self.assertEqual(gzip.decompress(gzip.compress(data, 1)), data)
1361+
1362+
13401363
if __name__ == "__main__":
13411364
unittest.main()

‎Lib/test/test_lzma.py‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2214,5 +2214,49 @@ def test_filter_properties_roundtrip(self):
22142214
)
22152215

22162216

2217+
class OutputBufferTestCase(unittest.TestCase):
2218+
# Outputs at and around the boundaries of the internal output buffer's
2219+
# blocks (Include/internal/pycore_blocks_output_buffer.h): the first four
2220+
# (32 KiB, 64 KiB, 256 KiB and 1 MiB) are one buffer grown by realloc();
2221+
# the next one (4 MiB) is a separate block on most platforms.
2222+
HEAD = (32 + 64 + 256 + 1024) * 1024
2223+
SIZES = [HEAD - 1, HEAD, HEAD + 1,
2224+
HEAD + 4 * 1024 * 1024 - 1, HEAD + 4 * 1024 * 1024,
2225+
HEAD + 4 * 1024 * 1024 + 1]
2226+
# a pattern every codec compresses quickly: 256 varied bytes per 4 KiB
2227+
PATTERN = bytes(range(256)) + bytes(4096 - 256)
2228+
2229+
@classmethod
2230+
def data(cls, size):
2231+
return (cls.PATTERN * (size // len(cls.PATTERN) + 1))[:size]
2232+
2233+
@classmethod
2234+
def setUpClass(cls):
2235+
cls.compressed = {size: lzma.compress(cls.data(size), preset=0)
2236+
for size in cls.SIZES}
2237+
2238+
def test_decompress(self):
2239+
for size in self.SIZES:
2240+
with self.subTest(size=size):
2241+
data = self.data(size)
2242+
self.assertEqual(lzma.decompress(self.compressed[size]), data)
2243+
2244+
def test_decompressor(self):
2245+
for size in self.SIZES:
2246+
with self.subTest(size=size):
2247+
data = self.data(size)
2248+
compressed = self.compressed[size]
2249+
self.assertEqual(
2250+
LZMADecompressor().decompress(compressed), data)
2251+
# max_length past the first blocks and short of the next one
2252+
max_length = self.HEAD + 100 * 1024
2253+
d = LZMADecompressor()
2254+
first = d.decompress(compressed, max_length)
2255+
self.assertEqual(len(first), min(size, max_length))
2256+
rest = b'' if d.eof else d.decompress(b'')
2257+
self.assertEqual(first + rest, data)
2258+
self.assertTrue(d.eof)
2259+
2260+
22172261
if __name__ == "__main__":
22182262
unittest.main()

0 commit comments

Comments
 (0)