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
fix typo
  • Loading branch information
@embg
embg committed Mar 13, 2017
commit 15f2f01cb80ee95285a1e4fe341bc66cb2d68a5b
2 changes: 1 addition & 1 deletion Objects/listobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1046,7 +1046,7 @@ sortslice_advance(sortslice *slice, Py_ssize_t n)
if (k)

/* Here we define custom comparison functions to optimize for the cases one commonly
* in practice: homogeneous lists, often of one of the basic types. */
* encounters in practice: homogeneous lists, often of one of the basic types. */

/* This struct holds the comparison function and helper functions
* selected in the pre-sort check. */
Expand Down