[Python-checkins] python/dist/src/Objects dictobject.c,2.154,2.155
rhettinger at users.sourceforge.net
rhettinger at users.sourceforge.net
Wed Mar 17 21:41:22 EST 2004
Update of /cvsroot/python/python/dist/src/Objects
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv9478
Modified Files:
dictobject.c
Log Message:
Optimize dictionary iterators.
* Split into three separate types that share everything except the
code for iternext. Saves run time decision making and allows
each iternext function to be specialized.
* Inlined PyDict_Next(). In addition to saving a function call, this
allows a redundant test to be eliminated and further specialization
of the code for the unique needs of each iterator type.
* Created a reusable result tuple for iteritems(). Saves the malloc
time for tuples when the previous result was not kept by client code
(this is the typical use case for iteritems). If the client code
does keep the reference, then a new tuple is created.
Results in a 20% to 30% speedup depending on the size and sparsity
of the dictionary.
Index: dictobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/dictobject.c,v
retrieving revision 2.154
retrieving revision 2.155
diff -C2 -d -r2.154 -r2.155
*** dictobject.c 17 Mar 2004 21:55:03 -0000 2.154
--- dictobject.c 18 Mar 2004 02:41:19 -0000 2.155
***************
*** 1727,1764 ****
! static PyObject *dictiter_new(dictobject *, binaryfunc);
!
! static PyObject *
! select_key(PyObject *key, PyObject *value)
! {
! Py_INCREF(key);
! return key;
! }
!
! static PyObject *
! select_value(PyObject *key, PyObject *value)
! {
! Py_INCREF(value);
! return value;
! }
!
! static PyObject *
! select_item(PyObject *key, PyObject *value)
! {
! PyObject *res = PyTuple_New(2);
!
! if (res != NULL) {
! Py_INCREF(key);
! Py_INCREF(value);
! PyTuple_SET_ITEM(res, 0, key);
! PyTuple_SET_ITEM(res, 1, value);
! }
! return res;
! }
static PyObject *
dict_iterkeys(dictobject *dict)
{
! return dictiter_new(dict, select_key);
}
--- 1727,1739 ----
! extern PyTypeObject PyDictIterKey_Type; /* Forward */
! extern PyTypeObject PyDictIterValue_Type; /* Forward */
! extern PyTypeObject PyDictIterItem_Type; /* Forward */
! static PyObject *dictiter_new(dictobject *, PyTypeObject *);
static PyObject *
dict_iterkeys(dictobject *dict)
{
! return dictiter_new(dict, &PyDictIterKey_Type);
}
***************
*** 1766,1770 ****
dict_itervalues(dictobject *dict)
{
! return dictiter_new(dict, select_value);
}
--- 1741,1745 ----
dict_itervalues(dictobject *dict)
{
! return dictiter_new(dict, &PyDictIterValue_Type);
}
***************
*** 1772,1776 ****
dict_iteritems(dictobject *dict)
{
! return dictiter_new(dict, select_item);
}
--- 1747,1751 ----
dict_iteritems(dictobject *dict)
{
! return dictiter_new(dict, &PyDictIterItem_Type);
}
***************
*** 1932,1936 ****
dict_iter(dictobject *dict)
{
! return dictiter_new(dict, select_key);
}
--- 1907,1911 ----
dict_iter(dictobject *dict)
{
! return dictiter_new(dict, &PyDictIterKey_Type);
}
***************
*** 2031,2037 ****
}
! /* Dictionary iterator type */
!
! extern PyTypeObject PyDictIter_Type; /* Forward */
typedef struct {
--- 2006,2010 ----
}
! /* Dictionary iterator types */
typedef struct {
***************
*** 2040,2051 ****
int di_used;
int di_pos;
! binaryfunc di_select;
} dictiterobject;
static PyObject *
! dictiter_new(dictobject *dict, binaryfunc select)
{
dictiterobject *di;
! di = PyObject_New(dictiterobject, &PyDictIter_Type);
if (di == NULL)
return NULL;
--- 2013,2024 ----
int di_used;
int di_pos;
! PyObject* di_result; /* reusable result tuple for iteritems */
} dictiterobject;
static PyObject *
! dictiter_new(dictobject *dict, PyTypeObject *itertype)
{
dictiterobject *di;
! di = PyObject_New(dictiterobject, itertype);
if (di == NULL)
return NULL;
***************
*** 2054,2058 ****
di->di_used = dict->ma_used;
di->di_pos = 0;
! di->di_select = select;
return (PyObject *)di;
}
--- 2027,2039 ----
di->di_used = dict->ma_used;
di->di_pos = 0;
! if (itertype == &PyDictIterItem_Type) {
! di->di_result = PyTuple_Pack(2, Py_None, Py_None);
! if (di->di_result == NULL) {
! Py_DECREF(di);
! return NULL;
! }
! }
! else
! di->di_result = NULL;
return (PyObject *)di;
}
***************
*** 2062,2076 ****
{
Py_XDECREF(di->di_dict);
PyObject_Del(di);
}
! static PyObject *dictiter_iternext(dictiterobject *di)
{
! PyObject *key, *value;
! if (di->di_dict == NULL)
return NULL;
! if (di->di_used != di->di_dict->ma_used) {
PyErr_SetString(PyExc_RuntimeError,
"dictionary changed size during iteration");
--- 2043,2062 ----
{
Py_XDECREF(di->di_dict);
+ Py_XDECREF(di->di_result);
PyObject_Del(di);
}
! static PyObject *dictiter_iternextkey(dictiterobject *di)
{
! PyObject *key;
! register int i, mask;
! register dictentry *ep;
! dictobject *d = di->di_dict;
! if (d == NULL)
return NULL;
+ assert (PyDict_Check(d));
! if (di->di_used != d->ma_used) {
PyErr_SetString(PyExc_RuntimeError,
"dictionary changed size during iteration");
***************
*** 2078,2093 ****
return NULL;
}
- if (PyDict_Next((PyObject *)(di->di_dict), &di->di_pos, &key, &value))
- return (*di->di_select)(key, value);
! Py_DECREF(di->di_dict);
di->di_dict = NULL;
return NULL;
}
! PyTypeObject PyDictIter_Type = {
PyObject_HEAD_INIT(&PyType_Type)
0, /* ob_size */
! "dictionary-iterator", /* tp_name */
sizeof(dictiterobject), /* tp_basicsize */
0, /* tp_itemsize */
--- 2064,2092 ----
return NULL;
}
! i = di->di_pos;
! if (i < 0)
! goto fail;
! ep = d->ma_table;
! mask = d->ma_mask;
! while (i <= mask && ep[i].me_value == NULL)
! i++;
! di->di_pos = i+1;
! if (i > mask)
! goto fail;
! key = ep[i].me_key;
! Py_INCREF(key);
! return key;
!
! fail:
! Py_DECREF(d);
di->di_dict = NULL;
return NULL;
}
! PyTypeObject PyDictIterKey_Type = {
PyObject_HEAD_INIT(&PyType_Type)
0, /* ob_size */
! "dictionary-keyiterator", /* tp_name */
sizeof(dictiterobject), /* tp_basicsize */
0, /* tp_itemsize */
***************
*** 2115,2125 ****
0, /* tp_weaklistoffset */
PyObject_SelfIter, /* tp_iter */
! (iternextfunc)dictiter_iternext, /* tp_iternext */
! 0, /* tp_methods */
! 0, /* tp_members */
! 0, /* tp_getset */
! 0, /* tp_base */
! 0, /* tp_dict */
! 0, /* tp_descr_get */
! 0, /* tp_descr_set */
};
--- 2114,2270 ----
0, /* tp_weaklistoffset */
PyObject_SelfIter, /* tp_iter */
! (iternextfunc)dictiter_iternextkey, /* tp_iternext */
! };
!
! static PyObject *dictiter_iternextvalue(dictiterobject *di)
! {
! PyObject *value;
! register int i, mask;
! register dictentry *ep;
! dictobject *d = di->di_dict;
!
! if (d == NULL)
! return NULL;
! assert (PyDict_Check(d));
!
! if (di->di_used != d->ma_used) {
! PyErr_SetString(PyExc_RuntimeError,
! "dictionary changed size during iteration");
! di->di_used = -1; /* Make this state sticky */
! return NULL;
! }
!
! i = di->di_pos;
! if (i < 0)
! goto fail;
! ep = d->ma_table;
! mask = d->ma_mask;
! while (i <= mask && (value=ep[i].me_value) == NULL)
! i++;
! di->di_pos = i+1;
! if (i > mask)
! goto fail;
! Py_INCREF(value);
! return value;
!
! fail:
! Py_DECREF(d);
! di->di_dict = NULL;
! return NULL;
! }
!
! PyTypeObject PyDictIterValue_Type = {
! PyObject_HEAD_INIT(&PyType_Type)
! 0, /* ob_size */
! "dictionary-valueiterator", /* tp_name */
! sizeof(dictiterobject), /* tp_basicsize */
! 0, /* tp_itemsize */
! /* methods */
! (destructor)dictiter_dealloc, /* tp_dealloc */
! 0, /* tp_print */
! 0, /* tp_getattr */
! 0, /* tp_setattr */
! 0, /* tp_compare */
! 0, /* tp_repr */
! 0, /* tp_as_number */
! 0, /* tp_as_sequence */
! 0, /* tp_as_mapping */
! 0, /* tp_hash */
! 0, /* tp_call */
! 0, /* tp_str */
! PyObject_GenericGetAttr, /* tp_getattro */
! 0, /* tp_setattro */
! 0, /* tp_as_buffer */
! Py_TPFLAGS_DEFAULT, /* tp_flags */
! 0, /* tp_doc */
! 0, /* tp_traverse */
! 0, /* tp_clear */
! 0, /* tp_richcompare */
! 0, /* tp_weaklistoffset */
! PyObject_SelfIter, /* tp_iter */
! (iternextfunc)dictiter_iternextvalue, /* tp_iternext */
! };
!
! static PyObject *dictiter_iternextitem(dictiterobject *di)
! {
! PyObject *key, *value, *result = di->di_result;
! register int i, mask;
! register dictentry *ep;
! dictobject *d = di->di_dict;
!
! if (d == NULL)
! return NULL;
! assert (PyDict_Check(d));
!
! if (di->di_used != d->ma_used) {
! PyErr_SetString(PyExc_RuntimeError,
! "dictionary changed size during iteration");
! di->di_used = -1; /* Make this state sticky */
! return NULL;
! }
!
! i = di->di_pos;
! if (i < 0)
! goto fail;
! ep = d->ma_table;
! mask = d->ma_mask;
! while (i <= mask && ep[i].me_value == NULL)
! i++;
! di->di_pos = i+1;
! if (i > mask)
! goto fail;
!
! if (result->ob_refcnt == 1) {
! Py_INCREF(result);
! Py_DECREF(PyTuple_GET_ITEM(result, 0));
! Py_DECREF(PyTuple_GET_ITEM(result, 1));
! } else {
! result = PyTuple_New(2);
! if (result == NULL)
! return NULL;
! }
! key = ep[i].me_key;
! value = ep[i].me_value;
! Py_INCREF(key);
! Py_INCREF(value);
! PyTuple_SET_ITEM(result, 0, key);
! PyTuple_SET_ITEM(result, 1, value);
! return result;
!
! fail:
! Py_DECREF(d);
! di->di_dict = NULL;
! return NULL;
! }
!
! PyTypeObject PyDictIterItem_Type = {
! PyObject_HEAD_INIT(&PyType_Type)
! 0, /* ob_size */
! "dictionary-itemiterator", /* tp_name */
! sizeof(dictiterobject), /* tp_basicsize */
! 0, /* tp_itemsize */
! /* methods */
! (destructor)dictiter_dealloc, /* tp_dealloc */
! 0, /* tp_print */
! 0, /* tp_getattr */
! 0, /* tp_setattr */
! 0, /* tp_compare */
! 0, /* tp_repr */
! 0, /* tp_as_number */
! 0, /* tp_as_sequence */
! 0, /* tp_as_mapping */
! 0, /* tp_hash */
! 0, /* tp_call */
! 0, /* tp_str */
! PyObject_GenericGetAttr, /* tp_getattro */
! 0, /* tp_setattro */
! 0, /* tp_as_buffer */
! Py_TPFLAGS_DEFAULT, /* tp_flags */
! 0, /* tp_doc */
! 0, /* tp_traverse */
! 0, /* tp_clear */
! 0, /* tp_richcompare */
! 0, /* tp_weaklistoffset */
! PyObject_SelfIter, /* tp_iter */
! (iternextfunc)dictiter_iternextitem, /* tp_iternext */
};
More information about the Python-checkins
mailing list