[Python-checkins] python/dist/src/Objects dictobject.c,2.153,2.154
rhettinger at users.sourceforge.net
rhettinger at users.sourceforge.net
Wed Mar 17 16:55:06 EST 2004
Update of /cvsroot/python/python/dist/src/Objects
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv20012
Modified Files:
dictobject.c
Log Message:
Dictionary optimizations:
* Factored constant structure references out of the inner loops for
PyDict_Next(), dict_keys(), dict_values(), and dict_items().
Gave measurable speedups to each (the improvement varies depending
on the sparseness of the dictionary being measured).
* Added a freelist scheme styled after that for tuples. Saves around
80% of the calls to malloc and free. About 10% of the time, the
previous dictionary was completely empty; in those cases, the
dictionary initialization with memset() can be skipped.
Index: dictobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/dictobject.c,v
retrieving revision 2.153
retrieving revision 2.154
diff -C2 -d -r2.153 -r2.154
*** dictobject.c 8 Mar 2004 04:19:01 -0000 2.153
--- dictobject.c 17 Mar 2004 21:55:03 -0000 2.154
***************
*** 153,156 ****
--- 153,161 ----
} while(0)
+ /* Dictionary reuse scheme to save calls to malloc, free, and memset */
+ #define MAXFREEDICTS 80
+ static PyDictObject *free_dicts[MAXFREEDICTS];
+ static int num_free_dicts = 0;
+
PyObject *
PyDict_New(void)
***************
*** 165,172 ****
#endif
}
! mp = PyObject_GC_New(dictobject, &PyDict_Type);
! if (mp == NULL)
! return NULL;
! EMPTY_TO_MINSIZE(mp);
mp->ma_lookup = lookdict_string;
#ifdef SHOW_CONVERSION_COUNTS
--- 170,190 ----
#endif
}
! if (num_free_dicts) {
! mp = free_dicts[--num_free_dicts];
! assert (mp != NULL);
! assert (mp->ob_type == &PyDict_Type);
! _Py_NewReference((PyObject *)mp);
! if (mp->ma_fill) {
! EMPTY_TO_MINSIZE(mp);
! }
! assert (mp->ma_used == 0);
! assert (mp->ma_table == mp->ma_smalltable);
! assert (mp->ma_mask == PyDict_MINSIZE - 1);
! } else {
! mp = PyObject_GC_New(dictobject, &PyDict_Type);
! if (mp == NULL)
! return NULL;
! EMPTY_TO_MINSIZE(mp);
! }
mp->ma_lookup = lookdict_string;
#ifdef SHOW_CONVERSION_COUNTS
***************
*** 673,693 ****
PyDict_Next(PyObject *op, int *ppos, PyObject **pkey, PyObject **pvalue)
{
! int i;
! register dictobject *mp;
if (!PyDict_Check(op))
return 0;
- mp = (dictobject *)op;
i = *ppos;
if (i < 0)
return 0;
! while (i <= mp->ma_mask && mp->ma_table[i].me_value == NULL)
i++;
*ppos = i+1;
! if (i > mp->ma_mask)
return 0;
if (pkey)
! *pkey = mp->ma_table[i].me_key;
if (pvalue)
! *pvalue = mp->ma_table[i].me_value;
return 1;
}
--- 691,713 ----
PyDict_Next(PyObject *op, int *ppos, PyObject **pkey, PyObject **pvalue)
{
! register int i, mask;
! register dictentry *ep;
!
if (!PyDict_Check(op))
return 0;
i = *ppos;
if (i < 0)
return 0;
! ep = ((dictobject *)op)->ma_table;
! mask = ((dictobject *)op)->ma_mask;
! while (i <= mask && ep[i].me_value == NULL)
i++;
*ppos = i+1;
! if (i > mask)
return 0;
if (pkey)
! *pkey = ep[i].me_key;
if (pvalue)
! *pvalue = ep[i].me_value;
return 1;
}
***************
*** 711,715 ****
if (mp->ma_table != mp->ma_smalltable)
PyMem_DEL(mp->ma_table);
! mp->ob_type->tp_free((PyObject *)mp);
Py_TRASHCAN_SAFE_END(mp)
}
--- 731,738 ----
if (mp->ma_table != mp->ma_smalltable)
PyMem_DEL(mp->ma_table);
! if (num_free_dicts < MAXFREEDICTS && mp->ob_type == &PyDict_Type)
! free_dicts[num_free_dicts++] = mp;
! else
! mp->ob_type->tp_free((PyObject *)mp);
Py_TRASHCAN_SAFE_END(mp)
}
***************
*** 883,887 ****
{
register PyObject *v;
! register int i, j, n;
again:
--- 906,912 ----
{
register PyObject *v;
! register int i, j;
! dictentry *ep;
! int mask, n;
again:
***************
*** 897,903 ****
goto again;
}
! for (i = 0, j = 0; i <= mp->ma_mask; i++) {
! if (mp->ma_table[i].me_value != NULL) {
! PyObject *key = mp->ma_table[i].me_key;
Py_INCREF(key);
PyList_SET_ITEM(v, j, key);
--- 922,930 ----
goto again;
}
! ep = mp->ma_table;
! mask = mp->ma_mask;
! for (i = 0, j = 0; i <= mask; i++) {
! if (ep[i].me_value != NULL) {
! PyObject *key = ep[i].me_key;
Py_INCREF(key);
PyList_SET_ITEM(v, j, key);
***************
*** 905,908 ****
--- 932,936 ----
}
}
+ assert(j == n);
return v;
}
***************
*** 912,916 ****
{
register PyObject *v;
! register int i, j, n;
again:
--- 940,946 ----
{
register PyObject *v;
! register int i, j;
! dictentry *ep;
! int mask, n;
again:
***************
*** 926,932 ****
goto again;
}
! for (i = 0, j = 0; i <= mp->ma_mask; i++) {
! if (mp->ma_table[i].me_value != NULL) {
! PyObject *value = mp->ma_table[i].me_value;
Py_INCREF(value);
PyList_SET_ITEM(v, j, value);
--- 956,964 ----
goto again;
}
! ep = mp->ma_table;
! mask = mp->ma_mask;
! for (i = 0, j = 0; i <= mask; i++) {
! if (ep[i].me_value != NULL) {
! PyObject *value = ep[i].me_value;
Py_INCREF(value);
PyList_SET_ITEM(v, j, value);
***************
*** 934,937 ****
--- 966,970 ----
}
}
+ assert(j == n);
return v;
}
***************
*** 942,946 ****
--- 975,981 ----
register PyObject *v;
register int i, j, n;
+ int mask;
PyObject *item, *key, *value;
+ dictentry *ep;
/* Preallocate the list of tuples, to avoid allocations during
***************
*** 969,976 ****
}
/* Nothing we do below makes any function calls. */
! for (i = 0, j = 0; i <= mp->ma_mask; i++) {
! if (mp->ma_table[i].me_value != NULL) {
! key = mp->ma_table[i].me_key;
! value = mp->ma_table[i].me_value;
item = PyList_GET_ITEM(v, j);
Py_INCREF(key);
--- 1004,1013 ----
}
/* Nothing we do below makes any function calls. */
! ep = mp->ma_table;
! mask = mp->ma_mask;
! for (i = 0, j = 0; i <= mask; i++) {
! if (ep[i].me_value != NULL) {
! key = ep[i].me_key;
! value = ep[i].me_value;
item = PyList_GET_ITEM(v, j);
Py_INCREF(key);
More information about the Python-checkins
mailing list