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;