diff --git a/mercurial/dirs.c b/mercurial/dirs.c
--- a/mercurial/dirs.c
+++ b/mercurial/dirs.c
@@ -9,7 +9,6 @@
 
 #define PY_SSIZE_T_CLEAN
 #include <Python.h>
-#include <string.h>
 #include "util.h"
 
 /*
@@ -33,19 +32,23 @@ static inline Py_ssize_t _finddir(PyObje
 {
 	const char *s = PyString_AS_STRING(path);
 
-	const char *ret = strchr(s + pos, '/');
-	return (ret != NULL) ? (ret - s) : -1;
+	while (pos != -1) {
+		if (s[pos] == '/')
+			break;
+		pos -= 1;
+	}
+
+	return pos;
 }
 
 static int _addpath(PyObject *dirs, PyObject *path)
 {
-	char *cpath = PyString_AS_STRING(path);
-	Py_ssize_t len = PyString_GET_SIZE(path);
-	Py_ssize_t pos = -1;
+	const char *cpath = PyString_AS_STRING(path);
+	Py_ssize_t pos = PyString_GET_SIZE(path);
 	PyObject *key = NULL;
 	int ret = -1;
 
-	while ((pos = _finddir(path, pos + 1)) != -1) {
+	while ((pos = _finddir(path, pos - 1)) != -1) {
 		PyObject *val;
 
 		/* It's likely that every prefix already has an entry
@@ -53,18 +56,10 @@ static int _addpath(PyObject *dirs, PyOb
 		   deallocating a string for each prefix we check. */
 		if (key != NULL)
 			((PyStringObject *)key)->ob_shash = -1;
-		else if (pos != 0) {
-			/* pos >= 1, which means that len >= 2. This is
-			   guaranteed to produce a non-interned string. */
-			key = PyString_FromStringAndSize(cpath, len);
-			if (key == NULL)
-				goto bail;
-		} else {
-			/* pos == 0, which means we need to increment the dir
-			   count for the empty string. We need to make sure we
-			   don't muck around with interned strings, so throw it
-			   away later. */
-			key = PyString_FromString("");
+		else {
+			/* Force Python to not reuse a small shared string. */
+			key = PyString_FromStringAndSize(cpath,
+							 pos < 2 ? 2 : pos);
 			if (key == NULL)
 				goto bail;
 		}
@@ -74,10 +69,6 @@ static int _addpath(PyObject *dirs, PyOb
 		val = PyDict_GetItem(dirs, key);
 		if (val != NULL) {
 			PyInt_AS_LONG(val) += 1;
-			if (pos != 0)
-				PyString_AS_STRING(key)[pos] = '/';
-			else
-				key = NULL;
 			continue;
 		}
 
@@ -92,9 +83,6 @@ static int _addpath(PyObject *dirs, PyOb
 		Py_DECREF(val);
 		if (ret == -1)
 			goto bail;
-
-		/* Clear the key out since we've already exposed it to Python
-		   and can't mutate it further. */
 		Py_CLEAR(key);
 	}
 	ret = 0;
@@ -107,11 +95,11 @@ bail:
 
 static int _delpath(PyObject *dirs, PyObject *path)
 {
-	Py_ssize_t pos = -1;
+	Py_ssize_t pos = PyString_GET_SIZE(path);
 	PyObject *key = NULL;
 	int ret = -1;
 
-	while ((pos = _finddir(path, pos + 1)) != -1) {
+	while ((pos = _finddir(path, pos - 1)) != -1) {
 		PyObject *val;
 
 		key = PyString_FromStringAndSize(PyString_AS_STRING(path), pos);