Skip to content

/rust

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.

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

Tracking issue for unstable sort in libcore #40585

Closed
alexcrichton opened this Issue Mar 16, 2017 · 6 comments

Comments

Assignees
No one assigned
Labels
B-unstable T-libs final-comment-period
Projects
None yet
Milestone
No milestone
4 participants
@alexcrichton @scottmcm @stjepang @rfcbot
@alexcrichton
Copy link
Member

alexcrichton commented Mar 16, 2017

Tracking issue for rust-lang/rfcs#1884

@alexcrichton alexcrichton added B-RFC-approved T-libs labels Mar 16, 2017

@alexcrichton alexcrichton referenced this issue Mar 16, 2017

Merged

Add unstable sort to libcore #1884

steveklabnik added a commit to steveklabnik/rust that referenced this issue Mar 16, 2017

@steveklabnik
add sort_unstable to unstable book 
cc rust-lang#40585
3d01e1a

@steveklabnik steveklabnik referenced this issue Mar 16, 2017

Merged

add sort_unstable to unstable book #40586

frewsxcv added a commit to frewsxcv/rust that referenced this issue Mar 17, 2017

@frewsxcv
Rollup merge of rust-lang#40586 - steveklabnik:add-unstable-sort-to-u… 
…nstable-book, r=frewsxcv

add sort_unstable to unstable book

cc rust-lang#40585
b4436f3

frewsxcv added a commit to frewsxcv/rust that referenced this issue Mar 17, 2017

@frewsxcv
Rollup merge of rust-lang#40586 - steveklabnik:add-unstable-sort-to-u… 
…nstable-book, r=frewsxcv

add sort_unstable to unstable book

cc rust-lang#40585
ee03f19

frewsxcv added a commit to frewsxcv/rust that referenced this issue Mar 17, 2017

@frewsxcv
Rollup merge of rust-lang#40586 - steveklabnik:add-unstable-sort-to-u… 
…nstable-book, r=frewsxcv

add sort_unstable to unstable book

cc rust-lang#40585
7569ddc

frewsxcv added a commit to frewsxcv/rust that referenced this issue Mar 17, 2017

@frewsxcv
Rollup merge of rust-lang#40586 - steveklabnik:add-unstable-sort-to-u… 
…nstable-book, r=frewsxcv

add sort_unstable to unstable book

cc rust-lang#40585
365ae32

frewsxcv added a commit to frewsxcv/rust that referenced this issue Mar 17, 2017

@frewsxcv
Rollup merge of rust-lang#40586 - steveklabnik:add-unstable-sort-to-u… 
…nstable-book, r=frewsxcv

add sort_unstable to unstable book

cc rust-lang#40585
3bec563

This was referenced Mar 17, 2017

Merged
Merged

frewsxcv added a commit to frewsxcv/rust that referenced this issue Mar 18, 2017

@frewsxcv
Rollup merge of rust-lang#40619 - stjepang:unstable-book-sort-unstabl… 
…e, r=steveklabnik

Add docs for sort_unstable to unstable book

Tracking issue for the feature: rust-lang#40585

r? @steveklabnik
45d9514

bors added a commit that referenced this issue Mar 21, 2017

@bors
Auto merge of #40601 - stjepang:sort-unstable, r=alexcrichton 
Implement feature sort_unstable

Tracking issue for the feature: #40585

