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

2002年8月04日 10:47:29 -0700

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