speedup some comparisons #47356

pitrou · 2008-06-13T18:38:02Z

BPO	3106
Nosy	@malemburg, @rhettinger, @pitrou
Files	cpms.patch cmps4.patch cmps5.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/rhettinger'
closed_at = <Date 2008-12-20.13:23:49.545>
created_at = <Date 2008-06-13.18:38:02.241>
labels = ['interpreter-core', 'performance']
title = 'speedup some comparisons'
updated_at = <Date 2008-12-20.13:23:49.543>
user = 'https://github.com/pitrou'

bugs.python.org fields:

activity = <Date 2008-12-20.13:23:49.543>
actor = 'pitrou'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2008-12-20.13:23:49.545>
closer = 'pitrou'
components = ['Interpreter Core']
creation = <Date 2008-06-13.18:38:02.241>
creator = 'pitrou'
dependencies = []
files = ['10622', '12021', '12341']
hgrepos = []
issue_num = 3106
keywords = ['patch']
message_count = 11.0
messages = ['68174', '69609', '75940', '75943', '77744', '77749', '77753', '77870', '77873', '77880', '78100']
nosy_count = 3.0
nosy_names = ['lemburg', 'rhettinger', 'pitrou']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue3106'
versions = ['Python 3.0']

pitrou · 2008-06-13T18:37:58Z

This patch is an experiment in making faster some of the most common
comparisons (str vs. str, int vs. int). I don't know if it may bring
noticeable speedups in real-world situations, but here are the synthetic
benchmark numbers (from pybench, "this" is the patched version and
"other" is vanilla py3k):

Test minimum run-time average run-time
this other diff this other
diff
-------------------------------------------------------------------------------
CompareFloats: 182ms 173ms +5.4% 182ms 176ms
+3.4%
CompareFloatsIntegers: 238ms 232ms +2.3% 242ms 236ms
+2.5%
CompareIntegers: 237ms 277ms -14.4% 237ms 280ms
-15.2%
CompareInternedStrings: 163ms 257ms -36.7% 163ms 258ms
-36.7%
CompareLongs: 137ms 160ms -14.5% 137ms 162ms
-15.6%
CompareStrings: 149ms 170ms -12.1% 154ms 170ms
-9.5%
-------------------------------------------------------------------------------
Totals: 1105ms 1268ms -12.9% 1115ms 1281ms
-13.0%

pitrou · 2008-07-13T13:00:49Z

Raymond, would you want to take a look?

rhettinger · 2008-11-16T15:13:31Z

