Special-case string formatting in BINARY_MODULO implementation

[collinwinter]

BPO	5176
Files	faster_modulo.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 = None
closed_at = <Date 2009-02-20.19:32:01.956>
created_at = <Date 2009-02-06.23:48:49.380>
labels = ['interpreter-core', 'performance']
title = 'Special-case string formatting in BINARY_MODULO implementation'
updated_at = <Date 2009-02-20.19:32:01.954>
user = 'https://bugs.python.org/collinwinter'

bugs.python.org fields:

activity = <Date 2009-02-20.19:32:01.954>
actor = 'collinwinter'
assignee = 'jyasskin'
closed = True
closed_date = <Date 2009-02-20.19:32:01.956>
closer = 'collinwinter'
components = ['Interpreter Core']
creation = <Date 2009-02-06.23:48:49.380>
creator = 'collinwinter'
dependencies = []
files = ['13077']
hgrepos = []
issue_num = 5176
keywords = ['patch', 'needs review']
message_count = 5.0
messages = ['81319', '81331', '81982', '82500', '82543']
nosy_count = 2.0
nosy_names = ['collinwinter', 'jyasskin']
pr_nums = []
priority = 'normal'
resolution = 'accepted'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue5176'
versions = ['Python 2.7']

[collinwinter]

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:

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

Django:
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:

Pickling:
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
unpickling.

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] - http://code.google.com/p/spitfire/

[jyasskin]

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/test_decimal.py](https://github.com/python/cpython/blob/main/Lib/test/test_decimal.py)?

[collinwinter]

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
ints/longs.

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:
Spitfire:
Min: 0.687 -> 0.668: 2.96% faster
Avg: 0.689 -> 0.669: 2.96% faster

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

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

SlowPickle:
Min: 0.920 -> 0.905: 1.62% faster
Avg: 0.926 -> 0.913: 1.38% faster

[jyasskin]

Looks good to me.

[collinwinter]

Committed as r69811.