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;
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4