[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;