Optimize BytesIO to do less reallocations when written, similarly to StringIO

[elibendersky]

BPO	15381
Nosy	@ncoghlan, @pitrou, @scoder, @vstinner, @benjaminp, @meadori, @berkerpeksag, @hynek, @dw, @serhiy-storchaka
Files	bytesio_resized_bytes-2.patch bytesio_resized_bytes-3.patch bytesio_resized_bytes-4.patch bytesio_faster_readline.patch bytesio_resized_bytes-5.patch bytesio_resized_bytes-6.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/serhiy-storchaka'
closed_at = None
created_at = <Date 2012-07-17.12:12:45.969>
labels = ['library', 'performance']
title = 'Optimize BytesIO to do  less reallocations when written, similarly to StringIO'
updated_at = <Date 2019-03-15.22:56:18.774>
user = 'https://bugs.python.org/elibendersky'

bugs.python.org fields:

activity = <Date 2019-03-15.22:56:18.774>
actor = 'BreamoreBoy'
assignee = 'serhiy.storchaka'
closed = False
closed_date = None
closer = None
components = ['Library (Lib)']
creation = <Date 2012-07-17.12:12:45.969>
creator = 'eli.bendersky'
dependencies = []
files = ['26461', '32536', '36180', '36369', '36371', '37939']
hgrepos = []
issue_num = 15381
keywords = ['patch']
message_count = 47.0
messages = ['165715', '165716', '165718', '165748', '165760', '165780', '165795', '165883', '165884', '165901', '165935', '165937', '165976', '165977', '165978', '165979', '165980', '165981', '165995', '166005', '166007', '166008', '166043', '171205', '202374', '203034', '203045', '224409', '225272', '225274', '225276', '225295', '225298', '225306', '225311', '225316', '225317', '225318', '234885', '235103', '235326', '235339', '235340', '235353', '236003', '236007', '236011']
nosy_count = 17.0
nosy_names = ['ncoghlan', 'pitrou', 'scoder', 'vstinner', 'benjamin.peterson', 'stutzbach', 'Arfrever', 'eli.bendersky', 'meador.inge', 'tshepang', 'python-dev', 'jcon', 'berker.peksag', 'hynek', 'dw', 'serhiy.storchaka', 'kmike']
pr_nums = []
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue15381'
versions = ['Python 3.5']

[elibendersky]

From this pydev thread: http://mail.python.org/pipermail/python-dev/2012-July/120981.html

"BytesIO is actually missing an optimisation that is already used in
StringIO: the StringIO C implementation uses a fragment accumulator
internally, and collapses that into a single string object when
getvalue() is called. BytesIO is still using the old
"resize-the-buffer-as-you-go" strategy, and thus ends up repeatedly
reallocating the buffer as the data sequence grows incrementally.

It should be optimised to work the same way StringIO does (which is
effectively the same way that the monkeypatched version works)"

[elibendersky]

This optimization for StringIO was done in issue bpo-13149

[serhiy-storchaka]

I am not see that BytesIO is slower than StringIO (both are about 30% slower than append/join).

$ ./python -m timeit -s "import io; d=[b'a'*10,b'bb'*5,b'ccc'*5]*1000"  "b=[]; w=b.append"  "for x in d: w(x)"  "b''.join(b)"
1000 loops, best of 3: 966 usec per loop

$ ./python -m timeit -s "import io; d=['a'*10,'bb'*5,'ccc'*5]*1000"  "b=[]; w=b.append"  "for x in d: w(x)"  "''.join(b)"
1000 loops, best of 3: 918 usec per loop

$ ./python -m timeit -s "import io; d=[b'a'*10,b'bb'*5,b'ccc'*5]*1000"  "b=io.BytesIO(); w=b.write"  "for x in d: w(x)"  "b.getvalue()"
1000 loops, best of 3: 1.22 msec per loop

$ ./python -m timeit -s "import io; d=['a'*10,'bb'*5,'ccc'*5]*1000"  "b=io.StringIO(); w=b.write"  "for x in d: w(x)"  "b.getvalue()"
1000 loops, best of 3: 1.24 msec per loop

[elibendersky]

I wonder if this is a fair comparison, Serhiy. Strings are unicode underneath, so they have a large overhead per string (more data to copy around). Increasing the length of the strings changes the game because due to PEP-393, the overhead for ASCII-only Unicode strings is constant:

