diff --git a/Objects/stringlib/partition.h b/Objects/stringlib/partition.h
new file mode 100644
index 0000000..498bc19
--- /dev/null
+++ b/Objects/stringlib/partition.h
@@ -0,0 +1,50 @@
+/* stringlib: partition implementation */
+
+#ifndef STRINGLIB_PARTITION_H
+#define STRINGLIB_PARTITION_H
+
+#include "stringlib/fastsearch.h"
+
+Py_LOCAL(PyObject*)
+partition(PyObject* str_obj, const STRINGLIB_CHAR* str, Py_ssize_t str_len,
+	  PyObject* sep_obj, const STRINGLIB_CHAR* sep, Py_ssize_t sep_len)
+{
+    PyObject* out;
+    Py_ssize_t pos;
+
+    if (sep_len == 0) {
+        PyErr_SetString(PyExc_ValueError, "empty separator");
+	return NULL;
+    }
+
+    out = PyTuple_New(3);
+    if (!out)
+	return NULL;
+
+    pos = fastsearch(str, str_len, sep, sep_len, FAST_SEARCH);
+
+    if (pos < 0) {
+	Py_INCREF(str_obj);
+	PyTuple_SET_ITEM(out, 0, (PyObject*) str_obj);
+	Py_INCREF(STRINGLIB_EMPTY);
+	PyTuple_SET_ITEM(out, 1, (PyObject*) STRINGLIB_EMPTY);
+	Py_INCREF(STRINGLIB_EMPTY);
+	PyTuple_SET_ITEM(out, 2, (PyObject*) STRINGLIB_EMPTY);
+	return out;
+    }
+
+    PyTuple_SET_ITEM(out, 0, STRINGLIB_NEW(str, pos));
+    Py_INCREF(sep_obj);
+    PyTuple_SET_ITEM(out, 1, sep_obj);
+    pos += sep_len;
+    PyTuple_SET_ITEM(out, 2, STRINGLIB_NEW(str + pos, str_len - pos));
+
+    if (PyErr_Occurred()) {
+	Py_DECREF(out);
+	return NULL;
+    }
+
+    return out;
+}
+
+#endif
diff --git a/Objects/stringobject.c b/Objects/stringobject.c
index 138ebfe..3790bfa 100644
--- a/Objects/stringobject.c
+++ b/Objects/stringobject.c
@@ -772,8 +772,11 @@
 #ifdef USE_FAST
 
 #define STRINGLIB_CHAR char
+#define STRINGLIB_NEW PyString_FromStringAndSize
+#define STRINGLIB_EMPTY nullstring
 
 #include "stringlib/fastsearch.h"
+#include "stringlib/partition.h"
 
 #endif
 
