diff --git a/Objects/setobject.c b/Objects/setobject.c
index d489711..0af1f15 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -10,6 +10,20 @@
 #include "Python.h"
 #include "structmember.h"
 
+/* Set a key error with the specified argument, wrapping it in a
+ * tuple automatically so that tuple keys are not unpacked as the
+ * exception arguments. */
+static void
+set_key_error(PyObject *arg)
+{
+	PyObject *tup;
+	tup = PyTuple_Pack(1, arg);
+	if (!tup)
+		return; /* caller will expect error to be set anyway */
+	PyErr_SetObject(PyExc_KeyError, tup);
+	Py_DECREF(tup);
+}
+
 /* This must be >= 1. */
 #define PERTURB_SHIFT 5
 
@@ -179,11 +193,13 @@
 		if (entry->key == dummy && freeslot == NULL)
 			freeslot = entry;
 	}
+	assert(0);	/* NOT REACHED */
+	return 0;
 }
 
 /*
 Internal routine to insert a new key into the table.
-Used both by the internal resize routine and by the public insert routine.
+Used by the public insert routine.
 Eats a reference to key.
 */
 static int
@@ -216,6 +232,35 @@
 }
 
 /*
+Internal routine used by set_table_resize() to insert an item which is
+known to be absent from the set.  This routine also assumes that
+the set contains no deleted entries.  Besides the performance benefit,
+using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
+Note that no refcounts are changed by this routine; if needed, the caller
+is responsible for incref'ing `key`.
+*/
+static void
+set_insert_clean(register PySetObject *so, PyObject *key, long hash)
+{
+	register size_t i;
+	register size_t perturb;
+	register size_t mask = (size_t)so->mask;
+	setentry *table = so->table;
+	register setentry *entry;
+
+	i = hash & mask;
+	entry = &table[i];
+	for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {
+		i = (i << 2) + i + perturb + 1;
+		entry = &table[i & mask];
+	}
+	so->fill++;
+	entry->key = key;
+	entry->hash = hash;
+	so->used++;
+}
+
+/*
 Restructure the table by allocating a new table and reinserting all
 keys again.  When entries have been deleted, the new table may
 actually be smaller than the old one.
@@ -296,11 +341,7 @@
 		} else {
 			/* ACTIVE */
 			--i;
-			if(set_insert_key(so, entry->key, entry->hash) == -1) {
-				if (is_oldtable_malloced)
-					PyMem_DEL(oldtable);
-				return -1;
-			}
+			set_insert_clean(so, entry->key, entry->hash);
 		}
 	}
 
@@ -319,8 +360,10 @@
 	assert(so->fill <= so->mask);  /* at least one empty slot */
 	n_used = so->used;
 	Py_INCREF(entry->key);
-	if (set_insert_key(so, entry->key, entry->hash) == -1)
+	if (set_insert_key(so, entry->key, entry->hash) == -1) {
+		Py_DECREF(entry->key);
 		return -1;
+	}
 	if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
 		return 0;
 	return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
@@ -1155,7 +1198,12 @@
 		}
 
 		while (set_next((PySetObject *)other, &pos, &entry)) {
-			if (set_contains_entry(so, entry)) {
+			int rv = set_contains_entry(so, entry);
+			if (rv == -1) {
+				Py_DECREF(result);
+				return NULL;
+			}
+			if (rv) {
 				if (set_add_entry(result, entry) == -1) {
 					Py_DECREF(result);
 					return NULL;
@@ -1172,8 +1220,27 @@
 	}
 
 	while ((key = PyIter_Next(it)) != NULL) {
-		if (set_contains_key(so, key)) {
-			if (set_add_key(result, key) == -1) {
+		int rv;
+		setentry entry;
+		long hash = PyObject_Hash(key);
+
+		if (hash == -1) {
+			Py_DECREF(it);
+			Py_DECREF(result);
+			Py_DECREF(key);
+			return NULL;
+		}
+		entry.hash = hash;
+		entry.key = key;
+		rv = set_contains_entry(so, &entry);
+		if (rv == -1) {
+			Py_DECREF(it);
+			Py_DECREF(result);
+			Py_DECREF(key);
+			return NULL;
+		}
+		if (rv) {
+			if (set_add_entry(result, &entry) == -1) {
 				Py_DECREF(it);
 				Py_DECREF(result);
 				Py_DECREF(key);
@@ -1249,7 +1316,8 @@
 		Py_ssize_t pos = 0;
 
 		while (set_next((PySetObject *)other, &pos, &entry))
-			set_discard_entry(so, entry);
+			if (set_discard_entry(so, entry) == -1)
+				return -1;
 	} else {
 		PyObject *key, *it;
 		it = PyObject_GetIter(other);
@@ -1312,17 +1380,26 @@
 			entrycopy.hash = entry->hash;
 			entrycopy.key = entry->key;
 			if (!PyDict_Contains(other, entry->key)) {
-				if (set_add_entry((PySetObject *)result, &entrycopy) == -1)
+				if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
+					Py_DECREF(result);
 					return NULL;
+				}
 			}
 		}
 		return result;
 	}
 
 	while (set_next(so, &pos, &entry)) {
-		if (!set_contains_entry((PySetObject *)other, entry)) {
-			if (set_add_entry((PySetObject *)result, entry) == -1)
+		int rv = set_contains_entry((PySetObject *)other, entry);
+		if (rv == -1) {
+			Py_DECREF(result);
+			return NULL;
+		}
+		if (!rv) {
+			if (set_add_entry((PySetObject *)result, entry) == -1) {
+				Py_DECREF(result);
 				return NULL;
+			}
 		}
 	}
 	return result;
@@ -1374,11 +1451,18 @@
 		PyObject *value;
 		int rv;
 		while (PyDict_Next(other, &pos, &key, &value)) {
-			rv = set_discard_key(so, key);
+			setentry an_entry;
+			long hash = PyObject_Hash(key);
+
+			if (hash == -1)
+				return NULL;
+			an_entry.hash = hash;
+			an_entry.key = key;
+			rv = set_discard_entry(so, &an_entry);
 			if (rv == -1)
 				return NULL;
 			if (rv == DISCARD_NOTFOUND) {
-				if (set_add_key(so, key) == -1)
+				if (set_add_entry(so, &an_entry) == -1)
 					return NULL;
 			}
 		}
@@ -1481,7 +1565,10 @@
 		Py_RETURN_FALSE;
 
 	while (set_next(so, &pos, &entry)) {
-		if (!set_contains_entry((PySetObject *)other, entry))
+		int rv = set_contains_entry((PySetObject *)other, entry);
+		if (rv == -1)
+			return NULL;
+		if (!rv)
 			Py_RETURN_FALSE;
 	}
 	Py_RETURN_TRUE;
@@ -1628,7 +1715,7 @@
 		Py_DECREF(tmpkey);
 		return result;
 	} else if (rv == DISCARD_NOTFOUND) {
-		PyErr_SetObject(PyExc_KeyError, key);
+		set_key_error(key);
 		return NULL;
 	}
 	Py_RETURN_NONE;