Skip to content

bpo-28685: Optimize sorted() list.sort() with type-specialized comparisons #582

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
rhettinger merged 50 commits into from
Jan 29, 2018
Merged

bpo-28685: Optimize sorted() list.sort() with type-specialized comparisons #582

Changes from 1 commit
Commits
Show all changes
50 commits
Select commit Hold shift + click to select a range
89c278f
Added data-aware optimizations to list.sort()
embg Mar 8, 2017
2ce5e5e
Removed trailing whitespace from listsort_impl
embg Mar 8, 2017
7d2f44a
fixed typo
embg Mar 8, 2017
d752fc7
Added myself to Misc/ACKS
embg Mar 8, 2017
e19728e
Made ISLT comment more in line with the current text
embg Mar 8, 2017
7e74c27
Remove newline
embg Mar 8, 2017
9c566b1
untabify
embg Mar 8, 2017
8876e26
removed newline
embg Mar 8, 2017
8accd71
simplified description of the tuple compare
embg Mar 9, 2017
1567801
grammar
embg Mar 9, 2017
3820cdb
Bugfix -- gcc ignored the error, but clang caught it!
embg Mar 9, 2017
201a468
Bugfix -- assertion in unsafe_long_compare was phrased incorrectly.
embg Mar 9, 2017
c2a9df2
fix typo
embg Mar 9, 2017
37b15b8
Added if (v == w) return 1; to all compares
embg Mar 11, 2017
e402948
Merge branch 'fastsort' of https://github.com/embg/cpython into fastsort
embg Mar 11, 2017
ed9b21f
Added if (v == w) return 0; to all compares, apologies for previous c…
embg Mar 11, 2017
acf4c9d
Folded CompareFuncs into MergeState and added safety check to unsafe_…
embg Mar 12, 2017
395bc7d
formatting
embg Mar 12, 2017
e677586
formatting
embg Mar 12, 2017
6070c72
don't need (v==w) for ints/strings
embg Mar 12, 2017
294aa1c
went back to i=0 for tuples; we can't infer == from < and >, even wit…
embg Mar 12, 2017
ba05b2a
move all declarations to top of their blocks
embg Mar 13, 2017
40ba266
typo
embg Mar 13, 2017
a175939
typo
embg Mar 13, 2017
f0dc847
added Py_NotImplemented check to unsafe_object_compare
embg Mar 13, 2017
15f87a2
ACTUALLY moved declarations to the tops of blocks
embg Mar 13, 2017
15f2f01
fix typo
embg Mar 9, 2017
6afa847
Added if (v == w) return 0; to all compares, apologies for previous c…
embg Mar 11, 2017
af7c027
Folded CompareFuncs into MergeState and added safety check to unsafe_…
embg Mar 12, 2017
20716cb
formatting
embg Mar 12, 2017
5960fbe
formatting
embg Mar 12, 2017
804807b
don't need (v==w) for ints/strings
embg Mar 12, 2017
5db7158
went back to i=0 for tuples; we can't infer == from < and >, even wit…
embg Mar 12, 2017
934d83f
move all declarations to top of their blocks
embg Mar 13, 2017
c536ed3
typo
embg Mar 13, 2017
0b85ac5
typo
embg Mar 13, 2017
a12d784
added Py_NotImplemented check to unsafe_object_compare
embg Mar 13, 2017
a54a4e4
ACTUALLY moved declarations to the tops of blocks
embg Mar 13, 2017
20172fb
Merge branch 'fastsort' of https://github.com/embg/cpython into fastsort
embg Mar 13, 2017
862c761
Made tuple compare precisely consistent with PyObject_RichCompareBool…
embg Mar 13, 2017
dd302b5
Added tests
embg Mar 15, 2017
ab3d520
Implemented all of serhiy-storchaka's changes
embg Mar 15, 2017
dba3f27
Removed braces at the end of unsafe_tuple_compare
embg Mar 15, 2017
c796422
Fixed test_safe_object_compare
embg Mar 16, 2017
fa19903
Fix spacing around PyObject *
rhettinger Jan 28, 2018
014fd8f
Merge in changes to master
rhettinger Jan 28, 2018
e4679e2
Add news blurb
rhettinger Jan 28, 2018
3b3ce52
Update listsort.txt for the optimization
rhettinger Jan 29, 2018
afed812
Fix whitespace
rhettinger Jan 29, 2018
ebb4c1f
Clean-up and fix tests for mutation of __class__.
rhettinger Jan 29, 2018
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
Prev Previous commit
Next Next commit
ACTUALLY moved declarations to the tops of blocks
  • Loading branch information
