Comparison of cyclic objects (was RE: [Python-Dev] trashcan and PR#7)

[Jeremy Hylton]

I did one more round of work on this idea, and I'm satisfied with the
results.  Most of the performance hit can be eliminated by doing
nothing until there are at least N recursive calls to
PyObject_Compare, where N is fairly large. (I picked 25000.)
Non-circular objects that are not deeply nested only pay for an
integer increment, a decrement, and a compare.

Background for patches-only readers: This patch appears to fix PR#7.

Comments and suggestions solicitied.  I think this is worth checking
in. 

Jeremy

Index: Include/object.h
===================================================================
RCS file: /projects/cvsroot/python/dist/src/Include/object.h,v
retrieving revision 2.52
diff -r2.52 object.h
286a287,289
> /* tstate dict key for PyObject_Compare helper */
> extern PyObject *_PyCompareState_Key;
> 
Index: Python/pythonrun.c
===================================================================
RCS file: /projects/cvsroot/python/dist/src/Python/pythonrun.c,v
retrieving revision 2.91
diff -r2.91 pythonrun.c
151a152,153
> 	_PyCompareState_Key = PyString_InternFromString("cmp_state");
> 
Index: Objects/object.c
===================================================================
RCS file: /projects/cvsroot/python/dist/src/Objects/object.c,v
retrieving revision 2.67
diff -r2.67 object.c
300a301,306
> PyObject *_PyCompareState_Key;
> 
> int _PyCompareState_nesting = 0;
> int _PyCompareState_flag = 0;
> #define NESTING_LIMIT 25000
> 
305a312,313
> 	int result;
> 
372c380
< 	if (vtp->tp_compare == NULL)
---
> 	if (vtp->tp_compare == NULL) {
374c382,440
< 	return (*vtp->tp_compare)(v, w);
---
> 	}
> 	++_PyCompareState_nesting;
> 	if (_PyCompareState_nesting > NESTING_LIMIT)
> 		_PyCompareState_flag = 1;
> 	if (_PyCompareState_flag &&
> 	    (vtp->tp_as_mapping || (vtp->tp_as_sequence &&
> 				   !PyString_Check(v))))
> 	{
> 		PyObject *tstate_dict, *cmp_dict, *pair;
> 
> 		tstate_dict = PyThreadState_GetDict();
> 		if (tstate_dict == NULL) {
> 			PyErr_BadInternalCall();
> 			return -1;
> 		} 
> 		cmp_dict = PyDict_GetItem(tstate_dict, _PyCompareState_Key);
> 		if (cmp_dict == NULL) {
> 			cmp_dict = PyDict_New();
> 			if (cmp_dict == NULL)
> 				return -1;
> 			PyDict_SetItem(tstate_dict,
> 				       _PyCompareState_Key,
> 				       cmp_dict);  
> 		}
> 
> 		pair = PyTuple_New(2);
> 		if (pair == NULL) {
> 			return -1;
> 		}
> 		if ((long)v <= (long)w) {
> 			PyTuple_SET_ITEM(pair, 0, PyInt_FromLong((long)v));
> 			PyTuple_SET_ITEM(pair, 1, PyInt_FromLong((long)w));
> 		} else {
> 			PyTuple_SET_ITEM(pair, 0, PyInt_FromLong((long)w));
> 			PyTuple_SET_ITEM(pair, 1, PyInt_FromLong((long)v));
> 		}
> 		if (PyDict_GetItem(cmp_dict, pair)) {
> 			/* already comparing these objects.  assume
> 			   they're equal until shown otherwise 
> 			*/
> 			Py_DECREF(pair);
> 			--_PyCompareState_nesting;
> 			if (_PyCompareState_nesting == 0)
> 				_PyCompareState_flag = 0;
> 			return 0;
> 		}
> 		if (PyDict_SetItem(cmp_dict, pair, pair) == -1) {
> 			return -1;
> 		}
> 		result = (*vtp->tp_compare)(v, w);
> 		PyDict_DelItem(cmp_dict, pair);
> 		Py_DECREF(pair);
> 	} else {
> 		result = (*vtp->tp_compare)(v, w);
> 	}
> 	--_PyCompareState_nesting;
> 	if (_PyCompareState_nesting == 0)
> 		_PyCompareState_flag = 0;
> 	return result;