classification
Title: replace_interleave can be optimized for single character byte strings
Type: performance Stage:
Components: Library (Lib) Versions: Python 3.6
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Josh Snider, haypo, python-dev, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2016-03-16 23:28 by Josh Snider, last changed 2016-03-21 10:39 by haypo. This issue is now closed.

Files
File name Uploaded Description Edit
bytes.patch Josh Snider, 2016-03-16 23:28 review
bytes-2.patch Josh Snider, 2016-03-17 00:43 review
bench.py haypo, 2016-03-21 09:39
Messages (8)
msg261870 - (view) Author: Josh Snider (Josh Snider) * Date: 2016-03-16 23:28
replace_interleave in Objects/bytesobject.c and Objects/bytearrayobject.c can be optimized for the special case where the interleaving byte string is a single character.

Here's some quick results from timeit showing that it's about three times faster for the special case.
* Before (cold start):
>>> timeit.timeit('(b"x" * 2000000).replace(b"", b".")', number=1000)
7.619218342995737
* After (cold start):
>>> timeit.timeit('(b"x" * 2000000).replace(b"", b".")', number=1000)
2.7605581780080684

For the non-special case, running timeit.timeit('(b"x" * 2000000).replace(b"", b".0")', number=10000) takes ~173 seconds on both versions.
msg261871 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2016-03-16 23:45
I reviewed your patch on Rietveld (you should get an email notification).
msg261873 - (view) Author: Josh Snider (Josh Snider) * Date: 2016-03-17 00:43
Addresses review comments.
msg262111 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2016-03-21 09:39
I wrote a microbenchmark with my benchmark.py tool.

The patch always make bytes.replace(b'', char) and bytearray.replace(b'', char) faster even for strings of 10 bytes, the speedup on string of 1000 bytes or more is very interesting, even I never used this Python instruction :-)

-------------+-------------+---------------
type bytes   |        orig |          patch
-------------+-------------+---------------
length=10    |  250 ns (*) |  211 ns (-15%)
length=10**3 | 4.67 us (*) | 1.07 us (-77%)
length=10**5 |  441 us (*) | 78.2 us (-82%)
-------------+-------------+---------------
Total        |  446 us (*) | 79.5 us (-82%)
-------------+-------------+---------------

---------------+-------------+---------------
type bytearray |        orig |          patch
---------------+-------------+---------------
length=10      |  266 ns (*) |  224 ns (-16%)
length=10**3   | 4.67 us (*) | 1.08 us (-77%)
length=10**5   |  441 us (*) | 78.3 us (-82%)
---------------+-------------+---------------
Total          |  446 us (*) | 79.6 us (-82%)
---------------+-------------+---------------

---------------+------------+---------------
Summary        |       orig |          patch
---------------+------------+---------------
type bytes     | 446 us (*) | 79.5 us (-82%)
type bytearray | 446 us (*) | 79.6 us (-82%)
---------------+------------+---------------
Total          | 892 us (*) |  159 us (-82%)
---------------+------------+---------------
msg262112 - (view) Author: Roundup Robot (python-dev) Date: 2016-03-21 09:39
New changeset 62e3b7af0697 by Victor Stinner in branch 'default':
Optimize bytes.replace(b'', b'.')
https://hg.python.org/cpython/rev/62e3b7af0697
msg262113 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2016-03-21 09:40
I pushed my latest patches, thanks for your contribution Josh.
msg262114 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-03-21 10:32
Is it worth to optimize this pretty rare special case?
msg262115 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2016-03-21 10:39
> Is it worth to optimize this pretty rare special case?

There was a TODO in the code, so I guess that the author wanted to write specialized code for 1-char replacement. Since the patch is short (adds 8 lines of C code), I consider that it's ok to optimize it.
History
Date User Action Args
2016-03-21 10:39:44hayposetmessages: + msg262115
2016-03-21 10:32:03serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg262114
2016-03-21 09:40:19hayposetstatus: open -> closed
resolution: fixed
messages: + msg262113
2016-03-21 09:39:52python-devsetnosy: + python-dev
messages: + msg262112
2016-03-21 09:39:25hayposetfiles: + bench.py

messages: + msg262111
2016-03-17 00:43:02Josh Snidersetfiles: + bytes-2.patch

messages: + msg261873
2016-03-16 23:45:26hayposetnosy: + haypo
messages: + msg261871
2016-03-16 23:28:10Josh Snidercreate