Slight performance hack that also avoids requiring the existence of thread

state for dictionaries that have only been indexed by string keys.

See the comments in SourceForge for more.

This closes SourceForge patch #101309.

1 files changed, 124 insertions, 12 deletions

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 621ed73..37111d2 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -19,6 +19,9 @@ redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES.
 
 #define MINSIZE 4
 
+/* define this out if you don't want conversion statistics on exit */
+#undef SHOW_CONVERSION_COUNTS
+
 /*
 Table of irreducible polynomials to efficiently cycle through
 GF(2^n)-{0}, 2<=n<=30.
@@ -82,14 +85,33 @@ of non-NULL, non-dummy keys.
 To avoid slowing down lookups on a near-full table, we resize the table
 when it is more than half filled.
 */
-typedef struct {
+typedef struct dictobject dictobject;
+struct dictobject {
 	PyObject_HEAD
 	int ma_fill;
 	int ma_used;
 	int ma_size;
 	int ma_poly;
 	dictentry *ma_table;
-} dictobject;
+	dictentry *(*ma_lookup)(dictobject *mp, PyObject *key, long hash);
+};
+
+/* forward declarations */
+static dictentry *
+lookdict_string(dictobject *mp, PyObject *key, long hash);
+
+#ifdef SHOW_CONVERSION_COUNTS
+static long created = 0L;
+static long converted = 0L;
+
+static void
+show_counts(void)
+{
+	fprintf(stderr, "created %ld string dicts\n", created);
+	fprintf(stderr, "converted %ld to normal dicts\n", converted);
+	fprintf(stderr, "%.2f%% conversion rate\n", (100.0*converted)/created);
+}
+#endif
 
 PyObject *
 PyDict_New(void)
@@ -99,6 +121,9 @@ PyDict_New(void)
 		dummy = PyString_FromString("<dummy key>");
 		if (dummy == NULL)
 			return NULL;
+#ifdef SHOW_CONVERSION_COUNTS
+		Py_AtExit(show_counts);
+#endif
 	}
 	mp = PyObject_NEW(dictobject, &PyDict_Type);
 	if (mp == NULL)
@@ -108,6 +133,10 @@ PyDict_New(void)
 	mp->ma_table = NULL;
 	mp->ma_fill = 0;
 	mp->ma_used = 0;
+	mp->ma_lookup = lookdict_string;
+#ifdef SHOW_CONVERSION_COUNTS
+	++created;
+#endif
 	PyObject_GC_Init(mp);
 	return (PyObject *)mp;
 }
@@ -129,6 +158,10 @@ All arithmetic on hash should ignore overflow.
 
 (This version is due to Reimer Behrends, some ideas are also due to
 Jyrki Alakuijala and Vladimir Marangozov.)
+
+This function must never return NULL; failures are indicated by returning
+a dictentry* for which the me_value field is NULL.  Exceptions are never
+reported by this function, and outstanding exceptions are maintained.
 */
 static dictentry *
 lookdict(dictobject *mp, PyObject *key, register long hash)