@@ -1541,9 +1544,8 @@
 static PyObject *
 string_partition(PyStringObject *self, PyObject *sep_obj)
 {
-	Py_ssize_t len = PyString_GET_SIZE(self), sep_len, pos;
+	Py_ssize_t str_len = PyString_GET_SIZE(self), sep_len;
 	const char *str = PyString_AS_STRING(self), *sep;
-	PyObject * out;
 
 	if (PyString_Check(sep_obj)) {
 		sep = PyString_AS_STRING(sep_obj);
@@ -1556,38 +1558,7 @@
 	else if (PyObject_AsCharBuffer(sep_obj, &sep, &sep_len))
 		return NULL;
 
-	if (sep_len == 0) {
-		PyErr_SetString(PyExc_ValueError, "empty separator");
-		return NULL;
-	}
-
-	out = PyTuple_New(3);
-	if (!out)
-		return NULL;
-
-	pos = fastsearch(str, len, sep, sep_len, FAST_SEARCH);
-	if (pos < 0) {
-		Py_INCREF(self);
-		PyTuple_SET_ITEM(out, 0, (PyObject*) self);
-		Py_INCREF(nullstring);
-		PyTuple_SET_ITEM(out, 1, (PyObject*) nullstring);
-		Py_INCREF(nullstring);
-		PyTuple_SET_ITEM(out, 2, (PyObject*) nullstring);
-	} else {
-		PyObject* obj;
-		PyTuple_SET_ITEM(out, 0, PyString_FromStringAndSize(str, pos));
-		Py_INCREF(sep_obj);
-		PyTuple_SET_ITEM(out, 1, sep_obj);
-		pos += sep_len;
-		obj = PyString_FromStringAndSize(str + pos, len - pos);
-		PyTuple_SET_ITEM(out, 2, obj);
-		if (PyErr_Occurred()) {
-			Py_DECREF(out);
-			return NULL;
-		}
-	}
-
-	return out;
+	return partition((PyObject*)self, str, str_len, sep_obj, sep, sep_len);
 }
 
 Py_LOCAL(PyObject *)
diff --git a/Objects/unicodeobject.c b/Objects/unicodeobject.c
index 7ce9215..0ebc30a 100644
--- a/Objects/unicodeobject.c
+++ b/Objects/unicodeobject.c
@@ -3856,7 +3856,13 @@
 
 #define STRINGLIB_CHAR Py_UNICODE
 
+#define STRINGLIB_NEW PyUnicode_FromUnicode
+
+#define STRINGLIB_EMPTY unicode_empty
+
 #include "stringlib/fastsearch.h"
+#include "stringlib/partition.h"
+
 
 Py_LOCAL(Py_ssize_t) count(PyUnicodeObject *self,
                            Py_ssize_t start,
@@ -6197,59 +6203,26 @@
 {
     PyObject* str_obj;
     PyObject* sep_obj;
-    Py_UNICODE *str, *sep;
-    Py_ssize_t len, sep_len, pos;
     PyObject* out;
-    
+
     str_obj = PyUnicode_FromObject(str_in);
     if (!str_obj)
 	return NULL;
     sep_obj = PyUnicode_FromObject(sep_in);
-    if (!sep_obj)
-        goto error;
-
-    str = PyUnicode_AS_UNICODE(str_obj);
-    len = PyUnicode_GET_SIZE(str_obj);
-
-    sep = PyUnicode_AS_UNICODE(sep_obj);
-    sep_len = PyUnicode_GET_SIZE(sep_obj);
-
-    if (sep_len == 0) {
-        PyErr_SetString(PyExc_ValueError, "empty separator");
-        goto error;
+    if (!sep_obj) {
+        Py_DECREF(str_obj);
+        return NULL;
     }
 
-    out = PyTuple_New(3);
-    if (!out)
-        goto error;
+    out = partition(
+        str_obj, PyUnicode_AS_UNICODE(str_obj), PyUnicode_GET_SIZE(str_obj),
+        sep_obj, PyUnicode_AS_UNICODE(sep_obj), PyUnicode_GET_SIZE(sep_obj)
+        );
 
-    pos = fastsearch(str, len, sep, sep_len, FAST_SEARCH);
-    if (pos < 0) {
-        Py_INCREF(str_obj);
-        PyTuple_SET_ITEM(out, 0, (PyObject*) str_obj);
-        Py_INCREF(unicode_empty);
-        PyTuple_SET_ITEM(out, 1, (PyObject*) unicode_empty);
-        Py_INCREF(unicode_empty);
-        PyTuple_SET_ITEM(out, 2, (PyObject*) unicode_empty);
-    } else {
-        PyObject* obj;
-        PyTuple_SET_ITEM(out, 0, PyUnicode_FromUnicode(str, pos));
-        Py_INCREF(sep_obj);
-        PyTuple_SET_ITEM(out, 1, sep_obj);
-        obj = PyUnicode_FromUnicode(str + sep_len + pos, len - sep_len - pos);
-        PyTuple_SET_ITEM(out, 2, obj);
-        if (PyErr_Occurred()) {
-            Py_DECREF(out);
-            goto error;
-        }
-    }
+    Py_DECREF(sep_obj);
+    Py_DECREF(str_obj);
 
     return out;
-
-error:
-    Py_XDECREF(sep_obj);
-    Py_DECREF(str_obj);
-    return NULL;
 }
 
 PyDoc_STRVAR(partition__doc__,