>>> import sys
>>> sys.getsizeof('a')
50
>>> sys.getsizeof(b'a')
34
>>> sys.getsizeof('a' * 1000)
1049
>>> sys.getsizeof(b'a' * 1000)
1033
>>> 

When re-running your tests with larger chunks, the results are quite interesting:

$ ./python -m timeit -s "import io; d=[b'a'*100,b'bb'*50,b'ccc'*50]*1000"  "b=io.BytesIO(); w=b.write"  "for x in d: w(x)"  "b.getvalue()"
1000 loops, best of 3: 509 usec per loop
$ ./python -m timeit -s "import io; d=['a'*100,'bb'*50,'ccc'*50]*1000"  "s=io.StringIO(); w=s.write"  "for x in d: w(x)"  "s.getvalue()"
1000 loops, best of 3: 282 usec per loop

So, it seems to me that BytesIO could use some optimization!

[elibendersky]

I'd like to take a shot at this, if Antoine doesn't mind. I'll prepare a patch for bytesio.c

Question: what set of benchmarks would it be good to run to make sure this doesn't degrade the performance of BytesIO in various cases?

[serhiy-storchaka]

I wonder if this is a fair comparison, Serhiy.

I just used your examples.

When re-running your tests with larger chunks, the results are quite interesting:

Well, now I see, that BytesIO slower StringIO.

[serhiy-storchaka]

Here is a preliminary version of the patch. I am not sure that it is fully correct.

Microbenchmark results:

$ ./python -m timeit -s "import io; n=100; d=['a'*n,'bb'*n,'ccc'*n]*10000"  "s=io.StringIO(); w=s.write"  "for x in d: w(x)"  "s.getvalue()"
10 loops, best of 3: 25.5 msec per loop
$ ./python -m timeit -s "import io; n=100; d=[b'a'*n,b'bb'*n,b'ccc'*n]*10000"  "s=io.BytesIO(); w=s.write"  "for x in d: w(x)"  "s.getvalue()"
10 loops, best of 3: 39.9 msec per loop
$ ./python-patched -m timeit -s "import io; n=100; d=[b'a'*n,b'bb'*n,b'ccc'*n]*10000"  "s=io.BytesIO(); w=s.write"  "for x in d: w(x)"  "s.getvalue()"
10 loops, best of 3: 26.1 msec per loop

$ ./python -m timeit -s "import io; n=1000; d=['a'*n,'bb'*n,'ccc'*n]*1000"  "s=io.StringIO(); w=s.write"  "for x in d: w(x)"  "s.getvalue()"
100 loops, best of 3: 12.1 msec per loop
$ ./python -m timeit -s "import io; n=1000; d=[b'a'*n,b'bb'*n,b'ccc'*n]*1000"  "s=io.BytesIO(); w=s.write"  "for x in d: w(x)"  "s.getvalue()"
10 loops, best of 3: 26.5 msec per loop
$ ./python-patched -m timeit -s "import io; n=1000; d=[b'a'*n,b'bb'*n,b'ccc'*n]*1000"  "s=io.BytesIO(); w=s.write"  "for x in d: w(x)"  "s.getvalue()"
100 loops, best of 3: 13.6 msec per loop

[pitrou]

Here is a preliminary version of the patch.

I don't understand the purpose of your patch. It just replaces a direct realloc() call with an indirect one (since _PyBytes_Resize() will call realloc() internally).

[pitrou]

> Here is a preliminary version of the patch.

I don't understand the purpose of your patch. It just replaces a
direct realloc() call with an indirect one (since _PyBytes_Resize()
will call realloc() internally).

Ok, I understand. You're trying to make the getvalue() call cheaper,
right?

[serhiy-storchaka]

Ok, I understand. You're trying to make the getvalue() call cheaper,
right?

Yes, it saves up to half of time on large data (on Linux). It would be
interesting to see the results of these microbenchmarks on Windows.

[pitrou]

There seems to be a problem with the patch: when you store the getvalue() result somewhere (instead of discarding it), things get much slower:

$ ./python -m timeit -s "import io; n=2000; d=[b'a'*n,b'bb'*n,b'ccc'*n]*1000"  "s=io.BytesIO(); w=s.write"  "for x in d: w(x)"  "s.getvalue()"
1000 loops, best of 3: 913 usec per loop

$ ./python -m timeit -s "import io; n=2000; d=[b'a'*n,b'bb'*n,b'ccc'*n]*1000"  "s=io.BytesIO(); w=s.write"  "for x in d: w(x)"  "global y; y = s.getvalue()"
100 loops, best of 3: 4.67 msec per loop

