[Python-checkins] python/dist/src/Objects listobject.c,2.131,2.132

[tim_one@users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv4644/python/Objects

Modified Files:
	listobject.c 
Log Message:
Sped the usual case for sorting by calling PyObject_RichCompareBool
directly when no comparison function is specified.  This saves a layer
of function call on every compare then.  Measured speedups:

 i    2**i  *sort  \sort  /sort  3sort  +sort  %sort  ~sort  =sort  !sort
15   32768  12.5%   0.0%   0.0% 100.0%   0.0%  50.0% 100.0% 100.0% -50.0%
16   65536   8.7%   0.0%   0.0%   0.0%   0.0%   0.0%  12.5%   0.0%   0.0%
17  131072   8.0%  25.0%   0.0%  25.0%   0.0%  14.3%   5.9%   0.0%   0.0%
18  262144   6.3% -10.0%  12.5%  11.1%   0.0%   6.3%   5.6%  12.5%   0.0%
19  524288   5.3%   5.9%   0.0%   5.6%   0.0%   5.9%   5.4%   0.0%   2.9%
20 1048576   5.3%   2.9%   2.9%   5.1%   2.8%   1.3%   5.9%   2.9%   4.2%

The best indicators are those that take significant time (larger i), and
where sort doesn't do very few compares (so *sort and ~sort benefit most
reliably).  The large numbers are due to roundoff noise combined with
platform variability; e.g., the 14.3% speedup for %sort at i=17 reflects
a printed elapsed time of 0.18 seconds falling to 0.17, but a change in
the last digit isn't really meaningful (indeed, if it really took 0.175
seconds, one electron having a lazy nanosecond could shift it to either
value <wink>).  Similarly the 25% at 3sort i=17 was a meaningless change
from 0.05 to 0.04.  However, almost all the "meaningless changes" were
in the same direction, which is good.  The before-and-after times for
*sort are clearest:

before after
  0.18  0.16
  0.25  0.23
  0.54  0.50
  1.18  1.11
  2.57  2.44
  5.58  5.30


Index: listobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v
retrieving revision 2.131
retrieving revision 2.132
diff -C2 -d -r2.131 -r2.132
*** listobject.c	3 Aug 2002 02:28:24 -0000	2.131
--- listobject.c	4 Aug 2002 17:47:26 -0000	2.132
***************
*** 761,767 ****
  
  /* 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 -1 on error, 1 if x < y, 0 if x >= y.
   */
--- 761,767 ----
  
  /* Comparison function.  Takes care of calling a user-supplied
!  * comparison function (any callable Python object), which must not be
!  * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool
!  * with Py_LT if you know it's NULL).
   * Returns -1 on error, 1 if x < y, 0 if x >= y.
   */
***************
*** 773,779 ****
  	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).
--- 773,777 ----
  	int i;
  
! 	assert(compare != NULL);
  	/* Call the user's comparison function and translate the 3-way
  	 * result into true or false (or error).
***************
*** 801,809 ****
  }
  
! /* 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)
  
--- 799,816 ----
  }
  
! /* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls
!  * islt.  This avoids a layer of function call in the usual case, and
!  * sorting does many comparisons.
!  * Returns -1 on error, 1 if x < y, 0 if x >= y.
!  */
! #define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ?			\
! 			     PyObject_RichCompareBool(X, Y, Py_LT) :	\
! 			     islt(X, Y, COMPARE))
! 
! /* Compare X to Y via "<".  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)
  
***************
*** 1242,1246 ****
  		 */
   		for (;;) {
! 	 		k = islt(*pb, *pa, compare);
  			if (k) {
  				if (k < 0)
--- 1249,1253 ----
  		 */
   		for (;;) {
! 	 		k = ISLT(*pb, *pa, compare);
  			if (k) {
  				if (k < 0)
***************
*** 1370,1374 ****
  		 */
   		for (;;) {
! 	 		k = islt(*pb, *pa, compare);
  			if (k) {
  				if (k < 0)
--- 1377,1381 ----
  		 */
   		for (;;) {
! 	 		k = ISLT(*pb, *pa, compare);
  			if (k) {
  				if (k < 0)
***************
*** 1684,1687 ****
--- 1691,1695 ----
  }
  #undef IFLT
+ #undef ISLT
  
  int