René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Specialization for accurate complex summation in sum()?","articleBody":"# Feature or enhancement\r\n\r\n### Proposal:\r\n\r\nCurrently, sum() builtin lacks any specialization for complex numbers, yet it's usually faster than better pure-python alternatives.\r\n\r\n\u003cdetails\u003e\r\n\r\n\u003csummary\u003ebenchmark sum() wrt pure-python version\u003c/summary\u003e\r\n\r\n```python\r\n# a.py\r\nfrom random import random, seed\r\nseed(1)\r\ndata = [complex(random(), random()) for _ in range(10)]\r\ndef msum(xs):\r\n    it = iter(xs)\r\n    res = next(it)\r\n    for z in it:\r\n        res += z\r\n    return res\r\ndef sum2(xs):\r\n    return complex(sum(_.real for _ in xs),\r\n                   sum(_.imag for _ in xs))\r\n```\r\n\r\n```\r\n$ ./python -m timeit -r11 -unsec -s 'from a import data, msum' 'sum(data)'\r\n500000 loops, best of 11: 963 nsec per loop\r\n$ ./python -m timeit -r11 -unsec -s 'from a import data, msum' 'msum(data)'\r\n200000 loops, best of 11: 1.31e+03 nsec per loop\r\n```\r\n\r\nHardly using sum() component-wise is an option:\r\n```\r\n$ ./python -m timeit -r11 -unsec -s 'from a import data, sum2' 'sum2(data)'\r\n50000 loops, best of 11: 8.56e+03 nsec per loop\r\n```\r\n\r\n--------------------------\r\n\r\n\u003c/details\u003e\r\n\r\nUnfortunately, direct using this builtin in numeric code doesn't make sense, as results are (usually) inaccurate.  It's not too hard to do summation component-wise with math.fsum(), but it's slow and there might be a better way.\r\n\r\nIn #100425 simple algorithm, using compensated summation, was implemented in sum() for floats.  I propose (1) make specialization in sum() for complex numbers, and (2) reuse #100425 code to implement accurate summation of complexes.\r\n\r\n(1) is simple and strightforward, yet it will give some measurable performance boost\r\n\r\n\u003cdetails\u003e\r\n\r\n\u003csummary\u003ebenchmark sum() in the main wrt added specialization for complex\u003c/summary\u003e\r\n\r\n```diff\r\ndiff --git a/Python/bltinmodule.c b/Python/bltinmodule.c\r\nindex 6e50623caf..da0eed584a 100644\r\n--- a/Python/bltinmodule.c\r\n+++ b/Python/bltinmodule.c\r\n@@ -2691,6 +2691,59 @@ builtin_sum_impl(PyObject *module, PyObject *iterable, PyObject *start)\r\n             }\r\n         }\r\n     }\r\n+\r\n+    if (PyComplex_CheckExact(result)) {\r\n+        Py_complex c_result = PyComplex_AsCComplex(result);\r\n+        Py_SETREF(result, NULL);\r\n+        while(result == NULL) {\r\n+            item = PyIter_Next(iter);\r\n+            if (item == NULL) {\r\n+                Py_DECREF(iter);\r\n+                if (PyErr_Occurred())\r\n+                    return NULL;\r\n+                return PyComplex_FromCComplex(c_result);\r\n+            }\r\n+            if (PyComplex_CheckExact(item)) {\r\n+                Py_complex x = PyComplex_AsCComplex(item);\r\n+                c_result.real += x.real;\r\n+                c_result.imag += x.imag;\r\n+                _Py_DECREF_SPECIALIZED(item, _PyFloat_ExactDealloc);\r\n+                continue;\r\n+            }\r\n+            if (PyLong_Check(item)) {\r\n+                long value;\r\n+                int overflow;\r\n+                value = PyLong_AsLongAndOverflow(item, \u0026overflow);\r\n+                if (!overflow) {\r\n+                    c_result.real += (double)value;\r\n+                    c_result.imag += 0.0;\r\n+                    Py_DECREF(item);\r\n+                    continue;\r\n+                }\r\n+            }\r\n+            if (PyFloat_Check(item)) {\r\n+                double value = PyFloat_AS_DOUBLE(item);\r\n+                c_result.real += value;\r\n+                c_result.imag += 0.0;\r\n+                Py_DECREF(item);\r\n+                continue;\r\n+            }\r\n+            result = PyComplex_FromCComplex(c_result);\r\n+            if (result == NULL) {\r\n+                Py_DECREF(item);\r\n+                Py_DECREF(iter);\r\n+                return NULL;\r\n+            }\r\n+            temp = PyNumber_Add(result, item);\r\n+            Py_DECREF(result);\r\n+            Py_DECREF(item);\r\n+            result = temp;\r\n+            if (result == NULL) {\r\n+                Py_DECREF(iter);\r\n+                return NULL;\r\n+            }\r\n+        }\r\n+    }\r\n #endif\r\n \r\n     for(;;) {\r\n```\r\n\r\nmain:\r\n```\r\n$ ./python -m timeit -r11 -unsec -s 'from a import data, msum' 'sum(data)'\r\n500000 loops, best of 11: 963 nsec per loop\r\n```\r\n\r\nwith specialization:\r\n```\r\n$ ./python -m timeit -r11 -unsec -s 'from a import data, msum' 'sum(data)'\r\n500000 loops, best of 11: 606 nsec per loop\r\n```\r\n\r\n--------------------\r\n\r\n\u003c/details\u003e\r\n\r\n(2) also seems to be a no-brain task: simple refactoring of PyFloat specialization should allows us use same core for PyComplex specialization.\r\n\r\nIf there are no objections against - I'll work on a patch.\r\n\r\n\r\n### Has this already been discussed elsewhere?\r\n\r\nThis is a minor feature, which does not need previous discussion elsewhere\r\n\r\n### Links to previous discussion of this feature:\r\n\r\n_No response_\n\n\u003c!-- gh-linked-prs --\u003e\n### Linked PRs\n* gh-121176\n\u003c!-- /gh-linked-prs --\u003e\n","author":{"url":"https://github.com/skirpichev","@type":"Person","name":"skirpichev"},"datePublished":"2024-06-29T09:38:25.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":9},"url":"https://github.com/121149/cpython/issues/121149"}