This does not happen without the patch.

[pitrou]

Under Windows (64-bit Windows 7 on a VirtualBox VM), the patch increases performance slightly but not as much as under Linux:

-> before patch:

C:\t\cpython>pc\VS9.0\amd64\python.exe -m timeit -s "import io; n=2000; d=[b'a'*
n,b'bb'*n,b'ccc'*n]*1000" "s=io.BytesIO(); w=s.write" "for x in d: w(x)" "s.g
etvalue()"
10 loops, best of 3: 49.2 msec per loop

-> after patch:

C:\t\cpython>pc\VS9.0\amd64\python.exe -m timeit -s "import io; n=2000; d=[b'a'*
n,b'bb'*n,b'ccc'*n]*1000" "s=io.BytesIO(); w=s.write" "for x in d: w(x)" "s.g
etvalue()"
10 loops, best of 3: 41.7 msec per loop

And the join() approach is 10x faster (!):

C:\t\cpython>pc\VS9.0\amd64\python.exe -m timeit -s "import io; n=2000; d=[b'a'*
n,b'bb'*n,b'ccc'*n]*1000" "b''.join(d)"
100 loops, best of 3: 4.63 msec per loop

... which points to a much less optimized realloc() under Windows.

[serhiy-storchaka]

The patch updated. Fixed some errors, optimized initialization, added checks and comments. I think that now the patch is ready for review.

[serhiy-storchaka]

There seems to be a problem with the patch: when you store the getvalue() result somewhere (instead of discarding it), things get much slower:

This problem exists with the new patch?

[serhiy-storchaka]

Under Windows (64-bit Windows 7 on a VirtualBox VM), the patch increases performance slightly but not as much as under Linux:

Thank you, Antoine. This is an expected result.

And the join() approach is 10x faster (!):
C:\t\cpython>pc\VS9.0\amd64\python.exe -m timeit -s "import io; n=2000; d=[b'a'*
n,b'bb'*n,b'ccc'*n]*1000" "b''.join(d)"
100 loops, best of 3: 4.63 msec per loop

To be fair, test body should be: "s=[]; w=s.append" "for x in d: w(x)" "b''.join(s)"

May be tuning resize strategy (overallocate not 1/8, but 1/4, 1/2, or 100%) can help.

[pitrou]

> There seems to be a problem with the patch: when you store the
getvalue() result somewhere (instead of discarding it), things get
much slower:

This problem exists with the new patch?

I think you can run the benchmark yourself (I ran it under Linux).

[serhiy-storchaka]

I think you can run the benchmark yourself (I ran it under Linux).

I don't see any differences.

[pitrou]

Well, with the latest patch I get:

$ ./python -m timeit -s "import io; n=2000; d=[b'a'*n,b'bb'*n,b'ccc'*n]*1000"  "s=io.BytesIO(); w=s.write"  "for x in d: w(x)"  "s.getvalue()"
1000 loops, best of 3: 982 usec per loop

$ ./python -m timeit -s "import io; n=2000; d=[b'a'*n,b'bb'*n,b'ccc'*n]*1000"  "s=io.BytesIO(); w=s.write"  "for x in d: w(x)"  "global y; y = s.getvalue()"
100 loops, best of 3: 4.79 msec per loop

[serhiy-storchaka]

Hmm. Without the ability to reproduce this effect, it will be difficult for me to
get rid of him. What times for StringIO, append/join, unpatched BytesIO? Do
this happen with a little different numbers (n=1500, 1600,...,3000)?

[pitrou]

Hmm. Without the ability to reproduce this effect, it will be difficult for me to
get rid of him.

It's under 64-bit Linux, Intel Core i5 CPU. Are you sure you're testing
in non-debug mode?

That said, the numbers under Windows suggest me that Eli's original idea
(append and then join at the end) would be more robust.

[pitrou]

By the way, here is Matt Mackall's take on realloc():

http://www.selenic.com/pipermail/mercurial-devel/2011-October/034988.html

[pitrou]

StringIO:

$ ./python -m timeit -s "import io; n=2000; d=['a'*n,'bb'*n,'ccc'*n]*1000"  "s=io.StringIO(); w=s.write"  "for x in d: w(x)"  "global y; y = s.getvalue()"

-> Linux: 1000 loops, best of 3: 985 usec per loop
-> Windows: 100 loops, best of 3: 4.26 msec per loop

