Title: Special-case string formatting in BINARY_MODULO implementation
Type: performance Stage:
Components: Interpreter Core Versions: Python 2.7
Status: closed Resolution: accepted
Dependencies: Superseder:
Assigned To: jyasskin Nosy List: collinwinter, jyasskin
Priority: normal Keywords: needs review, patch

Created on 2009-02-06 23:48 by collinwinter, last changed 2009-02-20 19:32 by collinwinter. This issue is now closed.

File name Uploaded Description Edit
faster_modulo.patch collinwinter, 2009-02-14 00:13
Messages (5)
msg81319 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2009-02-06 23:48
This patch speeds up the string formatting % operator by avoiding the
unnecessary indirection in PyNumber_Remainder(). This particularly
benefits templating systems that do a lot of string formatting via %.

Performance tested with gcc 4.3.1 x86_64 on Linux 2.6.18:

Min: 22.443 -> 22.306: 0.61% faster
Avg: 22.465 -> 22.324: 0.63% faster

Min: 0.598 -> 0.591: 1.24% faster
Avg: 0.601 -> 0.595: 1.03% faster

Spitfire [1]:
Min: 0.752 -> 0.717: 4.91% faster
Avg: 0.754 -> 0.719: 4.83% faster

The Django test renders a 150x150 cell table 100 times. The Spitfire
test renders a 1000x1000 cell table 100 times. The 2to3 test translates
all of 2to3 with `-f all` five times. There is no significant impact on
PyBench. Less important code like the pure-Python pickle implementation
also shows an improvement:

Min: 6.680 -> 6.535: 2.22% faster
Avg: 6.740 -> 6.576: 2.50% faster

This is pickling a list of 40000 dicts 100 times. This does not impact

About the patch:
I tested various combinations of PyString_Check and PyString_CheckExact
and what you see in the patch demonstrated the best performance across
all benchmarks. I also tested changing the definition of PyString_Check
to include a short-circuit on PyString_CheckExact, but that did not
provide a consistent benefit. 

[1] -
msg81331 - (view) Author: Jeffrey Yasskin (jyasskin) * (Python committer) Date: 2009-02-07 01:53
I think this is only valid when PyString_CheckExact is true. A subclass
could override __mod__, right?

I'm somewhat interested to see how a primarily-numeric benchmark
responds to this patch. I'd expect it to get very slightly slower for %
operations. Probably, given that there's an indirect call in the way,
the extra test would hide in the noise, but it's worth checking. What's
a good numeric benchmark suite? `time ./python Lib/test/`?
msg81982 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2009-02-14 00:13
Updated the patch to use only PyString_CheckExact(); added a test for
the behaviour of string subclasses wrt the % operator.

There's a very slight performance hit when using % with numbers, but
it's so small as to be statistically insignificant. If it turns out to
be relevant in the future, it's easy enough to add a special case for

For some reason, using PyString_CheckExact instead of
PyString_CheckExact || PyString_Check actually results in slower code
(still an improvement, but not as much). The weird thing is that none of
the benchmarks I'm running use % on string subclasses at any point. I
talked about it with some of the gcc guys, but they didn't have any
immediate leads. I'm going to send them the .o files in case gcc is
missing some optimization.

New benchmark numbers:
Min: 0.687 -> 0.668: 2.96% faster
Avg: 0.689 -> 0.669: 2.96% faster

Min: 20.376 -> 20.187: 0.94% faster
Avg: 20.396 -> 20.225: 0.84% faster

Min: 0.560 -> 0.549: 1.94% faster
Avg: 0.562 -> 0.552: 1.93% faster

Min: 0.920 -> 0.905: 1.62% faster
Avg: 0.926 -> 0.913: 1.38% faster
msg82500 - (view) Author: Jeffrey Yasskin (jyasskin) * (Python committer) Date: 2009-02-19 22:09
Looks good to me.
msg82543 - (view) Author: Collin Winter (collinwinter) * (Python committer) Date: 2009-02-20 19:32
Committed as r69811.
Date User Action Args
2009-02-20 19:32:01collinwintersetstatus: open -> closed
resolution: accepted
messages: + msg82543
keywords: patch, patch, needs review
2009-02-19 22:09:39jyasskinsetkeywords: patch, patch, needs review
messages: + msg82500
2009-02-14 00:13:16collinwintersetfiles: - faster_modulo.patch
2009-02-14 00:13:07collinwintersetkeywords: patch, patch, needs review
files: + faster_modulo.patch
messages: + msg81982
2009-02-07 01:53:06jyasskinsetkeywords: patch, patch, needs review
messages: + msg81331
2009-02-06 23:48:49collinwintercreate