[Python-checkins] CVS: python/dist/src/Objects tupleobject.c,2.48,2.49

[Tim Peters]

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

Modified Files:
	tupleobject.c 
Log Message:
Speed tuple comparisons in two ways:
1. Omit the early-out EQ/NE "lengths different?" test.  Was unable to find
   any real code where it triggered, but it always costs.  The same is not
   true of list richcmps, where different-size lists appeared to get
   compared about half the time.
2. Because tuples are immutable, there's no need to refetch the lengths of
   both tuples from memory again on each loop trip.

BUG ALERT:  The tuple (and list) richcmp algorithm is arguably wrong,
because it won't believe there's any difference unless Py_EQ returns false
for some corresponding elements:

>>> class C:
...     def __lt__(x, y): return 1
...     __eq__ = __lt__
...
>>> C() < C()
1
>>> (C(),) < (C(),)
0
>>>

That doesn't make sense -- provided you believe the defn. of C makes sense.


Index: tupleobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/tupleobject.c,v
retrieving revision 2.48
retrieving revision 2.49
diff -C2 -r2.48 -r2.49
*** tupleobject.c	2001/01/18 00:00:53	2.48
--- tupleobject.c	2001/05/15 20:12:59	2.49
***************
*** 377,380 ****
--- 377,381 ----
  	PyTupleObject *vt, *wt;
  	int i;
+ 	int vlen, wlen;
  
  	if (!PyTuple_Check(v) || !PyTuple_Check(w)) {
***************
*** 386,402 ****
  	wt = (PyTupleObject *)w;
  
! 	if (vt->ob_size != wt->ob_size && (op == Py_EQ || op == Py_NE)) {
! 		/* Shortcut: if the lengths differ, the tuples differ */
! 		PyObject *res;
! 		if (op == Py_EQ)
! 			res = Py_False;
! 		else
! 			res = Py_True;
! 		Py_INCREF(res);
! 		return res;
! 	}
  
! 	/* Search for the first index where items are different */
! 	for (i = 0; i < vt->ob_size && i < wt->ob_size; i++) {
  		int k = PyObject_RichCompareBool(vt->ob_item[i],
  						 wt->ob_item[i], Py_EQ);
--- 387,405 ----
  	wt = (PyTupleObject *)w;
  
! 	vlen = vt->ob_size;
! 	wlen = wt->ob_size;
! 
! 	/* Note:  the corresponding code for lists has an "early out" test
! 	 * here when op is EQ or NE and the lengths differ.  That pays there,
! 	 * but Tim was unable to find any real code where EQ/NE tuple
! 	 * compares don't have the same length, so testing for it here would
! 	 * have cost without benefit.
! 	 */
  
! 	/* Search for the first index where items are different.
! 	 * Note that because tuples are immutable, it's safe to reuse
! 	 * vlen and wlen across the comparison calls.
! 	 */
! 	for (i = 0; i < vlen && i < wlen; i++) {
  		int k = PyObject_RichCompareBool(vt->ob_item[i],
  						 wt->ob_item[i], Py_EQ);
***************
*** 407,423 ****
  	}
  
! 	if (i >= vt->ob_size || i >= wt->ob_size) {
  		/* No more items to compare -- compare sizes */
- 		int vs = vt->ob_size;
- 		int ws = wt->ob_size;
  		int cmp;
  		PyObject *res;
  		switch (op) {
! 		case Py_LT: cmp = vs <  ws; break;
! 		case Py_LE: cmp = ws <= ws; break;
! 		case Py_EQ: cmp = vs == ws; break;
! 		case Py_NE: cmp = vs != ws; break;
! 		case Py_GT: cmp = vs >  ws; break;
! 		case Py_GE: cmp = vs >= ws; break;
  		default: return NULL; /* cannot happen */
  		}
--- 410,424 ----
  	}
  
! 	if (i >= vlen || i >= wlen) {
  		/* No more items to compare -- compare sizes */
  		int cmp;
  		PyObject *res;
  		switch (op) {
! 		case Py_LT: cmp = vlen <  wlen; break;
! 		case Py_LE: cmp = vlen <= wlen; break;
! 		case Py_EQ: cmp = vlen == wlen; break;
! 		case Py_NE: cmp = vlen != wlen; break;
! 		case Py_GT: cmp = vlen >  wlen; break;
! 		case Py_GE: cmp = vlen >= wlen; break;
  		default: return NULL; /* cannot happen */
  		}