classification
Title: speedup some comparisons
Type: performance Stage:
Components: Interpreter Core Versions: Python 3.0
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: lemburg, pitrou, rhettinger
Priority: normal Keywords: patch

Created on 2008-06-13 18:38 by pitrou, last changed 2008-12-20 13:23 by pitrou. This issue is now closed.

Files
File name Uploaded Description Edit
cpms.patch pitrou, 2008-06-13 18:37
cmps4.patch pitrou, 2008-11-16 20:37
cmps5.patch pitrou, 2008-12-13 15:07
Messages (11)
msg68174 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-06-13 18:37
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%
msg69609 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-07-13 13:00
Raymond, would you want to take a look?
msg75940 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-11-16 15:13
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.
msg75943 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-11-16 20:37
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%
msg77744 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-13 15:07
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.
msg77749 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-13 16:03
If there's not a hurry, would like to review this a bit more when I get
back early next week.
msg77753 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-13 16:14
> If there's not a hurry, would like to review this a bit more when I get
> back early next week.

No pb!
msg77870 - (view) Author: Marc-Andre Lemburg (lemburg) * (Python committer) Date: 2008-12-15 14:41
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
msg77873 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-15 15:34
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)
msg77880 - (view) Author: Marc-Andre Lemburg (lemburg) * (Python committer) Date: 2008-12-15 19:27
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).
msg78100 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-20 13:23
I committed the patch, which will also help #1717. Thanks!
History
Date User Action Args
2008-12-20 13:23:49pitrousetstatus: open -> closed
resolution: fixed
messages: + msg78100
2008-12-15 19:27:57lemburgsetmessages: + msg77880
2008-12-15 15:34:39pitrousetmessages: + msg77873
2008-12-15 14:41:25lemburgsetnosy: + lemburg
messages: + msg77870
2008-12-13 16:14:14pitrousetmessages: + msg77753
2008-12-13 16:03:36rhettingersetmessages: + msg77749
2008-12-13 15:07:31pitrousetfiles: + cmps5.patch
messages: + msg77744
2008-11-16 20:37:10pitrousetfiles: + cmps4.patch
messages: + msg75943
2008-11-16 15:13:32rhettingersetmessages: + msg75940
2008-07-14 13:28:44rhettingersetassignee: rhettinger
2008-07-13 13:00:50pitrousetnosy: + rhettinger
messages: + msg69609
2008-06-13 18:38:02pitroucreate