[Python-checkins] bpo-24700: Add a fast path for comparing array.array of equal type (#3009)
Antoine Pitrou
webhook-mailer at python.org
Thu Aug 17 08:46:09 EDT 2017
https://github.com/python/cpython/commit/7c17e2304b9387f321c813516bf134e4f0bd332a
commit: 7c17e2304b9387f321c813516bf134e4f0bd332a
branch: master
author: Adrian Wielgosik <adrian17 at users.noreply.github.com>
committer: Antoine Pitrou <pitrou at free.fr>
date: 2017-08-17T14:46:06+02:00
summary:
bpo-24700: Add a fast path for comparing array.array of equal type (#3009)
files:
A Misc/NEWS.d/next/Library/2017-08-08-15-14-34.bpo-24700.44mvNV.rst
M Lib/test/test_array.py
M Modules/arraymodule.c
diff --git a/Lib/test/test_array.py b/Lib/test/test_array.py
index d67f9195eba..e9218f3dd68 100644
--- a/Lib/test/test_array.py
+++ b/Lib/test/test_array.py
@@ -1342,6 +1342,16 @@ class FPTest(NumberTest):
def assertEntryEqual(self, entry1, entry2):
self.assertAlmostEqual(entry1, entry2)
+ def test_nan(self):
+ a = array.array(self.typecode, [float('nan')])
+ b = array.array(self.typecode, [float('nan')])
+ self.assertIs(a != b, True)
+ self.assertIs(a == b, False)
+ self.assertIs(a > b, False)
+ self.assertIs(a >= b, False)
+ self.assertIs(a < b, False)
+ self.assertIs(a <= b, False)
+
def test_byteswap(self):
a = array.array(self.typecode, self.example)
self.assertRaises(TypeError, a.byteswap, 42)
diff --git a/Misc/NEWS.d/next/Library/2017-08-08-15-14-34.bpo-24700.44mvNV.rst b/Misc/NEWS.d/next/Library/2017-08-08-15-14-34.bpo-24700.44mvNV.rst
new file mode 100644
index 00000000000..a78172e0423
--- /dev/null
+++ b/Misc/NEWS.d/next/Library/2017-08-08-15-14-34.bpo-24700.44mvNV.rst
@@ -0,0 +1,2 @@
+Optimize array.array comparison. It is now from 10x up to 70x faster when
+comparing arrays holding values of the same integer type.
\ No newline at end of file
diff --git a/Modules/arraymodule.c b/Modules/arraymodule.c
index 06461c38036..1d9a4f11d87 100644
--- a/Modules/arraymodule.c
+++ b/Modules/arraymodule.c
@@ -31,6 +31,7 @@ struct arraydescr {
int itemsize;
PyObject * (*getitem)(struct arrayobject *, Py_ssize_t);
int (*setitem)(struct arrayobject *, Py_ssize_t, PyObject *);
+ int (*compareitems)(const void *, const void *, Py_ssize_t);
const char *formats;
int is_integer_type;
int is_signed;
@@ -518,6 +519,28 @@ d_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
return 0;
}
+#define DEFINE_COMPAREITEMS(code, type) \
+ static int \
+ code##_compareitems(const void *lhs, const void *rhs, Py_ssize_t length) \
+ { \
+ const type *a = lhs, *b = rhs; \
+ for (Py_ssize_t i = 0; i < length; ++i) \
+ if (a[i] != b[i]) \
+ return a[i] < b[i] ? -1 : 1; \
+ return 0; \
+ }
+
+DEFINE_COMPAREITEMS(b, signed char)
+DEFINE_COMPAREITEMS(BB, unsigned char)
+DEFINE_COMPAREITEMS(u, Py_UNICODE)
+DEFINE_COMPAREITEMS(h, short)
+DEFINE_COMPAREITEMS(HH, unsigned short)
+DEFINE_COMPAREITEMS(i, int)
+DEFINE_COMPAREITEMS(II, unsigned int)
+DEFINE_COMPAREITEMS(l, long)
+DEFINE_COMPAREITEMS(LL, unsigned long)
+DEFINE_COMPAREITEMS(q, long long)
+DEFINE_COMPAREITEMS(QQ, unsigned long long)
/* Description of types.
*
@@ -525,19 +548,19 @@ d_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
* typecode.
*/
static const struct arraydescr descriptors[] = {
- {'b', 1, b_getitem, b_setitem, "b", 1, 1},
- {'B', 1, BB_getitem, BB_setitem, "B", 1, 0},
- {'u', sizeof(Py_UNICODE), u_getitem, u_setitem, "u", 0, 0},
- {'h', sizeof(short), h_getitem, h_setitem, "h", 1, 1},
- {'H', sizeof(short), HH_getitem, HH_setitem, "H", 1, 0},
- {'i', sizeof(int), i_getitem, i_setitem, "i", 1, 1},
- {'I', sizeof(int), II_getitem, II_setitem, "I", 1, 0},
- {'l', sizeof(long), l_getitem, l_setitem, "l", 1, 1},
- {'L', sizeof(long), LL_getitem, LL_setitem, "L", 1, 0},
- {'q', sizeof(long long), q_getitem, q_setitem, "q", 1, 1},
- {'Q', sizeof(long long), QQ_getitem, QQ_setitem, "Q", 1, 0},
- {'f', sizeof(float), f_getitem, f_setitem, "f", 0, 0},
- {'d', sizeof(double), d_getitem, d_setitem, "d", 0, 0},
+ {'b', 1, b_getitem, b_setitem, b_compareitems, "b", 1, 1},
+ {'B', 1, BB_getitem, BB_setitem, BB_compareitems, "B", 1, 0},
+ {'u', sizeof(Py_UNICODE), u_getitem, u_setitem, u_compareitems, "u", 0, 0},
+ {'h', sizeof(short), h_getitem, h_setitem, h_compareitems, "h", 1, 1},
+ {'H', sizeof(short), HH_getitem, HH_setitem, HH_compareitems, "H", 1, 0},
+ {'i', sizeof(int), i_getitem, i_setitem, i_compareitems, "i", 1, 1},
+ {'I', sizeof(int), II_getitem, II_setitem, II_compareitems, "I", 1, 0},
+ {'l', sizeof(long), l_getitem, l_setitem, l_compareitems, "l", 1, 1},
+ {'L', sizeof(long), LL_getitem, LL_setitem, LL_compareitems, "L", 1, 0},
+ {'q', sizeof(long long), q_getitem, q_setitem, q_compareitems, "q", 1, 1},
+ {'Q', sizeof(long long), QQ_getitem, QQ_setitem, QQ_compareitems, "Q", 1, 0},
+ {'f', sizeof(float), f_getitem, f_setitem, NULL, "f", 0, 0},
+ {'d', sizeof(double), d_getitem, d_setitem, NULL, "d", 0, 0},
{'\0', 0, 0, 0, 0, 0, 0} /* Sentinel */
};
@@ -664,6 +687,31 @@ array_richcompare(PyObject *v, PyObject *w, int op)
return res;
}
+ if (va->ob_descr == wa->ob_descr && va->ob_descr->compareitems != NULL) {
+ /* Fast path:
+ arrays with same types can have their buffers compared directly */
+ Py_ssize_t common_length = Py_MIN(Py_SIZE(va), Py_SIZE(wa));
+ int result = va->ob_descr->compareitems(va->ob_item, wa->ob_item,
+ common_length);
+ if (result == 0)
+ goto compare_sizes;
+
+ int cmp;
+ switch (op) {
+ case Py_LT: cmp = result < 0; break;
+ case Py_LE: cmp = result <= 0; break;
+ case Py_EQ: cmp = result == 0; break;
+ case Py_NE: cmp = result != 0; break;
+ case Py_GT: cmp = result > 0; break;
+ case Py_GE: cmp = result >= 0; break;
+ default: return NULL; /* cannot happen */
+ }
+ PyObject *res = cmp ? Py_True : Py_False;
+ Py_INCREF(res);
+ return res;
+ }
+
+
/* Search for the first index where items are different */
k = 1;
for (i = 0; i < Py_SIZE(va) && i < Py_SIZE(wa); i++) {
@@ -685,14 +733,17 @@ array_richcompare(PyObject *v, PyObject *w, int op)
if (k) {
/* No more items to compare -- compare sizes */
+ compare_sizes: ;
Py_ssize_t vs = Py_SIZE(va);
Py_ssize_t ws = Py_SIZE(wa);
int cmp;
switch (op) {
case Py_LT: cmp = vs < ws; break;
case Py_LE: cmp = vs <= ws; break;
- case Py_EQ: cmp = vs == ws; break;
- case Py_NE: cmp = vs != ws; break;
+ /* If the lengths were not equal,
+ the earlier fast-path check would have caught that. */
+ case Py_EQ: assert(vs == ws); cmp = 1; break;
+ case Py_NE: assert(vs == ws); cmp = 0; break;
case Py_GT: cmp = vs > ws; break;
case Py_GE: cmp = vs >= ws; break;
default: return NULL; /* cannot happen */
More information about the Python-checkins
mailing list