[Python-checkins] python/dist/src/Objects listobject.c,2.123,2.124
tim_one@users.sourceforge.net
tim_one@users.sourceforge.net
Thu, 18 Jul 2002 20:30:59 -0700
Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv24947/python/Objects
Modified Files:
listobject.c
Log Message:
Cleanup yielding a small speed boost: before rich comparisons were
introduced, list.sort() was rewritten to use only the "< or not <?"
distinction. After rich comparisons were introduced, docompare() was
fiddled to translate a Py_LT Boolean result into the old "-1 for <,
0 for ==, 1 for >" flavor of outcome, and the sorting code was left
alone. This left things more obscure than they should be, and turns
out it also cost measurable cycles.
So: The old CMPERROR novelty is gone. docompare() is renamed to islt(),
and now has the same return conditinos as PyObject_RichCompareBool. The
SETK macro is renamed to ISLT, and is even weirder than before (don't
complain unless you want to maintain the sort code <wink>).
Overall, this yields a 1-2% speedup in the usual (no explicit function
passed to list.sort()) case when sorting arrays of floats (as sortperf.py
does). The boost is higher for arrays of ints.
Index: listobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v
retrieving revision 2.123
retrieving revision 2.124
diff -C2 -d -r2.123 -r2.124
*** listobject.c 19 Jul 2002 02:35:45 -0000 2.123
--- listobject.c 19 Jul 2002 03:30:57 -0000 2.124
***************
*** 759,774 ****
Thanks to discussions with Tim Peters. */
- /* CMPERROR is returned by our comparison function when an error
- occurred. This is the largest negative integer (0x80000000 on a
- 32-bit system). */
- #define CMPERROR ( (int) ((unsigned int)1 << (8*sizeof(int) - 1)) )
-
/* Comparison function. Takes care of calling a user-supplied
comparison function (any callable Python object). Calls the
! standard comparison function, PyObject_Compare(), if the user-
! supplied function is NULL. */
static int
! docompare(PyObject *x, PyObject *y, PyObject *compare)
{
PyObject *res;
--- 759,770 ----
Thanks to discussions with Tim Peters. */
/* Comparison function. Takes care of calling a user-supplied
comparison function (any callable Python object). Calls the
! standard comparison function, PyObject_RichCompareBool(), if the user-
! supplied function is NULL.
! Returns <0 on error, >0 if x < y, 0 if x >= y. */
static int
! islt(PyObject *x, PyObject *y, PyObject *compare)
{
PyObject *res;
***************
*** 776,795 ****
int i;
! if (compare == NULL) {
! /* NOTE: we rely on the fact here that the sorting algorithm
! only ever checks whether k<0, i.e., whether x<y. So we
! invoke the rich comparison function with Py_LT ('<'), and
! return -1 when it returns true and 0 when it returns
! false. */
! i = PyObject_RichCompareBool(x, y, Py_LT);
! if (i < 0)
! return CMPERROR;
! else
! return -i;
! }
args = PyTuple_New(2);
if (args == NULL)
! return CMPERROR;
Py_INCREF(x);
Py_INCREF(y);
--- 772,784 ----
int i;
! if (compare == NULL)
! return PyObject_RichCompareBool(x, y, Py_LT);
+ /* Call the user's comparison function and translate the 3-way
+ * result into true or false (or error).
+ */
args = PyTuple_New(2);
if (args == NULL)
! return -1;
Py_INCREF(x);
Py_INCREF(y);
***************
*** 799,816 ****
Py_DECREF(args);
if (res == NULL)
! return CMPERROR;
if (!PyInt_Check(res)) {
Py_DECREF(res);
PyErr_SetString(PyExc_TypeError,
"comparison function must return int");
! return CMPERROR;
}
i = PyInt_AsLong(res);
Py_DECREF(res);
! if (i < 0)
! return -1;
! if (i > 0)
! return 1;
! return 0;
}
--- 788,801 ----
Py_DECREF(args);
if (res == NULL)
! return -1;
if (!PyInt_Check(res)) {
Py_DECREF(res);
PyErr_SetString(PyExc_TypeError,
"comparison function must return int");
! return -1;
}
i = PyInt_AsLong(res);
Py_DECREF(res);
! return i < 0;
}
***************
*** 851,856 ****
#define STACKSIZE 60
!
! #define SETK(X,Y) if ((k = docompare(X,Y,compare))==CMPERROR) goto fail
/* binarysort is the best method for sorting small arrays: it does
--- 836,845 ----
#define STACKSIZE 60
! /* Compare X to Y via islt(). Goto "fail" if the comparison raises an
! error. Else "k" is set to true iff X<Y, and an "if (k)" block is
! started. It makes more sense in context <wink>. X and Y are PyObject*s.
! */
! #define IFLT(X, Y) if ((k = islt(X, Y, compare)) < 0) goto fail; \
! if (k)
/* binarysort is the best method for sorting small arrays: it does
***************
*** 858,865 ****
elements.
[lo, hi) is a contiguous slice of a list, and is sorted via
! binary insertion.
On entry, must have lo <= start <= hi, and that [lo, start) is already
sorted (pass start == lo if you don't know!).
! If docompare complains (returns CMPERROR) return -1, else 0.
Even in case of error, the output slice will be some permutation of
the input (nothing is lost or duplicated).
--- 847,854 ----
elements.
[lo, hi) is a contiguous slice of a list, and is sorted via
! binary insertion. This sort is stable.
On entry, must have lo <= start <= hi, and that [lo, start) is already
sorted (pass start == lo if you don't know!).
! If islt() complains return -1, else 0.
Even in case of error, the output slice will be some permutation of
the input (nothing is lost or duplicated).
***************
*** 870,879 ****
/* compare -- comparison function object, or NULL for default */
{
- /* assert lo <= start <= hi
- assert [lo, start) is sorted */
register int k;
register PyObject **l, **p, **r;
register PyObject *pivot;
if (lo == start)
++start;
--- 859,868 ----
/* compare -- comparison function object, or NULL for default */
{
register int k;
register PyObject **l, **p, **r;
register PyObject *pivot;
+ assert(lo <= start && start <= hi);
+ /* assert [lo, start) is sorted */
if (lo == start)
++start;
***************
*** 885,890 ****
do {
p = l + ((r - l) >> 1);
! SETK(pivot, *p);
! if (k < 0)
r = p;
else
--- 874,878 ----
do {
p = l + ((r - l) >> 1);
! IFLT(pivot, *p)
r = p;
else
***************
*** 907,911 ****
[lo, hi) is a contiguous slice of a list, to be sorted in place.
On entry, must have lo <= hi,
! If docompare complains (returns CMPERROR) return -1, else 0.
Even in case of error, the output slice will be some permutation of
the input (nothing is lost or duplicated).
--- 895,899 ----
[lo, hi) is a contiguous slice of a list, to be sorted in place.
On entry, must have lo <= hi,
! If islt() complains return -1, else 0.
Even in case of error, the output slice will be some permutation of
the input (nothing is lost or duplicated).
***************
*** 1024,1029 ****
/* assert lo < hi */
for (r = lo+1; r < hi; ++r) {
! SETK(*r, *(r-1));
! if (k < 0)
break;
}
--- 1012,1016 ----
/* assert lo < hi */
for (r = lo+1; r < hi; ++r) {
! IFLT(*r, *(r-1))
break;
}
***************
*** 1037,1042 ****
/* assert lo < hi */
for (r = lo+1; r < hi; ++r) {
! SETK(*(r-1), *r);
! if (k < 0)
break;
}
--- 1024,1028 ----
/* assert lo < hi */
for (r = lo+1; r < hi; ++r) {
! IFLT(*(r-1), *r)
break;
}
***************
*** 1193,1198 ****
/* slide l right, looking for key >= pivot */
do {
! SETK(*l, pivot);
! if (k < 0)
++l;
else
--- 1179,1183 ----
/* slide l right, looking for key >= pivot */
do {
! IFLT(*l, pivot)
++l;
else
***************
*** 1203,1208 ****
while (l < r) {
register PyObject *rval = *r--;
! SETK(rval, pivot);
! if (k < 0) {
/* swap and advance */
r[1] = *l;
--- 1188,1192 ----
while (l < r) {
register PyObject *rval = *r--;
! IFLT(rval, pivot) {
/* swap and advance */
r[1] = *l;
***************
*** 1220,1225 ****
if (l == r) {
! SETK(*r, pivot);
! if (k < 0)
++l;
else
--- 1204,1208 ----
if (l == r) {
! IFLT(*r, pivot)
++l;
else
***************
*** 1250,1255 ****
while (l < hi) {
/* pivot <= *l known */
! SETK(pivot, *l);
! if (k < 0)
break;
else
--- 1233,1237 ----
while (l < hi) {
/* pivot <= *l known */
! IFLT(pivot, *l)
break;
else
***************
*** 1291,1295 ****
}
! #undef SETK
static PyTypeObject immutable_list_type;
--- 1273,1277 ----
}
! #undef IFLT
static PyTypeObject immutable_list_type;