@embg
embg committed Mar 13, 2017
commit 15f87a26511b97e5de080122d81f1dd5b7438e23
99 changes: 51 additions & 48 deletions Objects/listobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1942,18 +1942,20 @@ safe_object_compare(PyObject* v, PyObject* w, MergeState* ms)
static int
unsafe_object_compare(PyObject* v, PyObject* w, MergeState* ms)
{
/* Modified from Objects/object.c:PyObject_RichCompareBool, assuming: */
#ifdef Py_DEBUG
assert(v->ob_type == w->ob_type &&
v->ob_type->tp_richcompare != NULL);
#endif
int ok;
int ok; PyObject* res;

/* Modified from Objects/object.c:PyObject_RichCompareBool, assuming: */
#ifdef Py_DEBUG
assert(v->ob_type == w->ob_type &&
v->ob_type->tp_richcompare != NULL);
#endif


if (v == w) return 0;
Copy link
Copy Markdown
Member

@serhiy-storchaka serhiy-storchaka Mar 14, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Split the line before return.

Copy link
Copy Markdown
Contributor Author

@embg embg Mar 15, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This was actually removed -- it turns out you only need to look at addresses when you're doing equality testing.

if (v->ob_type->tp_richcompare != ms->key_richcompare)
return PyObject_RichCompareBool(v, w, Py_LT);

PyObject* res = (*(ms->key_richcompare))(v, w, Py_LT);
res = (*(ms->key_richcompare))(v, w, Py_LT);

if (res == Py_NotImplemented) {
Py_DECREF(res);
Expand All @@ -1975,16 +1977,18 @@ unsafe_object_compare(PyObject* v, PyObject* w, MergeState* ms)
/* Latin string compare: safe for any two latin (one byte per char) strings. */
static int
unsafe_latin_compare(PyObject* v, PyObject* w, MergeState* ms){
Copy link
Copy Markdown
Member

@serhiy-storchaka serhiy-storchaka Mar 14, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Move { to separate line.

/* Modified from Objects/unicodeobject.c:unicode_compare, assuming: */
#ifdef Py_DEBUG
assert(v->ob_type == w->ob_type &&
v->ob_type == &PyUnicode_Type &&
PyUnicode_KIND(v) == PyUnicode_KIND(w) &&
PyUnicode_KIND(v) == PyUnicode_1BYTE_KIND);
#endif
int len, res;

/* Modified from Objects/unicodeobject.c:unicode_compare, assuming: */
#ifdef Py_DEBUG
assert(v->ob_type == w->ob_type &&
v->ob_type == &PyUnicode_Type &&
PyUnicode_KIND(v) == PyUnicode_KIND(w) &&
PyUnicode_KIND(v) == PyUnicode_1BYTE_KIND);
#endif

int len = Py_MIN(PyUnicode_GET_LENGTH(v), PyUnicode_GET_LENGTH(w));
int res = memcmp(PyUnicode_DATA(v), PyUnicode_DATA(w), len);
len = Py_MIN(PyUnicode_GET_LENGTH(v), PyUnicode_GET_LENGTH(w));
res = memcmp(PyUnicode_DATA(v), PyUnicode_DATA(w), len);

return (res != 0 ?
res < 0 :
Expand All @@ -1995,20 +1999,21 @@ unsafe_latin_compare(PyObject* v, PyObject* w, MergeState* ms){
static int
unsafe_long_compare(PyObject *v, PyObject *w, MergeState* ms)
{
/* Modified from Objects/longobject.c:long_compare, assuming: */
#ifdef Py_DEBUG
assert(v->ob_type == w->ob_type &&
v->ob_type == &PyLong_Type &&
Py_ABS(Py_SIZE(v)) <= 1 &&
Py_ABS(Py_SIZE(w)) <= 1);
#endif
PyLongObject *vl, *wl; sdigit v0, w0;

/* Modified from Objects/longobject.c:long_compare, assuming: */
#ifdef Py_DEBUG
assert(v->ob_type == w->ob_type &&
v->ob_type == &PyLong_Type &&
Py_ABS(Py_SIZE(v)) <= 1 &&
Py_ABS(Py_SIZE(w)) <= 1);
#endif

PyLongObject *vl, *wl;
vl = (PyLongObject*)v;
wl = (PyLongObject*)w;

sdigit v0 = Py_SIZE(vl) == 0 ? 0 : (sdigit)vl->ob_digit[0];
sdigit w0 = Py_SIZE(wl) == 0 ? 0 : (sdigit)wl->ob_digit[0];
v0 = Py_SIZE(vl) == 0 ? 0 : (sdigit)vl->ob_digit[0];
w0 = Py_SIZE(wl) == 0 ? 0 : (sdigit)wl->ob_digit[0];

if (Py_SIZE(vl) < 0)
v0 = -v0;
Expand All @@ -2021,13 +2026,13 @@ unsafe_long_compare(PyObject *v, PyObject *w, MergeState* ms)
/* Float compare: compare any two floats. */
static int
unsafe_float_compare(PyObject *v, PyObject *w, MergeState* ms){
Copy link
Copy Markdown
Member

@serhiy-storchaka serhiy-storchaka Mar 14, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Move { to separate line.

/* Modified from Objects/floatobject.c:float_richcompare, assuming: */
#ifdef Py_DEBUG
assert(v->ob_type == w->ob_type &&
v->ob_type == &PyFloat_Type);
#endif
if (v == w) return 0;

/* Modified from Objects/floatobject.c:float_richcompare, assuming: */
#ifdef Py_DEBUG
assert(v->ob_type == w->ob_type &&
v->ob_type == &PyFloat_Type);
#endif
if (v == w) return 0;
return PyFloat_AS_DOUBLE(v) < PyFloat_AS_DOUBLE(w);
}

Expand All @@ -2038,25 +2043,23 @@ unsafe_float_compare(PyObject *v, PyObject *w, MergeState* ms){
* on two levels (as long as [x[0] for x in L] is type-homogeneous.) */
static int
unsafe_tuple_compare(PyObject* v, PyObject* w, MergeState* ms)
{
/* Modified from Objects/tupleobject.c:tuplerichcompare, assuming: */
#ifdef Py_DEBUG
assert(v->ob_type == w->ob_type &&
v->ob_type == &PyTuple_Type &&
Py_SIZE(v) > 0 &&
Py_SIZE(w) > 0);
#endif

{
PyTupleObject *vt, *wt;
Py_ssize_t i;
Py_ssize_t vlen, wlen;
Py_ssize_t i, vlen, wlen;
int k;

/* Modified from Objects/tupleobject.c:tuplerichcompare, assuming: */
#ifdef Py_DEBUG
assert(v->ob_type == w->ob_type &&
v->ob_type == &PyTuple_Type &&
Py_SIZE(v) > 0 &&
Py_SIZE(w) > 0);
#endif

if (v == w) return 0;

vt = (PyTupleObject *)v;
wt = (PyTupleObject *)w;

int k;

if (v == w) return 0;

/* Is v[0] < w[0]? */
k = (*(ms->tuple_elem_compare))(vt->ob_item[0], wt->ob_item[0], ms);
Copy link
Copy Markdown
Member

@serhiy-storchaka serhiy-storchaka Mar 14, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Since specialized comparison is not recursive, wouldn't be safe to pass NULL rather of ms? Just for sure that this parameter is not misused.

Copy link
Copy Markdown
Contributor Author

@embg embg Mar 14, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No. If the compare function is unsafe_object_compare, then it could need the ms struct. For example: [(2**60,), (-2**60,)]. unsafe_long_compare doesn't apply because the ints are too big.

Expand Down