Skip to content

bpo-24700: Add a fast path for comparing array.array of equal type #3009

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
pitrou merged 1 commit into from
Aug 17, 2017
Merged

bpo-24700: Add a fast path for comparing array.array of equal type #3009

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
10 changes: 10 additions & 0 deletions Lib/test/test_array.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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)
Expand Down
2 changes: 2 additions & 0 deletions Misc/NEWS.d/next/Library/2017-08-08-15-14-34.bpo-24700.44mvNV.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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.
81 changes: 66 additions & 15 deletions Modules/arraymodule.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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;
Expand Down Expand Up @@ -518,26 +519,48 @@ 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.
*
* Don't forget to update typecode_to_mformat_code() if you add a new
* 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 */
};

Expand Down Expand Up @@ -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++) {
Expand All @@ -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 */
Expand Down