This is essentially integration of [pdqsort](https://github.com/stjepang/pdqsort) into libcore.

There's plenty of unsafe blocks to review. The heart of pdqsort is `fn partition_in_blocks` and is probably the most challenging function to understand. It requires some patience, but let me know if you find it too difficult - comments could always be improved.

#### Changes

* Added `sort_unstable` feature.
* Tweaked insertion sort constants for stable sort. Sorting integers is now up to 5% slower, but sorting big elements is much faster (in particular, `sort_large_big_random` is 35% faster). The old constants were highly optimized for sorting integers, so overall the configuration is more balanced now. A minor regression in case of integers is forgivable as we recently had performance improvements (#39538) that completely make up for it.
* Removed some uninteresting sort benchmarks.
* Added a new sort benchmark for string sorting.

#### Benchmarks

The following table compares stable and unstable sorting:
```
name                                 stable ns/iter        unstable ns/iter     diff ns/iter   diff %
slice::sort_large_ascending          7,240 (11049 MB/s)    7,380 (10840 MB/s)            140    1.93%
slice::sort_large_big_random         1,454,138 (880 MB/s)  910,269 (1406 MB/s)      -543,869  -37.40%
slice::sort_large_descending         13,450 (5947 MB/s)    10,895 (7342 MB/s)         -2,555  -19.00%
slice::sort_large_mostly_ascending   204,041 (392 MB/s)    88,639 (902 MB/s)        -115,402  -56.56%
slice::sort_large_mostly_descending  217,109 (368 MB/s)    99,009 (808 MB/s)        -118,100  -54.40%
slice::sort_large_random             477,257 (167 MB/s)    346,028 (231 MB/s)       -131,229  -27.50%
slice::sort_large_random_expensive   21,670,537 (3 MB/s)   22,710,238 (3 MB/s)     1,039,701    4.80%
slice::sort_large_strings            6,284,499 (38 MB/s)   6,410,896 (37 MB/s)       126,397    2.01%
slice::sort_medium_random            3,515 (227 MB/s)      3,327 (240 MB/s)             -188   -5.35%
slice::sort_small_ascending          42 (1904 MB/s)        41 (1951 MB/s)                 -1   -2.38%
slice::sort_small_big_random         503 (2544 MB/s)       514 (2490 MB/s)                11    2.19%
slice::sort_small_descending         72 (1111 MB/s)        69 (1159 MB/s)                 -3   -4.17%
slice::sort_small_random             369 (216 MB/s)        367 (217 MB/s)                 -2   -0.54%
```

Interesting cases:
* Expensive comparison function and string sorting - it's a really close race, but timsort performs a slightly smaller number of comparisons. This is a natural difference of bottom-up merging versus top-down partitioning.
* `large_descending` - unstable sort is faster, but both sorts should have equivalent performance. Both just check whether the slice is descending and if so, they reverse it. I blame LLVM for the discrepancy.

r? @alexcrichton
Loading status checks…
cab4bff

frewsxcv added a commit to frewsxcv/rust that referenced this issue Mar 22, 2017

@frewsxcv
Rollup merge of rust-lang#40619 - stjepang:unstable-book-sort-unstabl… 
…e, r=frewsxcv

Add docs for sort_unstable to unstable book

Tracking issue for the feature: rust-lang#40585

r? @steveklabnik
Loading status checks…
a24c81d

GuillaumeGomez added a commit to GuillaumeGomez/rust that referenced this issue Mar 22, 2017

@GuillaumeGomez
Rollup merge of rust-lang#40619 - stjepang:unstable-book-sort-unstabl… 
…e, r=frewsxcv

Add docs for sort_unstable to unstable book

Tracking issue for the feature: rust-lang#40585

r? @steveklabnik
7455018

frewsxcv added a commit to frewsxcv/rust that referenced this issue Mar 22, 2017

@frewsxcv
Rollup merge of rust-lang#40619 - stjepang:unstable-book-sort-unstabl… 
…e, r=frewsxcv

Add docs for sort_unstable to unstable book

Tracking issue for the feature: rust-lang#40585

r? @steveklabnik
Loading status checks…
5947db1

@SimonSapin SimonSapin referenced this issue Mar 24, 2017

Closed

Replace pdqsort with sort_unstable #16120

@chriskrycho chriskrycho referenced this issue Apr 1, 2017

Closed

Document all features #9

18 of 48 tasks complete
@scottmcm

This comment has been minimized.

Sign in to view
Copy link
Member

scottmcm commented Jun 3, 2017

Is there any work needed here before stabilization?
@stjepang

This comment has been minimized.

Sign in to view
Copy link
Contributor

stjepang commented Jun 3, 2017

@scottmcm There isn't. The feature is implemented and documented.

The final stabilization PR will just have to add one sentence to the docs, that's it (see the FIXMEs in the code).
@alexcrichton

This comment has been minimized.

Sign in to view
Copy link
Member Author

alexcrichton commented Jun 3, 2017

@rfcbot fcp merge

@alexcrichton alexcrichton added B-unstable and removed B-RFC-approved labels Jun 3, 2017

@rfcbot

This comment has been minimized.

Sign in to view
Copy link

rfcbot commented Jun 3, 2017 •
edited by brson

Team member @alexcrichton has proposed to merge this. The next step is review by the rest of the tagged teams:

No concerns currently listed.

Once these reviewers reach consensus, this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.
@rfcbot

This comment has been minimized.

Sign in to view
Copy link

rfcbot commented Jun 21, 2017

🔔 This is now entering its final comment period, as per the review above. 🔔

@rfcbot rfcbot added the final-comment-period label Jun 21, 2017

@rfcbot

This comment has been minimized.

Sign in to view
Copy link

rfcbot commented Jul 1, 2017

The final comment period is now complete.

@stjepang stjepang referenced this issue Jul 2, 2017

Merged

Stabilize feature sort_unstable #43010

bors added a commit that referenced this issue Jul 2, 2017

@bors
Auto merge of #43010 - stjepang:stabilize-sort-unstable, r=alexcrichton 
Stabilize feature sort_unstable

Closes #40585
Loading status checks…
1d2db7b

@bors bors closed this in #43010 Jul 3, 2017

@stjepang stjepang referenced this issue Jul 10, 2017

Closed

Add non-allocating sort function to libcore #790

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.