classification
Title: Optimize str%tuple for the PEP 393
Type: performance Stage:
Components: Versions: Python 3.3
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: kristjan.jonsson, loewis, pitrou, python-dev, serhiy.storchaka, vstinner
Priority: normal Keywords: patch

Created on 2012-04-28 00:47 by vstinner, last changed 2012-05-03 21:42 by vstinner. This issue is now closed.

Files
File name Uploaded Description Edit
pyunicode_format-2.patch vstinner, 2012-04-30 01:10 review
pyunicode_format_writer.patch vstinner, 2012-05-02 23:42 review
Messages (23)
msg159508 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2012-04-28 00:47
PyUnicode_Format() creates short temporary substrings. Attached patch tries to avoid substrings. For example, it avoids write of 1 character and repetition of 1 character like a space. PyUnicode_Format() now works in two steps:

 - computes the maximum character and the length of the output string
 - write characters into the output string

I'm not sure that my patch is correct, nor that the change does really speed-up Python.


Benchmark:

./python -m timeit \
  -s 's="x=%s, y=%u, z=%x"; args=(123, 456, 789)' \
  's%args'
./python -m timeit \
  -s 's="The %(k1)s is %(k2)s the %(k3)s."; args={"k1":"x","k2":"y","k3":"z",}' \
  's%args'

Python 3.2:

1000000 loops, best of 3: 0.482 usec per loop
1000000 loops, best of 3: 0.295 usec per loop

Python 3.3:

1000000 loops, best of 3: 0.653 usec per loop
1000000 loops, best of 3: 0.666 usec per loop

Python 3.3 + patch:

1000000 loops, best of 3: 0.596 usec per loop
1000000 loops, best of 3: 0.566 usec per loop
msg159529 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-04-28 17:19
I see sped up +10% on Intel Atom (but 3.2 still 2x fast).

With non-ascii arguments speed up can be a little bit larger.
msg159663 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2012-04-30 01:10
Updated patch:
 - use also PyUnicode_Kind for kind and fmtkind
 - fix compiler warnings
 - initialize data outside the loop
 - avoid duplicate PyUnicode_READ() where it is possible
 - minor code cleanup
msg159664 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2012-04-30 03:25
New changeset 42fbb4f9b540 by Victor Stinner in branch 'default':
Issue #14687: Cleanup PyUnicode_Format()
http://hg.python.org/cpython/rev/42fbb4f9b540

New changeset 08b54c635586 by Victor Stinner in branch 'default':
Issue #14687: Avoid an useless duplicated string in PyUnicode_Format()
http://hg.python.org/cpython/rev/08b54c635586
msg159768 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2012-05-01 23:19
New changeset 4b98ce6ef95e by Victor Stinner in branch 'default':
Issue #14687: Optimize str%args
http://hg.python.org/cpython/rev/4b98ce6ef95e

New changeset a966f9311ebb by Victor Stinner in branch 'default':
Issue #14687: Cleanup PyUnicode_Format()
http://hg.python.org/cpython/rev/a966f9311ebb
msg159822 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2012-05-02 23:42
pyunicode_format_writer.patch: a new completly different approach. It's an optimistic patch: start with a short ASCII buffer, and grows slowly the buffer, and convert to UCS2 and maybe to UCS4 if needed. The UTF-8 decoder is based on the same idea.

The patch adds a "unicode writer", the optimistic writer. It overallocates the buffer by 50% to limit the number of calls to PyUnicode_Resize(). It may be reused by other functions.

My dummy benchmark script:
------------
$ cat ~/bench.sh 
./python -m timeit \
    -s 'fmt="%s:"; arg="abc"' \
    'fmt % arg'
./python -m timeit \
    -s 'N=200; L=3; fmt="%s"*N; args=("a"*L,)*N' \
    'fmt % args'
./python -m timeit \
    -s 's="x=%s, y=%u, z=%x"; args=(123, 456, 789)' \
    's%args'
./python -m timeit \
    -s 's="The %(k1)s is %(k2)s the %(k3)s."; args={"k1":"x","k2":"y","k3":"z",}' \
    's%args'
------------

Results.

Python 3.2:

10000000 loops, best of 3: 0.0916 usec per loop
100000 loops, best of 3: 4.04 usec per loop
1000000 loops, best of 3: 0.492 usec per loop
1000000 loops, best of 3: 0.305 usec per loop

Python 3.3:

10000000 loops, best of 3: 0.169 usec per loop
100000 loops, best of 3: 8.02 usec per loop
1000000 loops, best of 3: 0.648 usec per loop
1000000 loops, best of 3: 0.658 usec per loop

Python 3.3 optimist (compared to 3.3):

10000000 loops, best of 3: 0.123 usec per loop (-27%)
100000 loops, best of 3: 5.73 usec per loop (-29%)
1000000 loops, best of 3: 0.466 usec per loop (-28%)
1000000 loops, best of 3: 0.454 usec per loop (-31%)

