[Python-checkins] bpo-40889: Optimize dict.items() ^ dict.items() (GH-20718)
Dennis Sweeney
webhook-mailer at python.org
Wed Jun 10 01:57:09 EDT 2020
https://github.com/python/cpython/commit/07d81128124f2b574808e33267c38b104b42ae2a
commit: 07d81128124f2b574808e33267c38b104b42ae2a
branch: master
author: Dennis Sweeney <36520290+sweeneyde at users.noreply.github.com>
committer: GitHub <noreply at github.com>
date: 2020-06-10T14:56:56+09:00
summary:
bpo-40889: Optimize dict.items() ^ dict.items() (GH-20718)
files:
A Misc/NEWS.d/next/Core and Builtins/2020-06-08-22-46-33.bpo-40889.vIBl-W.rst
M Lib/test/test_dict.py
M Objects/dictobject.c
diff --git a/Lib/test/test_dict.py b/Lib/test/test_dict.py
index 6b8596fff6a9f..5c08810f879b1 100644
--- a/Lib/test/test_dict.py
+++ b/Lib/test/test_dict.py
@@ -697,6 +697,16 @@ def test_dictview_set_operations_on_items(self):
self.assertEqual(k1 ^ k2, {(3,3)})
self.assertEqual(k1 ^ k3, {(1,1), (2,2), (4,4)})
+ def test_items_symmetric_difference(self):
+ rr = random.randrange
+ for _ in range(100):
+ left = {x:rr(3) for x in range(20) if rr(2)}
+ right = {x:rr(3) for x in range(20) if rr(2)}
+ with self.subTest(left=left, right=right):
+ expected = set(left.items()) ^ set(right.items())
+ actual = left.items() ^ right.items()
+ self.assertEqual(actual, expected)
+
def test_dictview_mixed_set_operations(self):
# Just a few for .keys()
self.assertTrue({1:1}.keys() == {1})
diff --git a/Misc/NEWS.d/next/Core and Builtins/2020-06-08-22-46-33.bpo-40889.vIBl-W.rst b/Misc/NEWS.d/next/Core and Builtins/2020-06-08-22-46-33.bpo-40889.vIBl-W.rst
new file mode 100644
index 0000000000000..0ab1a261e3e6e
--- /dev/null
+++ b/Misc/NEWS.d/next/Core and Builtins/2020-06-08-22-46-33.bpo-40889.vIBl-W.rst
@@ -0,0 +1 @@
+Improved the performance of symmetric difference operations on dictionary item views. Patch by Dennis Sweeney.
\ No newline at end of file
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index c4d5da51f3193..1bb8cfdab2b68 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -4409,9 +4409,99 @@ dictviews_or(PyObject* self, PyObject *other)
return result;
}
+static PyObject *
+dictitems_xor(PyObject *self, PyObject *other)
+{
+ assert(PyDictItems_Check(self));
+ assert(PyDictItems_Check(other));
+ PyObject *d1 = (PyObject *)((_PyDictViewObject *)self)->dv_dict;
+ PyObject *d2 = (PyObject *)((_PyDictViewObject *)other)->dv_dict;
+
+ PyObject *temp_dict = PyDict_Copy(d1);
+ if (temp_dict == NULL) {
+ return NULL;
+ }
+ PyObject *result_set = PySet_New(NULL);
+ if (result_set == NULL) {
+ Py_CLEAR(temp_dict);
+ return NULL;
+ }
+
+ PyObject *key = NULL, *val1 = NULL, *val2 = NULL;
+ Py_ssize_t pos = 0;
+ Py_hash_t hash;
+
+ while (_PyDict_Next(d2, &pos, &key, &val2, &hash)) {
+ Py_INCREF(key);
+ Py_INCREF(val2);
+ val1 = _PyDict_GetItem_KnownHash(temp_dict, key, hash);
+
+ int to_delete;
+ if (val1 == NULL) {
+ if (PyErr_Occurred()) {
+ goto error;
+ }
+ to_delete = 0;
+ }
+ else {
+ Py_INCREF(val1);
+ to_delete = PyObject_RichCompareBool(val1, val2, Py_EQ);
+ if (to_delete < 0) {
+ goto error;
+ }
+ }
+
+ if (to_delete) {
+ if (_PyDict_DelItem_KnownHash(temp_dict, key, hash) < 0) {
+ goto error;
+ }
+ }
+ else {
+ PyObject *pair = PyTuple_Pack(2, key, val2);
+ if (pair == NULL) {
+ goto error;
+ }
+ if (PySet_Add(result_set, pair) < 0) {
+ Py_DECREF(pair);
+ goto error;
+ }
+ Py_DECREF(pair);
+ }
+ Py_DECREF(key);
+ Py_XDECREF(val1);
+ Py_DECREF(val2);
+ }
+ key = val1 = val2 = NULL;
+
+ _Py_IDENTIFIER(items);
+ PyObject *remaining_pairs = _PyObject_CallMethodIdNoArgs(temp_dict,
+ &PyId_items);
+ if (remaining_pairs == NULL) {
+ goto error;
+ }
+ if (_PySet_Update(result_set, remaining_pairs) < 0) {
+ Py_DECREF(remaining_pairs);
+ goto error;
+ }
+ Py_DECREF(temp_dict);
+ Py_DECREF(remaining_pairs);
+ return result_set;
+
+error:
+ Py_XDECREF(temp_dict);
+ Py_XDECREF(result_set);
+ Py_XDECREF(key);
+ Py_XDECREF(val1);
+ Py_XDECREF(val2);
+ return NULL;
+}
+
static PyObject*
dictviews_xor(PyObject* self, PyObject *other)
{
+ if (PyDictItems_Check(self) && PyDictItems_Check(other)) {
+ return dictitems_xor(self, other);
+ }
PyObject *result = dictviews_to_set(self);
if (result == NULL) {
return NULL;
More information about the Python-checkins
mailing list