A much revised version of SF patch 514662, by Naofumi Honda. This
speeds up __getitem__ and __setitem__ in subclasses of built-in
sequences.
It's much revised because I took the opportunity to refactor the code
somewhat (moving a large section of duplicated code to a helper
function) and added comments to a series of functions.
diff --git a/Objects/typeobject.c b/Objects/typeobject.c
index c369ff7..f0e8c83 100644
--- a/Objects/typeobject.c
+++ b/Objects/typeobject.c
@@ -3239,9 +3239,9 @@
- slot_tp_getattr_hook() is used when a __getattr__ hook is present.
- The code in update_slot() and fixup_slot_dispatchers() always installs
- slot_tp_getattr_hook(); this detects the absence of __getattr__ and then
- installs the simpler slot if necessary. */
+ The code in update_one_slot() always installs slot_tp_getattr_hook(); this
+ detects the absence of __getattr__ and then installs the simpler slot if
+ necessary. */
static PyObject *
slot_tp_getattro(PyObject *self, PyObject *name)
@@ -3492,7 +3492,9 @@
incorporates the additional structures used for numbers, sequences and
mappings. Note that multiple names may map to the same slot (e.g. __eq__,
__ne__ etc. all map to tp_richcompare) and one name may map to multiple
- slots (e.g. __str__ affects tp_str as well as tp_repr). */
+ slots (e.g. __str__ affects tp_str as well as tp_repr). The table is
+ terminated with an all-zero entry. (This table is further initialized and
+ sorted in init_slotdefs() below.) */
typedef struct wrapperbase slotdef;
@@ -3713,6 +3715,11 @@
{NULL}
};
+/* Given a type pointer and an offset gotten from a slotdef entry, return a
+ pointer to the actual slot. This is not quite the same as simply adding
+ the offset to the type pointer, since it takes care to indirect through the
+ proper indirection pointer (as_buffer, etc.); it returns NULL if the
+ indirection pointer is NULL. */
static void **
slotptr(PyTypeObject *type, int offset)
{
@@ -3740,51 +3747,120 @@
return (void **)ptr;
}
+/* Length of array of slotdef pointers used to store slots with the
+ same __name__. There should be at most MAX_EQUIV-1 slotdef entries with
+ the same __name__, for any __name__. Since that's a static property, it is
+ appropriate to declare fixed-size arrays for this. */
+#define MAX_EQUIV 10
+
+/* Return a slot pointer for a given name, but ONLY if the attribute has
+ exactly one slot function. The name must be an interned string. */
+static void **
+resolve_slotdups(PyTypeObject *type, PyObject *name)
+{
+ /* XXX Maybe this could be optimized more -- but is it worth it? */
+
+ /* pname and ptrs act as a little cache */
+ static PyObject *pname;
+ static slotdef *ptrs[MAX_EQUIV];
+ slotdef *p, **pp;
+ void **res, **ptr;
+
+ if (pname != name) {
+ /* Collect all slotdefs that match name into ptrs. */
+ pname = name;
+ pp = ptrs;
+ for (p = slotdefs; p->name_strobj; p++) {
+ if (p->name_strobj == name)
+ *pp++ = p;
+ }
+ *pp = NULL;
+ }
+
+ /* Look in all matching slots of the type; if exactly one of these has
+ a filled-in slot, return its value. Otherwise return NULL. */
+ res = NULL;
+ for (pp = ptrs; *pp; pp++) {
+ ptr = slotptr(type, (*pp)->offset);
+ if (ptr == NULL || *ptr == NULL)
+ continue;
+ if (res != NULL)
+ return NULL;
+ res = ptr;
+ }
+ return res;
+}
+
+/* Common code for update_these_slots() and fixup_slot_dispatchers(). This
+ does some incredibly complex thinking and then sticks something into the
+ slot. (It sees if the adjacent slotdefs for the same slot have conflicting
+ interests, and then stores a generic wrapper or a specific function into
+ the slot.) Return a pointer to the next slotdef with a different offset,
+ because that's convenient for fixup_slot_dispatchers(). */
+static slotdef *
+update_one_slot(PyTypeObject *type, slotdef *p)
+{
+ PyObject *descr;
+ PyWrapperDescrObject *d;
+ void *generic = NULL, *specific = NULL;
+ int use_generic = 0;
+ int offset = p->offset;
+ void **ptr = slotptr(type, offset);
+
+ if (ptr == NULL) {
+ do {
+ ++p;
+ } while (p->offset == offset);
+ return p;
+ }
+ do {
+ descr = _PyType_Lookup(type, p->name_strobj);
+ if (descr == NULL)
+ continue;
+ if (descr->ob_type == &PyWrapperDescr_Type) {
+ void **tptr = resolve_slotdups(type, p->name_strobj);
+ if (tptr == NULL || tptr == ptr)
+ generic = p->function;
+ d = (PyWrapperDescrObject *)descr;
+ if (d->d_base->wrapper == p->wrapper &&
+ PyType_IsSubtype(type, d->d_type))
+ {
+ if (specific == NULL ||
+ specific == d->d_wrapped)
+ specific = d->d_wrapped;
+ else
+ use_generic = 1;
+ }
+ }
+ else {
+ use_generic = 1;
+ generic = p->function;
+ }
+ } while ((++p)->offset == offset);
+ if (specific && !use_generic)
+ *ptr = specific;
+ else
+ *ptr = generic;
+ return p;
+}
+
staticforward int recurse_down_subclasses(PyTypeObject *type,
slotdef **pp, PyObject *name);
+/* In the type, update the slots whose slotdefs are gathered in the pp0 array,
+ and then do the same for all this type's subtypes. */
static int
update_these_slots(PyTypeObject *type, slotdef **pp0, PyObject *name)
{
slotdef **pp;
- for (pp = pp0; *pp; pp++) {
- slotdef *p = *pp;
- PyObject *descr;
- PyWrapperDescrObject *d;
- void *generic = NULL, *specific = NULL;
- int use_generic = 0;
- int offset = p->offset;
- void **ptr = slotptr(type, offset);
- if (ptr == NULL)
- continue;
- do {
- descr = _PyType_Lookup(type, p->name_strobj);
- if (descr == NULL)
- continue;
- generic = p->function;
- if (descr->ob_type == &PyWrapperDescr_Type) {
- d = (PyWrapperDescrObject *)descr;
- if (d->d_base->wrapper == p->wrapper &&
- PyType_IsSubtype(type, d->d_type)) {
- if (specific == NULL ||
- specific == d->d_wrapped)
- specific = d->d_wrapped;
- else
- use_generic = 1;
- }
- }
- else
- use_generic = 1;
- } while ((++p)->offset == offset);
- if (specific && !use_generic)
- *ptr = specific;
- else
- *ptr = generic;
- }
+ for (pp = pp0; *pp; pp++)
+ update_one_slot(type, *pp);
return recurse_down_subclasses(type, pp0, name);
}
+/* Update the slots whose slotdefs are gathered in the pp array in all (direct
+ or indirect) subclasses of type. */
static int
recurse_down_subclasses(PyTypeObject *type, slotdef **pp, PyObject *name)
{
@@ -3815,6 +3891,8 @@
return 0;
}
+/* Comparison function for qsort() to compare slotdefs by their offset, and
+ for equal offset by their address (to force a stable sort). */
static int
slotdef_cmp(const void *aa, const void *bb)
{
@@ -3826,6 +3904,8 @@
return a - b;
}
+/* Initialize the slotdefs table by adding interned string objects for the
+ names and sorting the entries. */
static void
init_slotdefs(void)
{
@@ -3837,17 +3917,18 @@
for (p = slotdefs; p->name; p++) {
p->name_strobj = PyString_InternFromString(p->name);
if (!p->name_strobj)
- Py_FatalError("XXX ouch");
+ Py_FatalError("Out of memory interning slotdef names");
}
qsort((void *)slotdefs, (size_t)(p-slotdefs), sizeof(slotdef),
slotdef_cmp);
initialized = 1;
}
+/* Update the slots after assignment to a class (type) attribute. */
static int
update_slot(PyTypeObject *type, PyObject *name)
{
- slotdef *ptrs[10];
+ slotdef *ptrs[MAX_EQUIV];
slotdef *p;
slotdef **pp;
int offset;
@@ -3867,74 +3948,22 @@
--p;
*pp = p;
}
+ if (ptrs[0] == NULL)
+ return 0; /* Not an attribute that affects any slots */
return update_these_slots(type, ptrs, name);
}
+/* Store the proper functions in the slot dispatches at class (type)
+ definition time, based upon which operations the class overrides in its
+ dict. */
static void
fixup_slot_dispatchers(PyTypeObject *type)
{
slotdef *p;
- PyObject *mro, *descr;
- PyWrapperDescrObject *d;
- int i, n, offset;
- void **ptr;
- void *generic, *specific;
- int use_generic;
init_slotdefs();
- mro = type->tp_mro;
- assert(PyTuple_Check(mro));
- n = PyTuple_GET_SIZE(mro);
- for (p = slotdefs; p->name; ) {
- offset = p->offset;
- ptr = slotptr(type, offset);
- if (!ptr) {
- do {
- ++p;
- } while (p->offset == offset);
- continue;
- }
- generic = specific = NULL;
- use_generic = 0;
- do {
- descr = NULL;
- for (i = 0; i < n; i++) {
- PyObject *b = PyTuple_GET_ITEM(mro, i);
- PyObject *dict = NULL;
- if (PyType_Check(b))
- dict = ((PyTypeObject *)b)->tp_dict;
- else if (PyClass_Check(b))
- dict = ((PyClassObject *)b)->cl_dict;
- if (dict != NULL) {
- descr = PyDict_GetItem(
- dict, p->name_strobj);
- if (descr != NULL)
- break;
- }
- }
- if (descr == NULL)
- continue;
- generic = p->function;
- if (descr->ob_type == &PyWrapperDescr_Type) {
- d = (PyWrapperDescrObject *)descr;
- if (d->d_base->wrapper == p->wrapper &&
- PyType_IsSubtype(type, d->d_type))
- {
- if (specific == NULL ||
- specific == d->d_wrapped)
- specific = d->d_wrapped;
- else
- use_generic = 1;
- }
- }
- else
- use_generic = 1;
- } while ((++p)->offset == offset);
- if (specific && !use_generic)
- *ptr = specific;
- else
- *ptr = generic;
- }
+ for (p = slotdefs; p->name; )
+ p = update_one_slot(type, p);
}
/* This function is called by PyType_Ready() to populate the type's