Overhead of the PEP 393 (Python 3.2 => 3.3) without -> with the patch:

 * 85% -> 35%
 * 99% -> 41%
 * 31% -> -5% (Python 3.3 is *faster* on this specific case! maybe thanks to f4837725c50f)
 * 115% -> 49%

--

"%(name)s" syntax is still *much* slower than Python 3.2, I don't understand why.

Parameters of the Unicode writer (overallocation factor and initial size) may be adjusted (later?) for better performances.
msg159824 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2012-05-02 23:46
New changeset 90b4c2d7c90d by Victor Stinner in branch 'default':
Issue #14687: Optimize str%tuple for the "%(name)s" syntax
http://hg.python.org/cpython/rev/90b4c2d7c90d
msg159831 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2012-05-03 01:41
> Parameters of the Unicode writer (overallocation factor
> and initial size) may be adjusted (later?) for better performances.

I tried to compute the initial size from the args object. It is hard because we don't know how arguments are used. For example, an argument may not be a number formatted  as decimal, but the width of an argument. Another example: "%.3s" may be used to only read the 3 first characters of a very long string.

So I consider that it is *simpler and safer* to not guess anything from args, but only choose correctly the overallocation factor. I tried the following factors: 1 (no overallocation), 1.25, 1.5 and 2.0. It looks like 1.25 (pos*5/4) is the best compromise and offers the best performances.
msg159846 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2012-05-03 10:34
New changeset 830eeff4fe8f by Victor Stinner in branch 'default':
Issue #14624, #14687: Optimize unicode_widen()
http://hg.python.org/cpython/rev/830eeff4fe8f
msg159849 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2012-05-03 11:12
Results on 32 bits (Intel Core i5 CPU 661 @ 3.33GHz) on Linux 3.0 with a new patch.

Python 3.2:
 
10000000 loops, best of 3: 0.133 usec per loop
100000 loops, best of 3: 4.64 usec per loop
1000000 loops, best of 3: 0.637 usec per loop
1000000 loops, best of 3: 0.364 usec per loop

Python 3.3 @ 1439e2d1f490 (before my first optimization on str%tuple):

10000000 loops, best of 3: 0.193 usec per loop
100000 loops, best of 3: 10.1 usec per loop
1000000 loops, best of 3: 0.838 usec per loop
1000000 loops, best of 3: 0.825 usec per loop

Python 3.3 + patch, overallocate 50%:

10000000 loops, best of 3: 0.15 usec per loop
100000 loops, best of 3: 8.27 usec per loop
1000000 loops, best of 3: 0.527 usec per loop
1000000 loops, best of 3: 0.566 usec per loop

Python 3.3 + patch, overallocate 25%:

10000000 loops, best of 3: 0.142 usec per loop
100000 loops, best of 3: 7.93 usec per loop
1000000 loops, best of 3: 0.532 usec per loop
1000000 loops, best of 3: 0.546 usec per loop

I'm going to commit the new patch with an overallocation of 25%.
msg159850 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2012-05-03 11:16
New changeset f1db931b93d3 by Victor Stinner in branch 'default':
Issue #14687: str%tuple now uses an optimistic "unicode writer" instead of an
http://hg.python.org/cpython/rev/f1db931b93d3
msg159851 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-05-03 11:31
> Results on 32 bits (Intel Core i5 CPU 661 @ 3.33GHz) on Linux 3.0 with
> a new patch.

It would be nice to have measurements under Windows.
msg159852 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2012-05-03 11:43
New changeset 0a9143d7b097 by Victor Stinner in branch 'default':
Issue #14687: Cleanup unicode_writer_prepare()
http://hg.python.org/cpython/rev/0a9143d7b097
msg159854 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-05-03 12:15
> It would be nice to have measurements under Windows.

The differences between 32-bit Linux and 32-bit Windows should not be.
But 64-bit can be different, and 64-bit Linux and 64-bit Windows can
vary from 32-bit, and from each other. There are also differences
between high-end Intel Core and low-end Intel Atom, and AMD processors.
msg159855 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-05-03 12:25
> > It would be nice to have measurements under Windows.
> 
> The differences between 32-bit Linux and 32-bit Windows should not be.

The Windows memory allocator is quite different from the glibc's, so the
overallocation / resizing approach may play differently.
msg159856 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-05-03 12:26
> Results on 32 bits (Intel Core i5 CPU 661 @ 3.33GHz) on Linux 3.0 with a new patch.

Your tests only for ascii. You should also see some of corner cases --
a large format string and a few small arguments (templating),
a small simple format string and one large argument
(idiomatic `'[%s]' % ', '.join(long_list)`).
msg159867 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2012-05-03 17:28
New changeset f58159e5d52f by Victor Stinner in branch 'default':
Issue #14687: Remove redundant length attribute of unicode_write_t
http://hg.python.org/cpython/rev/f58159e5d52f
msg159869 - (view) Author: Kristján Valur Jónsson (kristjan.jonsson) * (Python committer) Date: 2012-05-03 19:30
Do you think that this optimization is relevant to 2.7?
In that case, it might be worthwhile for me to backport it to our EVE branch...
msg159872 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-05-03 20:21
> Do you think that this optimization is relevant to 2.7?

