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
move all declarations to top of their blocks
  • Loading branch information
@embg
embg committed Mar 13, 2017
commit 934d83f0b993e1b2ec6270094364ac95630e1f14
10 changes: 7 additions & 3 deletions Objects/listobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1947,15 +1947,16 @@ unsafe_object_compare(PyObject* v, PyObject* w, MergeState* ms)
assert(v->ob_type == w->ob_type &&
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.

It would be more helpful to use two separate asserts. In case of the failure we could know what condition is false.

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.

Does list.sort() sorts in-place? Can the content of the list be modified during sorting? If this is true, then the condition v->ob_type == w->ob_type can be false.

Copy link
Copy Markdown
Contributor Author

@embg embg Mar 15, 2017 •
edited
Loading

Choose a reason for hiding this comment

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

Yes, you are correct. ppperry gave an explicit counterexample to this. It's OK, though, because I added the following:

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

However, I should get rid of the ob_type assertion: it could legitimately fail.

v->ob_type->tp_richcompare != NULL);
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.

Is it possible that v->ob_type is changed during sorting? If this is true, than the condition v->ob_type->tp_richcompare != NULL can be false.

#endif
if (v == w) return 0;
int ok;
Copy link
Copy Markdown
Member

@tim-one tim-one Mar 13, 2017

Choose a reason for hiding this comment

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

In a debug build, the declaration of ok still isn't at the top of the block. If you look at virtually any of CPython's implementation, you'll see that declarations immediately follow a block's opening {'

Copy link
Copy Markdown
Contributor Author

@embg embg Mar 13, 2017

Choose a reason for hiding this comment

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

Right, sorry! Fixed (won't show up until I file a new PR, though)

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.

Current style guide allows declarations not at the start of the block.


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);
if (res == NULL)
return -1;
int ok;

if (PyBool_Check(res)){
Copy link
Copy Markdown
Member

@tim-one tim-one Mar 13, 2017

Choose a reason for hiding this comment

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

Right before this line, should add

if (res == Py_NotImplemented) {
    Py_DECREF(res);
    return PyObject_RichCompareBool(v, w, Py_LT);
}

That should repair the latest example on the bug tracker.

Copy link
Copy Markdown
Contributor Author

@embg embg Mar 13, 2017

Choose a reason for hiding this comment

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

thanks, fixed

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.

Add a space before {.

ok = (res == Py_True);
}
Expand Down Expand Up @@ -2040,14 +2041,17 @@ unsafe_tuple_compare(PyObject* v, PyObject* w, MergeState* ms)
Py_SIZE(v) > 0 &&
Py_SIZE(w) > 0);
#endif
if (v == w) return 0;

PyTupleObject *vt, *wt;
Py_ssize_t i;
Py_ssize_t vlen, wlen;

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

int ok;

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.


/* Is v[0] < w[0]? */
int k = (*(ms->tuple_elem_compare))(vt->ob_item[0], wt->ob_item[0], ms);
Expand Down