* Beef-up testing of str.__contains__() and str.find().

* Speed-up "x in y" where x has more than one character.

The existing code made excessive calls to the expensive memcmp() function.
The new code uses memchr() to rapidly find a start point for memcmp().
In addition to knowing that the first character is a match, the new code
also checks that the last character is a match.  This significantly reduces
the incidence of false starts (saving memcmp() calls and making quadratic
behavior less likely).

Improves the timings on:
    python -m timeit -r7 -s"x='a'*1000" "'ab' in x"
    python -m timeit -r7 -s"x='a'*1000" "'bc' in x"

Once this code has proven itself, then string_find_internal() should refer
to it rather than running its own version.  Also, something similar may
apply to unicode objects.

1 files changed, 26 insertions, 13 deletions

diff --git a/Objects/stringobject.c b/Objects/stringobject.c
index b90221a..0cbf439 100644
--- a/Objects/stringobject.c
+++ b/Objects/stringobject.c
@@ -1002,8 +1002,12 @@ string_slice(register PyStringObject *a, register int i, register int j)
 static int
 string_contains(PyObject *a, PyObject *el)
 {
-	const char *lhs, *rhs, *end;
-	int size;
+	char *s = PyString_AS_STRING(a);
+	const char *sub = PyString_AS_STRING(el);
+	char *last;
+	int len_sub = PyString_GET_SIZE(el);
+	int shortsub;
+	char firstchar, lastchar;
 
 	if (!PyString_CheckExact(el)) {
 #ifdef Py_USING_UNICODE
@@ -1016,20 +1020,29 @@ string_contains(PyObject *a, PyObject *el)
 			return -1;
 		}
 	}
-	size = PyString_GET_SIZE(el);
-	rhs = PyString_AS_STRING(el);
-	lhs = PyString_AS_STRING(a);
 
-	/* optimize for a single character */
-	if (size == 1)
-		return memchr(lhs, *rhs, PyString_GET_SIZE(a)) != NULL;
-
-	end = lhs + (PyString_GET_SIZE(a) - size);
-	while (lhs <= end) {
-		if (memcmp(lhs++, rhs, size) == 0)
+	if (len_sub == 0)
+		return 1;
+	/* last points to one char beyond the start of the rightmost 
+	   substring.  When s<last, there is still room for a possible match
+	   and s[0] through s[len_sub-1] will be in bounds.
+	   shortsub is len_sub minus the last character which is checked
+	   separately just before the memcmp().  That check helps prevent
+	   false starts and saves the setup time for memcmp().
+	*/
+	firstchar = sub[0];
+	shortsub = len_sub - 1;
+	lastchar = sub[shortsub];
+	last = s + PyString_GET_SIZE(a) - len_sub + 1;
+	while (s < last) {
+		s = memchr(s, firstchar, last-s);
+		if (s == NULL)
+			return 0;
+		assert(s < last);
+		if (s[shortsub] == lastchar && memcmp(s, sub, shortsub) == 0)
 			return 1;
+		s++;
 	}
-
 	return 0;
 }