Unpatched BytesIO:

$ ./python -m timeit -s "import io; n=2000; d=[b'a'*n,b'bb'*n,b'ccc'*n]*1000"  "s=io.BytesIO(); w=s.write"  "for x in d: w(x)"  "global y; y = s.getvalue()"

-> Linux: 100 loops, best of 3: 2.44 msec per loop
-> Windows: 10 loops, best of 3: 38.4 msec per loop

b''.join():

$ ./python -m timeit -s "import io; n=2000; d=[b'a'*n,b'bb'*n,b'ccc'*n]*1000"  "l = list(d)"  "global y; y = b''.join(l)"

-> Linux: 1000 loops, best of 3: 821 usec per loop
-> Windows: 100 loops, best of 3: 4.09 msec per loop

bytearray:

$ ./python -m timeit -s "import io; n=2000; d=[b'a'*n,b'bb'*n,b'ccc'*n]*1000"  "b = bytearray()" "for x in d: b += x" "global y; y = b"

-> Linux: 1000 loops, best of 3: 834 usec per loop
-> Windows: 10 loops, best of 3: 37.8 msec per loop

[serhiy-storchaka]

It's under 64-bit Linux, Intel Core i5 CPU. Are you sure you're testing
in non-debug mode?

I use 32-bit Linux.

That said, the numbers under Windows suggest me that Eli's original idea
(append and then join at the end) would be more robust.

I agree, it would be more robust, but much more complex solution. I will try to implement this approach too. Victor Stinner in their experiments with formatting preferred
overallocation approach (_PyUnicodeWriter), therefore, the solution probably will be a hybrid.

However, even in itself the patch deserves attention. It not only significant speeds up writing under Linux, but also speeds up the initialization, which leads to faster reading.

./python -m timeit -s "import io; d=(b'a'*99+b'\n')*10000" "s=io.BytesIO(d); r=s.readline" "while r(): pass"

Unpatched: 100 loops, best of 3: 5.92 msec per loop
Patched: 100 loops, best of 3: 3.95 msec per loop

I will try to preserve this advantage.

By the way, here is Matt Mackall's take on realloc():

Note, that list also uses realloc() inside and therefore you get the same behavior with other constant factor. Actually, appending to a list less than sizeof(void*) bytes at a
time you will run into this sooner. Perhaps this is the cause that append/join approach under Windows slower than under Linux.

Thank you for measurements, this shows the scale of the issue.

[vstinner]

See also issue bpo-15612 for a possible optimization on StringIO (use _PyUnicodeWriter).

[serhiy-storchaka]

Updated patch uses large overallocation factor (1/2 instead 1/8), it may increase the speed on Windows. Fixed implementation of __sizeof__() and some minor bugs.

[serhiy-storchaka]

Only one week left before feature freeze. Please benchmark this patch on Windows.

[vstinner]

Only one week left before feature freeze.

This issue is an optimization, not a new feature.

[serhiy-storchaka]

Synchronized with tip. Unfortunately there are no common points with recent bpo-22003 changes so they should be reverted (except tests).

[serhiy-storchaka]

What should be made to move this issue forward?

[dw]

Hey Serhiy,

The implementation for your readline optimization seems less contentious (and less risky) than the remainder of the patch -- it could perhaps be easily split off into a separate patch, which may be far more easily committed.

I love the concept of this patch, although from my last reading (weeks ago), it's slightly scary that it relies on Py_REFCNT() to know whether to mutate a string or not. In principle this should never break, in practice, however, it is uncertain that there are no strange edge cases that aren't immediately obvious.

The _PyBytes_Resize doc is quite clear: "Only use this to build up a brand new bytes object; don’t use this if the bytes may already be known in other parts of the code"

[ncoghlan]

It wouldn't be the first time we've used Py_REFCNT that way. We do it with tuples and normal strings as well.

[serhiy-storchaka]

Here is a patch which optimizes readline() and readlines() methods of BytesIO and the __next__() method of BytesIO iterator.

[pitrou]

I suppose this takes advantage of the libc's optimized memchr(). Any benchmarks?
(patch looks fine, by the way)

[serhiy-storchaka]

Benchmark from bpo-22003:

$ ./python0 -m timeit -s 'import i' 'i.readlines()'

Before patch: 10 loops, best of 3: 36.1 msec per loop
After patch: 10 loops, best of 3: 27.5 msec per loop

[python-dev]