You may get better timings if you more the types-are-equal test inside
the types-i-know test. Instead of:
+ if (Py_TYPE(v) == Py_TYPE(w)) {
+ if (PyLong_CheckExact(v)) {
+ if (v == w)
+ break;
+ return PyLong_RichCompare(v, w, op);
+ }
+ if (PyUnicode_CheckExact(v)) {

Do something like:
+ if (PyLong_CheckExact(v)) {
+ if (Py_TYPE(v) == Py_TYPE(w)) {
+ if (v == w)
+ break;
+ return PyLong_RichCompare(v, w, op);
+ }
+ if (PyUnicode_CheckExact(v)) {
+ if (Py_TYPE(v) == Py_TYPE(w)) {

In general, I'm not too keen on adding this kind of dispatch code to
ceval.c. It saves the time spent in PyObject_RichCompare() trying to
figure out where to delegate the work. But it comes at the expense of
weighing down ALL of the other comparisons which haven't gotten a
short-cut specialization.

pitrou · 2008-11-16T20:37:10Z

Hello,

You may get better timings if you more the types-are-equal test inside
the types-i-know test.

I get no discernable difference.

In general, I'm not too keen on adding this kind of dispatch code to
ceval.c. It saves the time spent in PyObject_RichCompare() trying to
figure out where to delegate the work.

Some minimal type testing is necessary if we want to implement the
identity-implies-equality optimization for some types without breaking
the fact that e.g. NaN != NaN. This optimization is important when
dealing with e.g. interned strings. There could be a special flag in the
type structure signaling that the optimization is safe.

I'm attaching a patch which reduces the additional dispatch to a
minimum. The speedup on pybench is smaller, but there is no significant
slowdown for "other" comparisons.

Test minimum run-time average run-time
this other diff this other diff
-------------------------------------------------------------------------------
CompareFloats: 176ms 173ms +1.9% 180ms 175ms +3.2%
CompareFloatsIntegers: 237ms 234ms +1.0% 251ms 240ms +4.6%
CompareIntegers: 266ms 276ms -3.6% 266ms 278ms -4.3%
CompareInternedStrings: 160ms 261ms -38.6% 161ms 261ms -38.4%
CompareLongs: 156ms 166ms -6.1% 156ms 167ms -7.1%
CompareStrings: 167ms 172ms -2.9% 170ms 173ms -1.9%
-------------------------------------------------------------------------------
Totals: 1161ms 1281ms -9.4% 1184ms 1295ms -8.6%

pitrou · 2008-12-13T15:07:29Z

Here is a new patch without any dispatch shortcut in ceval.c, just
optimizations in unicodeobject.c and longobject.c. Net result on pybench:

Test minimum run-time average run-time
this other diff this other
diff
-------------------------------------------------------------------------------
CompareFloats: 166ms 170ms -2.3% 169ms 174ms
-2.8%
CompareFloatsIntegers: 230ms 231ms -0.7% 233ms 231ms
+0.8%
CompareIntegers: 247ms 270ms -8.7% 248ms 272ms
-9.0%
CompareInternedStrings: 196ms 254ms -22.7% 197ms 255ms
-22.7%
CompareLongs: 143ms 158ms -9.0% 143ms 158ms
-9.3%
CompareStrings: 156ms 168ms -7.4% 157ms 169ms
-7.2%
-------------------------------------------------------------------------------
Totals: 1139ms 1252ms -9.1% 1148ms 1260ms
-8.9%

The patch seems fairly uncontroversial to me, I'll commit it soon if
there's no opposition.

rhettinger · 2008-12-13T16:03:37Z

If there's not a hurry, would like to review this a bit more when I get
back early next week.

pitrou · 2008-12-13T16:14:15Z

If there's not a hurry, would like to review this a bit more when I get
back early next week.

No pb!

malemburg · 2008-12-15T14:41:24Z

On 2008-12-13 16:08, Antoine Pitrou wrote:

Antoine Pitrou <pitrou@free.fr> added the comment:

Here is a new patch without any dispatch shortcut in ceval.c, just
optimizations in unicodeobject.c and longobject.c. Net result on pybench:

Test minimum run-time average run-time
this other diff this other
diff
-------------------------------------------------------------------------------
CompareFloats: 166ms 170ms -2.3% 169ms 174ms
-2.8%
CompareFloatsIntegers: 230ms 231ms -0.7% 233ms 231ms
+0.8%
CompareIntegers: 247ms 270ms -8.7% 248ms 272ms
-9.0%
CompareInternedStrings: 196ms 254ms -22.7% 197ms 255ms
-22.7%
CompareLongs: 143ms 158ms -9.0% 143ms 158ms
-9.3%
CompareStrings: 156ms 168ms -7.4% 157ms 169ms
-7.2%
-------------------------------------------------------------------------------
Totals: 1139ms 1252ms -9.1% 1148ms 1260ms
-8.9%

The patch seems fairly uncontroversial to me, I'll commit it soon if
there's no opposition.

Why have you removed the complete error handling section in
PyUnicode_RichCompare() ?

Added file: http://bugs.python.org/file12341/cmps5.patch

pitrou · 2008-12-15T15:34:39Z

Le lundi 15 décembre 2008 à 14:41 +0000, Marc-Andre Lemburg a écrit :

Why have you removed the complete error handling section in
PyUnicode_RichCompare() ?

Because the only error that can occur is a TypeError when one of the two
arguments is not an unicode object, and that is handled by returning
Py_NotImplemented at the end.
(there is no implicit bytes -> unicode coercion anymore, and therefore
things are much simpler)

malemburg · 2008-12-15T19:27:57Z

On 2008-12-15 16:34, Antoine Pitrou wrote:

Antoine Pitrou <pitrou@free.fr> added the comment:

Le lundi 15 décembre 2008 à 14:41 +0000, Marc-Andre Lemburg a écrit :
> Why have you removed the complete error handling section in
> PyUnicode_RichCompare() ?

Because the only error that can occur is a TypeError when one of the two
arguments is not an unicode object, and that is handled by returning
Py_NotImplemented at the end.
(there is no implicit bytes -> unicode coercion anymore, and therefore
things are much simpler)

Ah, sorry, just saw that this is just for Py3.

The fast-path would probably also make sense for Py2 (keeping the
error handling, of course).

pitrou · 2008-12-20T13:23:49Z

I committed the patch, which will also help bpo-1717. Thanks!

pitrou added interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage labels Jun 13, 2008

rhettinger self-assigned this Jul 14, 2008

pitrou closed this as completed Dec 20, 2008

ezio-melotti transferred this issue from another repository Apr 10, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

speedup some comparisons #47356

speedup some comparisons #47356

pitrou commented Jun 13, 2008

pitrou commented Jun 13, 2008

pitrou commented Jul 13, 2008

rhettinger commented Nov 16, 2008

pitrou commented Nov 16, 2008

pitrou commented Dec 13, 2008

rhettinger commented Dec 13, 2008

pitrou commented Dec 13, 2008

malemburg commented Dec 15, 2008

pitrou commented Dec 15, 2008

malemburg commented Dec 15, 2008

pitrou commented Dec 20, 2008

speedup some comparisons #47356

speedup some comparisons #47356

Comments

pitrou commented Jun 13, 2008

pitrou commented Jun 13, 2008

pitrou commented Jul 13, 2008

rhettinger commented Nov 16, 2008

pitrou commented Nov 16, 2008

pitrou commented Dec 13, 2008

rhettinger commented Dec 13, 2008

pitrou commented Dec 13, 2008

malemburg commented Dec 15, 2008

pitrou commented Dec 15, 2008

malemburg commented Dec 15, 2008

pitrou commented Dec 20, 2008