Author: antoine.pitrou Date: Tue Nov 30 23:23:20 2010 New Revision: 86905 Log: Issue #8685: Speed up set difference `a - b` when source set `a` is much larger than operand `b`. Patch by Andrew Bennetts. Modified: python/branches/py3k/Misc/NEWS python/branches/py3k/Objects/setobject.c Modified: python/branches/py3k/Misc/NEWS ============================================================================== --- python/branches/py3k/Misc/NEWS (original) +++ python/branches/py3k/Misc/NEWS Tue Nov 30 23:23:20 2010 @@ -10,6 +10,9 @@ Core and Builtins ----------------- +- Issue #8685: Speed up set difference ``a - b`` when source set ``a`` is + much larger than operand ``b``. Patch by Andrew Bennetts. + - Issue #10518: Bring back the callable() builtin. - Issue #8879. Add os.link support for Windows. Modified: python/branches/py3k/Objects/setobject.c ============================================================================== --- python/branches/py3k/Objects/setobject.c (original) +++ python/branches/py3k/Objects/setobject.c Tue Nov 30 23:23:20 2010 @@ -1525,6 +1525,20 @@ "Remove all elements of another set from this set."); static PyObject * +set_copy_and_difference(PySetObject *so, PyObject *other) +{ + PyObject *result; + + result = set_copy(so); + if (result == NULL) + return NULL; + if (set_difference_update_internal((PySetObject *) result, other) != -1) + return result; + Py_DECREF(result); + return NULL; +} + +static PyObject * set_difference(PySetObject *so, PyObject *other) { PyObject *result; @@ -1532,13 +1546,13 @@ Py_ssize_t pos = 0; if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) { - result = set_copy(so); - if (result == NULL) - return NULL; - if (set_difference_update_internal((PySetObject *)result, other) != -1) - return result; - Py_DECREF(result); - return NULL; + return set_copy_and_difference(so, other); + } + + /* If len(so) much more than len(other), it's more efficient to simply copy + * so and then iterate other looking for common elements. */ + if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) { + return set_copy_and_difference(so, other); } result = make_new_set_basetype(Py_TYPE(so), NULL); @@ -1560,6 +1574,7 @@ return result; } + /* Iterate over so, checking for common elements in other. */ while (set_next(so, &pos, &entry)) { int rv = set_contains_entry((PySetObject *)other, entry); if (rv == -1) {