@@ -226,6 +259,83 @@ lookdict(dictobject *mp, PyObject *key, register long hash)
 }
 
 /*
+ * Hacked up version of lookdict which can assume keys are always strings;
+ * this assumption allows testing for errors during PyObject_Compare() to
+ * be dropped; string-string comparisons never raise exceptions.  This also
+ * means we don't need to go through PyObject_Compare(); we can always use
+ * the tp_compare slot of the string type object directly.
+ *
+ * This really only becomes meaningful if proper error handling in lookdict()
+ * is too expensive.
+ */
+static dictentry *
+lookdict_string(dictobject *mp, PyObject *key, register long hash)
+{
+	register int i;
+	register unsigned incr;
+	register dictentry *freeslot;
+	register unsigned int mask = mp->ma_size-1;
+	dictentry *ep0 = mp->ma_table;
+	register dictentry *ep;
+        cmpfunc compare = PyString_Type.tp_compare;
+
+	/* make sure this function doesn't have to handle non-string keys */
+	if (!PyString_Check(key)) {
+#ifdef SHOW_CONVERSION_COUNTS
+		++converted;
+#endif
+		mp->ma_lookup = lookdict;
+		return lookdict(mp, key, hash);
+	}
+	/* We must come up with (i, incr) such that 0 <= i < ma_size
+	   and 0 < incr < ma_size and both are a function of hash */
+	i = (~hash) & mask;
+	/* We use ~hash instead of hash, as degenerate hash functions, such
+	   as for ints <sigh>, can have lots of leading zeros. It's not
+	   really a performance risk, but better safe than sorry. */
+	ep = &ep0[i];
+	if (ep->me_key == NULL || ep->me_key == key)
+		return ep;
+	if (ep->me_key == dummy)
+		freeslot = ep;
+	else {
+		if (ep->me_hash == hash
+                    && compare(ep->me_key, key) == 0) {
+			return ep;
+		}
+		freeslot = NULL;
+	}
+	/* Derive incr from hash, just to make it more arbitrary. Note that
+	   incr must not be 0, or we will get into an infinite loop.*/
+	incr = (hash ^ ((unsigned long)hash >> 3)) & mask;
+	if (!incr)
+		incr = mask;
+	for (;;) {
+		ep = &ep0[(i+incr)&mask];
+		if (ep->me_key == NULL) {
+			if (freeslot != NULL)
+				return freeslot;
+			else
+				return ep;
+		}
+		if (ep->me_key == dummy) {
+			if (freeslot == NULL)
+				freeslot = ep;
+		}
+		else if (ep->me_key == key
+			 || (ep->me_hash == hash
+			     && compare(ep->me_key, key) == 0)) {
+			return ep;
+                }
+		/* Cycle through GF(2^n)-{0} */
+		incr = incr << 1;
+		if (incr > mask)
+			incr ^= mp->ma_poly; /* This will implicitly clear
+						the highest bit */
+	}
+}
+
+/*
 Internal routine to insert a new item into the table.
 Used both by the internal resize routine and by the public insert routine.
 Eats a reference to key and one to value.
@@ -235,7 +345,7 @@ insertdict(register dictobject *mp, PyObject *key, long hash, PyObject *value)
 {
 	PyObject *old_value;
 	register dictentry *ep;
-	ep = lookdict(mp, key, hash);
+	ep = (mp->ma_lookup)(mp, key, hash);
 	if (ep->me_value != NULL) {
 		old_value = ep->me_value;
 		ep->me_value = value;
@@ -312,10 +422,11 @@ PyObject *
 PyDict_GetItem(PyObject *op, PyObject *key)
 {
 	long hash;
+	dictobject *mp = (dictobject *)op;
 	if (!PyDict_Check(op)) {
 		return NULL;
 	}
-	if (((dictobject *)op)->ma_table == NULL)
+	if (mp->ma_table == NULL)
 		return NULL;
 #ifdef CACHE_HASH
 	if (!PyString_Check(key) ||
@@ -328,7 +439,7 @@ PyDict_GetItem(PyObject *op, PyObject *key)
 			return NULL;
 		}
 	}
-	return lookdict((dictobject *)op, key, hash) -> me_value;
+	return (mp->ma_lookup)(mp, key, hash)->me_value;
 }
 
 int
@@ -400,7 +511,7 @@ PyDict_DelItem(PyObject *op, PyObject *key)
 	mp = (dictobject *)op;
 	if (((dictobject *)op)->ma_table == NULL)
 		goto empty;
-	ep = lookdict(mp, key, hash);
+	ep = (mp->ma_lookup)(mp, key, hash);
 	if (ep->me_value == NULL) {
 	empty:
 		PyErr_SetObject(PyExc_KeyError, key);
@@ -583,7 +694,7 @@ dict_subscript(dictobject *mp, register PyObject *key)
 		if (hash == -1)
 			return NULL;
 	}
-	v = lookdict(mp, key, hash) -> me_value;
+	v = (mp->ma_lookup)(mp, key, hash) -> me_value;
 	if (v == NULL)
 		PyErr_SetObject(PyExc_KeyError, key);
 	else
@@ -912,8 +1023,8 @@ dict_compare(dictobject *a, dictobject *b)
 			if (bhash == -1)
 				PyErr_Clear(); /* Don't want errors here */
 		}
-		aval = lookdict(a, akey, ahash) -> me_value;
-		bval = lookdict(b, bkey, bhash) -> me_value;
+		aval = (a->ma_lookup)(a, akey, ahash) -> me_value;
+		bval = (b->ma_lookup)(b, bkey, bhash) -> me_value;
 		res = PyObject_Compare(aval, bval);
 		if (res != 0)
 			break;
@@ -948,7 +1059,8 @@ dict_has_key(register dictobject *mp, PyObject *args)
 		if (hash == -1)
 			return NULL;
 	}
-	ok = mp->ma_size != 0 && lookdict(mp, key, hash)->me_value != NULL;
+	ok = (mp->ma_size != 0
+	      && (mp->ma_lookup)(mp, key, hash)->me_value != NULL);
 	return PyInt_FromLong(ok);
 }
 
@@ -974,7 +1086,7 @@ dict_get(register dictobject *mp, PyObject *args)
 		if (hash == -1)
 			return NULL;
 	}
-	val = lookdict(mp, key, hash)->me_value;
+	val = (mp->ma_lookup)(mp, key, hash)->me_value;
 
   finally:
 	if (val == NULL)
@@ -1006,7 +1118,7 @@ dict_setdefault(register dictobject *mp, PyObject *args)
 		if (hash == -1)
 			return NULL;
 	}
-	val = lookdict(mp, key, hash)->me_value;
+	val = (mp->ma_lookup)(mp, key, hash)->me_value;
 
   finally:
 	if (val == NULL) {