No, this is just an attempt to deal with the shortcomings of PEP 393.
msg159874 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2012-05-03 21:25
Results on Windows Seven 64 bits, on Intel i7 2600 @ 3.4 GHz (8 cores), Windows running in a virtual machine (kvm) with hardware virtualization.

Python 3.2.2:

10000000 loops, best of 3: 0.12 usec per loop
100000 loops, best of 3: 5.12 usec per loop
1000000 loops, best of 3: 0.581 usec per loop
1000000 loops, best of 3: 0.397 usec per loop

Python 3.3 @ 1439e2d1f490:

1000000 loops, best of 3: 0.265 usec per loop
100000 loops, best of 3: 11 usec per loop
1000000 loops, best of 3: 0.961 usec per loop
1000000 loops, best of 3: 0.924 usec per loop

Python 3.3 @ cdc4e0f8135d:

10000000 loops, best of 3: 0.154 usec per loop
100000 loops, best of 3: 7.85 usec per loop
1000000 loops, best of 3: 0.583 usec per loop
1000000 loops, best of 3: 0.535 usec per loop

To be honest, I'm surprised that my work speeds up Python 3.3 on Windows, because I read that realloc() on Windows is not efficient. It is maybe no more true with Windows Seven? It would be interesting if someone could run the benchmark on Windows XP or 2000.
msg159875 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-05-03 21:34
> Python 3.3 @ 1439e2d1f490:
> 
> 1000000 loops, best of 3: 0.265 usec per loop
> 100000 loops, best of 3: 11 usec per loop
> 1000000 loops, best of 3: 0.961 usec per loop
> 1000000 loops, best of 3: 0.924 usec per loop
> 
> Python 3.3 @ cdc4e0f8135d:
> 
> 10000000 loops, best of 3: 0.154 usec per loop
> 100000 loops, best of 3: 7.85 usec per loop
> 1000000 loops, best of 3: 0.583 usec per loop
> 1000000 loops, best of 3: 0.535 usec per loop

Very nice, thank you!
msg159876 - (view) Author: Kristján Valur Jónsson (kristjan.jonsson) * (Python committer) Date: 2012-05-03 21:35
> because I read that realloc() on Windows is not efficient.
Efficiency is not a Boolean property, you know :)  Anyway, I´d be surprised if it were very iniefficient, given that the heap allocators on Windows are quite mature by now.
msg159877 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2012-05-03 21:42
>> because I read that realloc() on Windows is not efficient.
> Efficiency is not a Boolean property, you know :)  Anyway,
> I´d be surprised if it were very iniefficient, given that
> the heap allocators on Windows are quite mature by now.

My benchmark is more a *micro* benchmark on some very basic cases (short ASCII strings). But it looks like overallocating *helps*. In the following example, only two resize are needed:

./python -m timeit \
    -s 'N=200; L=3; fmt="%s"*N; args=("a"*L,)*N' \
    'fmt % args'

len(fmt)+100 = 500 characters are allocated for the initial buffer. Writing the 501st character enlarges the buffer to 626 characters: first resize. The output string is truncated to 600 characters: second and final resize.
History
Date User Action Args
2012-05-03 21:42:48vstinnersetmessages: + msg159877
2012-05-03 21:35:20kristjan.jonssonsetmessages: + msg159876
2012-05-03 21:34:57pitrousetmessages: + msg159875
2012-05-03 21:25:50vstinnersetmessages: + msg159874
2012-05-03 20:21:45serhiy.storchakasetmessages: + msg159872
2012-05-03 19:30:21kristjan.jonssonsetnosy: + kristjan.jonsson
messages: + msg159869
2012-05-03 17:28:26python-devsetmessages: + msg159867
2012-05-03 12:26:26serhiy.storchakasetmessages: + msg159856
2012-05-03 12:25:20pitrousetmessages: + msg159855
2012-05-03 12:15:56serhiy.storchakasetmessages: + msg159854
2012-05-03 11:43:26python-devsetmessages: + msg159852
2012-05-03 11:31:20pitrousetmessages: + msg159851
2012-05-03 11:17:57vstinnersetstatus: open -> closed
resolution: fixed
2012-05-03 11:16:52python-devsetmessages: + msg159850
2012-05-03 11:12:19vstinnersetmessages: + msg159849
2012-05-03 10:34:06python-devsetmessages: + msg159846
2012-05-03 01:41:24vstinnersetmessages: + msg159831
2012-05-02 23:46:27python-devsetmessages: + msg159824
2012-05-02 23:42:52vstinnersetfiles: - pyunicode_format.patch
2012-05-02 23:42:40vstinnersetfiles: + pyunicode_format_writer.patch

messages: + msg159822
2012-05-01 23:19:10python-devsetmessages: + msg159768
2012-04-30 03:25:20python-devsetnosy: + python-dev
messages: + msg159664
2012-04-30 01:10:10vstinnersetfiles: + pyunicode_format-2.patch

messages: + msg159663
2012-04-28 17:19:25serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg159529
2012-04-28 00:47:58vstinnercreate