New changeset 601045ceff94 by Serhiy Storchaka in branch 'default':
Issue bpo-15381: Optimized line reading in io.BytesIO.
http://hg.python.org/cpython/rev/601045ceff94

[serhiy-storchaka]

Updated patch without just committed line reading optimization and committed in bpo-22193 the _PySys_GetSizeOf() function.

[pitrou]

Can you post any benchmark?
Also, if you wouldn't change the resizing factor it would make it easier to compare the two approaches on their own merits, IMO.

[serhiy-storchaka]

I posted benchmarks two years ago, in msg165795. Here are updated results:

$ ./python -m timeit -s "import io; n=100; d=[b'a'*n,b'bb'*n,b'ccc'*n]*10000"  "s=io.BytesIO(); w=s.write"  "for x in d: w(x)"  "s.getvalue()"

Before patch: 10 loops, best of 3: 42.3 msec per loop
After patch: 10 loops, best of 3: 27.6 msec per loop

$ ./python -m timeit -s "import io; n=1000; d=[b'a'*n,b'bb'*n,b'ccc'*n]*1000"  "s=io.BytesIO(); w=s.write"  "for x in d: w(x)"  "s.getvalue()"

Before patch: 10 loops, best of 3: 28.7 msec per loop
After patch: 100 loops, best of 3: 14.8 msec per loop

They don't depend from the resizing factor on Linux. I increased it in hope it will help on Windows.

[serhiy-storchaka]

Ping.

[serhiy-storchaka]

Updated patch addresses Antoine's comment.

[python-dev]

New changeset 2e29d54843a4 by Serhiy Storchaka in branch 'default':
Issue bpo-15381: Optimized io.BytesIO to make less allocations and copyings.
https://hg.python.org/cpython/rev/2e29d54843a4

[serhiy-storchaka]

Some buildbots crash:

http://buildbot.python.org/all/builders/x86%20Ubuntu%20Shared%203.x/builds/11152/steps/test/logs/stdio
http://buildbot.python.org/all/builders/AMD64%20Debian%20PGO%203.x/builds/4/steps/test/logs/stdio
http://buildbot.python.org/all/builders/AMD64%20Debian%20root%203.x/builds/1715/steps/test/logs/stdio
http://buildbot.python.org/all/builders/AMD64%20Solaris%2011%20%5BSB%5D%203.x/builds/3836/steps/test/logs/stdio

E.g.:

Fatal Python error: Objects/frameobject.c:429 object at 0x406dd878 has negative ref count -5

Current thread 0x40525ce0 (most recent call first):
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/unittest/case.py", line 605 in run
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/unittest/case.py", line 625 in __call__
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/unittest/suite.py", line 122 in run
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/unittest/suite.py", line 84 in __call__
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/unittest/suite.py", line 122 in run
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/unittest/suite.py", line 84 in __call__
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/unittest/suite.py", line 122 in run
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/unittest/suite.py", line 84 in __call__
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/unittest/runner.py", line 168 in run
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/test/support/init.py", line 1770 in _run_suite
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/test/support/init.py", line 1804 in run_unittest
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/test/regrtest.py", line 1283 in test_runner
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/test/regrtest.py", line 1284 in runtest_inner
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/test/regrtest.py", line 967 in runtest
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/test/regrtest.py", line 763 in main
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/test/regrtest.py", line 1568 in main_in_temp_cwd
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/test/main.py", line 3 in <module>
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/runpy.py", line 85 in _run_code
File "/srv/buildbot/buildarea/3.x.bolen-ubuntu/build/Lib/runpy.py", line 170 in _run_module_as_main
Aborted
make: *** [buildbottest] Error 134

Trying to reproduce locally and investigate.

[python-dev]

New changeset 3fdbdf4d2ac7 by Serhiy Storchaka in branch 'default':
Issue bpo-15381: Try to fix refcount bug. Empty and 1-byte buffers are always shared.
https://hg.python.org/cpython/rev/3fdbdf4d2ac7

[python-dev]

New changeset ea33b61cac74 by Serhiy Storchaka in branch 'default':
Issue bpo-15381: Fixed a bug in BytesIO.write().
https://hg.python.org/cpython/rev/ea33b61cac74

[berkerpeksag]

Can this be closed now?

[serhiy-storchaka]

No, I'm working on more advanced patch.

[BreamoreBoy]

Oh, Berker, please stop shaking up bug tracker.

[iritkatriel]

No, I'm working on more advanced patch.

@serhiy-storchaka are you still planning to work on this?