[Python-checkins] cpython: Issues #26289 and #26315: Optimize floor/modulo div for single-digit longs
yury.selivanov
python-checkins at python.org
Thu Feb 11 10:26:39 EST 2016
https://hg.python.org/cpython/rev/37bacf3fa1f5
changeset: 100230:37bacf3fa1f5
user: Yury Selivanov <yselivanov at sprymix.com>
date: Thu Feb 11 10:26:27 2016 -0500
summary:
Issues #26289 and #26315: Optimize floor/modulo div for single-digit longs
Microbenchmarks show 2-2.5x improvement. Built-in 'divmod' function
is now also ~10% faster.
-m timeit -s "x=22331" "x//2;x//-3;x//4;x//5;x//-6;x//7;x//8;x//-99;x//100;"
with patch: 0.321 without patch: 0.633
-m timeit -s "x=22331" "x%2;x%3;x%-4;x%5;x%6;x%-7;x%8;x%99;x%-100;"
with patch: 0.224 without patch: 0.66
Big thanks to Serhiy Storchaka, Mark Dickinson and Victor Stinner for
thorow code reviews and algorithms improvements.
files:
Lib/test/test_long.py | 33 ++++++++++++
Misc/NEWS | 4 +
Objects/longobject.c | 79 +++++++++++++++++++++++++++++++
3 files changed, 116 insertions(+), 0 deletions(-)
diff --git a/Lib/test/test_long.py b/Lib/test/test_long.py
--- a/Lib/test/test_long.py
+++ b/Lib/test/test_long.py
@@ -689,6 +689,20 @@
self.assertRaises(OverflowError, int, float('-inf'))
self.assertRaises(ValueError, int, float('nan'))
+ def test_mod_division(self):
+ with self.assertRaises(ZeroDivisionError):
+ _ = 1 % 0
+
+ self.assertEqual(13 % 10, 3)
+ self.assertEqual(-13 % 10, 7)
+ self.assertEqual(13 % -10, -7)
+ self.assertEqual(-13 % -10, -3)
+
+ self.assertEqual(12 % 4, 0)
+ self.assertEqual(-12 % 4, 0)
+ self.assertEqual(12 % -4, 0)
+ self.assertEqual(-12 % -4, 0)
+
def test_true_division(self):
huge = 1 << 40000
mhuge = -huge
@@ -723,6 +737,25 @@
for zero in ["huge / 0", "mhuge / 0"]:
self.assertRaises(ZeroDivisionError, eval, zero, namespace)
+ def test_floordiv(self):
+ with self.assertRaises(ZeroDivisionError):
+ _ = 1 // 0
+
+ self.assertEqual(2 // 3, 0)
+ self.assertEqual(2 // -3, -1)
+ self.assertEqual(-2 // 3, -1)
+ self.assertEqual(-2 // -3, 0)
+
+ self.assertEqual(-11 // -3, 3)
+ self.assertEqual(-11 // 3, -4)
+ self.assertEqual(11 // -3, -4)
+ self.assertEqual(11 // 3, 3)
+
+ self.assertEqual(-12 // -3, 4)
+ self.assertEqual(-12 // 3, -4)
+ self.assertEqual(12 // -3, -4)
+ self.assertEqual(12 // 3, 4)
+
def check_truediv(self, a, b, skip_small=True):
"""Verify that the result of a/b is correctly rounded, by
comparing it with a pure Python implementation of correctly
diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -176,6 +176,10 @@
- Issue #26288: Optimize PyLong_AsDouble.
+- Issues #26289 and #26315: Optimize floor and modulo division for
+ single-digit longs. Microbenchmarks show 2-2.5x improvement. Built-in
+ 'divmod' function is now also ~10% faster.
+
Library
-------
diff --git a/Objects/longobject.c b/Objects/longobject.c
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -3502,6 +3502,52 @@
return (PyObject *)z;
}
+/* Fast modulo division for single-digit longs. */
+static PyObject *
+fast_mod(PyLongObject *a, PyLongObject *b)
+{
+ sdigit left = a->ob_digit[0];
+ sdigit right = b->ob_digit[0];
+ sdigit mod;
+
+ assert(Py_ABS(Py_SIZE(a)) == 1);
+ assert(Py_ABS(Py_SIZE(b)) == 1);
+
+ if (Py_SIZE(a) == Py_SIZE(b)) {
+ /* 'a' and 'b' have the same sign. */
+ mod = left % right;
+ }
+ else {
+ /* Either 'a' or 'b' is negative. */
+ mod = right - 1 - (left - 1) % right;
+ }
+
+ return PyLong_FromLong(mod * Py_SIZE(b));
+}
+
+/* Fast floor division for single-digit longs. */
+static PyObject *
+fast_floor_div(PyLongObject *a, PyLongObject *b)
+{
+ sdigit left = a->ob_digit[0];
+ sdigit right = b->ob_digit[0];
+ sdigit div;
+
+ assert(Py_ABS(Py_SIZE(a)) == 1);
+ assert(Py_ABS(Py_SIZE(b)) == 1);
+
+ if (Py_SIZE(a) == Py_SIZE(b)) {
+ /* 'a' and 'b' have the same sign. */
+ div = left / right;
+ }
+ else {
+ /* Either 'a' or 'b' is negative. */
+ div = -1 - (left - 1) / right;
+ }
+
+ return PyLong_FromLong(div);
+}
+
/* The / and % operators are now defined in terms of divmod().
The expression a mod b has the value a - b*floor(a/b).
The long_divrem function gives the remainder after division of
@@ -3529,6 +3575,30 @@
{
PyLongObject *div, *mod;
+ if (Py_ABS(Py_SIZE(v)) == 1 && Py_ABS(Py_SIZE(w)) == 1) {
+ /* Fast path for single-digit longs */
+ div = NULL;
+ if (pdiv != NULL) {
+ div = (PyLongObject *)fast_floor_div(v, w);
+ if (div == NULL) {
+ return -1;
+ }
+ }
+ if (pmod != NULL) {
+ mod = (PyLongObject *)fast_mod(v, w);
+ if (mod == NULL) {
+ Py_XDECREF(div);
+ return -1;
+ }
+ *pmod = mod;
+ }
+ if (pdiv != NULL) {
+ /* We only want to set `*pdiv` when `*pmod` is
+ set successfully. */
+ *pdiv = div;
+ }
+ return 0;
+ }
if (long_divrem(v, w, &div, &mod) < 0)
return -1;
if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) ||
@@ -3573,6 +3643,11 @@
PyLongObject *div;
CHECK_BINOP(a, b);
+
+ if (Py_ABS(Py_SIZE(a)) == 1 && Py_ABS(Py_SIZE(b)) == 1) {
+ return fast_floor_div((PyLongObject*)a, (PyLongObject*)b);
+ }
+
if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, NULL) < 0)
div = NULL;
return (PyObject *)div;
@@ -3848,6 +3923,10 @@
CHECK_BINOP(a, b);
+ if (Py_ABS(Py_SIZE(a)) == 1 && Py_ABS(Py_SIZE(b)) == 1) {
+ return fast_mod((PyLongObject*)a, (PyLongObject*)b);
+ }
+
if (l_divmod((PyLongObject*)a, (PyLongObject*)b, NULL, &mod) < 0)
mod = NULL;
return (PyObject *)mod;
--
Repository URL: https://hg.python.org/cpython
More information about the Python-checkins
mailing list