{"action":"created","comment":{"url":"https://api.github.com/repos/rust-lang/rust/pulls/comments/175281748","pull_request_review_id":104790050,"id":175281748,"diff_hunk":"@@ -1328,12 +1334,72 @@ impl<T> [T] {\n     /// ```\n     #[stable(feature = \"slice_sort_by_key\", since = \"1.7.0\")]\n     #[inline]\n-    pub fn sort_by_key<B, F>(&mut self, mut f: F)\n-        where F: FnMut(&T) -> B, B: Ord\n+    pub fn sort_by_key<K, F>(&mut self, mut f: F)\n+        where F: FnMut(&T) -> K, K: Ord\n     {\n         merge_sort(self, |a, b| f(a).lt(&f(b)));\n     }\n \n+    /// Sorts the slice with a key extraction function.\n+    ///\n+    /// During sorting, the key function is called only once per element.\n+    ///\n+    /// This sort is stable (i.e. does not reorder equal elements) and `O(m n + n log n)`\n+    /// worst-case, where the key function is `O(m)`.\n+    ///\n+    /// For simple key functions (e.g. functions that are property accesses or\n+    /// basic operations), [`sort_by_key`](#method.sort_by_key) is likely to be\n+    /// faster.\n+    ///\n+    /// # Current implementation\n+    ///\n+    /// The current algorithm is an adaptive, iterative merge sort inspired by\n+    /// [timsort](https://en.wikipedia.org/wiki/Timsort).\n+    /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of\n+    /// two or more sorted sequences concatenated one after another.\n+    ///\n+    /// The algorithm allocates temporary storage in a `Vec<(K, usize)>` the length of the slice.\n+    ///\n+    /// # Examples\n+    ///\n+    /// ```\n+    /// let mut v = [-5i32, 4, 1, -3, 2];\n+    ///\n+    /// v.sort_by_cached_key(|k| k.abs());\n+    /// assert!(v == [1, 2, -3, 4, -5]);\n+    /// ```\n+    #[unstable(feature = \"slice_sort_by_cached_key\", issue = \"34447\")]\n+    #[inline]\n+    pub fn sort_by_cached_key<K, F>(&mut self, f: F)\n+        where F: FnMut(&T) -> K, K: Ord\n+    {\n+        // Helper macro for indexing our vector by the smallest possible type, to reduce allocation.\n+        macro_rules! sort_by_key {\n+            ($t:ty, $slice:ident, $f:ident) => ({\n+                let mut indices: Vec<_> =","path":"src/liballoc/slice.rs","position":74,"original_position":70,"commit_id":"8aee82c8c7637885d53f60feae157098c2700d50","original_commit_id":"7378909eb58a9c83df1d731edf384ce8a6bfb5e4","user":{"login":"SimonSapin","id":291359,"avatar_url":"https://avatars0.githubusercontent.com/u/291359?v=4","gravatar_id":"","url":"https://api.github.com/users/SimonSapin","html_url":"https://github.com/SimonSapin","followers_url":"https://api.github.com/users/SimonSapin/followers","following_url":"https://api.github.com/users/SimonSapin/following{/other_user}","gists_url":"https://api.github.com/users/SimonSapin/gists{/gist_id}","starred_url":"https://api.github.com/users/SimonSapin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/SimonSapin/subscriptions","organizations_url":"https://api.github.com/users/SimonSapin/orgs","repos_url":"https://api.github.com/users/SimonSapin/repos","events_url":"https://api.github.com/users/SimonSapin/events{/privacy}","received_events_url":"https://api.github.com/users/SimonSapin/received_events","type":"User","site_admin":false},"body":"Rather than pulling in a full crate (which is mostly about encapsulating stuff in a single type that can be moved as a unit), you can reproduce that functionality with a couple of stack variables. Something like:\r\n\r\n```rust\r\npub fn foo<T>(s: &[T], f: &Fn(&T) -> T) {\r\n    let iter = s.iter().map(f).enumerate().map(|(i, k)| (k, i as u16));\r\n    let mut vec: Vec<_>;\r\n    let mut array: [_; ARRAY_LEN];\r\n    const ARRAY_LEN: usize = 32;\r\n    let len = iter.len();\r\n    let mapped = if len <= ARRAY_LEN {\r\n        array = unsafe {\r\n            std::mem::uninitialized()\r\n        };\r\n        for (x, slot) in iter.zip(&mut array) {\r\n            *slot = x\r\n        }\r\n        &mut array[..len]\r\n    } else {\r\n        vec = iter.collect();\r\n        &mut vec[..]\r\n    };\r\n    // …\r\n}","created_at":"2018-03-18T08:56:51Z","updated_at":"2018-03-18T08:56:51Z","html_url":"https://github.com/rust-lang/rust/pull/48639#discussion_r175281748","pull_request_url":"https://api.github.com/repos/rust-lang/rust/pulls/48639","author_association":"CONTRIBUTOR","_links":{"self":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/comments/175281748"},"html":{"href":"https://github.com/rust-lang/rust/pull/48639#discussion_r175281748"},"pull_request":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/48639"}},"in_reply_to_id":175256852},"pull_request":{"url":"https://api.github.com/repos/rust-lang/rust/pulls/48639","id":172242733,"html_url":"https://github.com/rust-lang/rust/pull/48639","diff_url":"https://github.com/rust-lang/rust/pull/48639.diff","patch_url":"https://github.com/rust-lang/rust/pull/48639.patch","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/48639","number":48639,"state":"open","locked":false,"title":"Add slice::sort_by_cached_key as a memoised sort_by_key","user":{"login":"varkor","id":3943692,"avatar_url":"https://avatars1.githubusercontent.com/u/3943692?v=4","gravatar_id":"","url":"https://api.github.com/users/varkor","html_url":"https://github.com/varkor","followers_url":"https://api.github.com/users/varkor/followers","following_url":"https://api.github.com/users/varkor/following{/other_user}","gists_url":"https://api.github.com/users/varkor/gists{/gist_id}","starred_url":"https://api.github.com/users/varkor/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/varkor/subscriptions","organizations_url":"https://api.github.com/users/varkor/orgs","repos_url":"https://api.github.com/users/varkor/repos","events_url":"https://api.github.com/users/varkor/events{/privacy}","received_events_url":"https://api.github.com/users/varkor/received_events","type":"User","site_admin":false},"body":"At present, `slice::sort_by_key` calls its key function twice for each comparison that is made. When the key function is expensive (which can often be the case when `sort_by_key` is chosen over `sort_by`), this can lead to very suboptimal behaviour.\r\n\r\nTo address this, I've introduced a new slice method, `sort_by_cached_key`, which has identical semantic behaviour to `sort_by_key`, except that it guarantees the key function will only be called once per element.\r\n\r\nWhere there are `n` elements and the key function is `O(m)`:\r\n- `slice::sort_by_cached_key` time complexity is `O(m n log m n)`, compared to `slice::sort_by_key`'s `O(m n + n log n)`.\r\n- `slice::sort_by_cached_key` space complexity remains at `O(n + m)`. (Technically, it now reserves a slice of size `n`, whereas before it reserved a slice of size `n/2`.)\r\n\r\n`slice::sort_unstable_by_key` has not been given an analogue, as it is important that unstable sorts are in-place, which is not a property that is guaranteed here. However, this also means that `slice::sort_unstable_by_key` is likely to be slower than `slice::sort_by_cached_key` when the key function does not have negligible complexity. We might want to explore this trade-off further in the future.\r\n\r\nBenchmarks (for a vector of 100 `i32`s):\r\n```\r\n# Lexicographic: `|x| x.to_string()`\r\ntest bench_sort_by_key ... bench:      112,638 ns/iter (+/- 19,563)\r\ntest bench_sort_by_cached_key ... bench:       15,038 ns/iter (+/- 4,814)\r\n\r\n# Identity: `|x| *x`\r\ntest bench_sort_by_key ... bench:        1,346 ns/iter (+/- 238)\r\ntest bench_sort_by_cached_key ... bench:        1,839 ns/iter (+/- 765)\r\n\r\n# Power: `|x| x.pow(31)`\r\ntest bench_sort_by_key ... bench:        3,624 ns/iter (+/- 738)\r\ntest bench_sort_by_cached_key ... bench:        1,997 ns/iter (+/- 311)\r\n\r\n# Abs: `|x| x.abs()`\r\ntest bench_sort_by_key ... bench:        1,546 ns/iter (+/- 174)\r\ntest bench_sort_by_cached_key ... bench:        1,668 ns/iter (+/- 790)\r\n```\r\n(So it seems functions that are single operations do perform slightly worse with this method, but for pretty much any more complex key, you're better off with this optimisation.)\r\n\r\nI've definitely found myself using expensive keys in the past and wishing this optimisation was made (e.g. for https://github.com/rust-lang/rust/pull/47415). This feels like both desirable and expected behaviour, at the small cost of slightly more stack allocation and minute degradation in performance for extremely trivial keys.\r\n\r\nResolves #34447.","created_at":"2018-03-01T13:55:00Z","updated_at":"2018-03-18T08:56:51Z","closed_at":null,"merged_at":null,"merge_commit_sha":"7054177ff26522316b46625b23f182c7a16ff6d1","assignee":{"login":"bluss","id":3209739,"avatar_url":"https://avatars1.githubusercontent.com/u/3209739?v=4","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false},"assignees":[{"login":"bluss","id":3209739,"avatar_url":"https://avatars1.githubusercontent.com/u/3209739?v=4","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false}],"requested_reviewers":[],"requested_teams":[],"labels":[{"id":583426710,"url":"https://api.github.com/repos/rust-lang/rust/labels/S-waiting-on-review","name":"S-waiting-on-review","color":"d3dddd","default":false}],"milestone":null,"commits_url":"https://api.github.com/repos/rust-lang/rust/pulls/48639/commits","review_comments_url":"https://api.github.com/repos/rust-lang/rust/pulls/48639/comments","review_comment_url":"https://api.github.com/repos/rust-lang/rust/pulls/comments{/number}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/48639/comments","statuses_url":"https://api.github.com/repos/rust-lang/rust/statuses/8aee82c8c7637885d53f60feae157098c2700d50","head":{"label":"varkor:sort_by_key-cached","ref":"sort_by_key-cached","sha":"8aee82c8c7637885d53f60feae157098c2700d50","user":{"login":"varkor","id":3943692,"avatar_url":"https://avatars1.githubusercontent.com/u/3943692?v=4","gravatar_id":"","url":"https://api.github.com/users/varkor","html_url":"https://github.com/varkor","followers_url":"https://api.github.com/users/varkor/followers","following_url":"https://api.github.com/users/varkor/following{/other_user}","gists_url":"https://api.github.com/users/varkor/gists{/gist_id}","starred_url":"https://api.github.com/users/varkor/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/varkor/subscriptions","organizations_url":"https://api.github.com/users/varkor/orgs","repos_url":"https://api.github.com/users/varkor/repos","events_url":"https://api.github.com/users/varkor/events{/privacy}","received_events_url":"https://api.github.com/users/varkor/received_events","type":"User","site_admin":false},"repo":{"id":106295063,"name":"rust","full_name":"varkor/rust","owner":{"login":"varkor","id":3943692,"avatar_url":"https://avatars1.githubusercontent.com/u/3943692?v=4","gravatar_id":"","url":"https://api.github.com/users/varkor","html_url":"https://github.com/varkor","followers_url":"https://api.github.com/users/varkor/followers","following_url":"https://api.github.com/users/varkor/following{/other_user}","gists_url":"https://api.github.com/users/varkor/gists{/gist_id}","starred_url":"https://api.github.com/users/varkor/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/varkor/subscriptions","organizations_url":"https://api.github.com/users/varkor/orgs","repos_url":"https://api.github.com/users/varkor/repos","events_url":"https://api.github.com/users/varkor/events{/privacy}","received_events_url":"https://api.github.com/users/varkor/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/varkor/rust","description":"A safe, concurrent, practical language.","fork":true,"url":"https://api.github.com/repos/varkor/rust","forks_url":"https://api.github.com/repos/varkor/rust/forks","keys_url":"https://api.github.com/repos/varkor/rust/keys{/key_id}","collaborators_url":"https://api.github.com/repos/varkor/rust/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/varkor/rust/teams","hooks_url":"https://api.github.com/repos/varkor/rust/hooks","issue_events_url":"https://api.github.com/repos/varkor/rust/issues/events{/number}","events_url":"https://api.github.com/repos/varkor/rust/events","assignees_url":"https://api.github.com/repos/varkor/rust/assignees{/user}","branches_url":"https://api.github.com/repos/varkor/rust/branches{/branch}","tags_url":"https://api.github.com/repos/varkor/rust/tags","blobs_url":"https://api.github.com/repos/varkor/rust/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/varkor/rust/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/varkor/rust/git/refs{/sha}","trees_url":"https://api.github.com/repos/varkor/rust/git/trees{/sha}","statuses_url":"https://api.github.com/repos/varkor/rust/statuses/{sha}","languages_url":"https://api.github.com/repos/varkor/rust/languages","stargazers_url":"https://api.github.com/repos/varkor/rust/stargazers","contributors_url":"https://api.github.com/repos/varkor/rust/contributors","subscribers_url":"https://api.github.com/repos/varkor/rust/subscribers","subscription_url":"https://api.github.com/repos/varkor/rust/subscription","commits_url":"https://api.github.com/repos/varkor/rust/commits{/sha}","git_commits_url":"https://api.github.com/repos/varkor/rust/git/commits{/sha}","comments_url":"https://api.github.com/repos/varkor/rust/comments{/number}","issue_comment_url":"https://api.github.com/repos/varkor/rust/issues/comments{/number}","contents_url":"https://api.github.com/repos/varkor/rust/contents/{+path}","compare_url":"https://api.github.com/repos/varkor/rust/compare/{base}...{head}","merges_url":"https://api.github.com/repos/varkor/rust/merges","archive_url":"https://api.github.com/repos/varkor/rust/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/varkor/rust/downloads","issues_url":"https://api.github.com/repos/varkor/rust/issues{/number}","pulls_url":"https://api.github.com/repos/varkor/rust/pulls{/number}","milestones_url":"https://api.github.com/repos/varkor/rust/milestones{/number}","notifications_url":"https://api.github.com/repos/varkor/rust/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/varkor/rust/labels{/name}","releases_url":"https://api.github.com/repos/varkor/rust/releases{/id}","deployments_url":"https://api.github.com/repos/varkor/rust/deployments","created_at":"2017-10-09T14:34:36Z","updated_at":"2018-03-17T21:30:31Z","pushed_at":"2018-03-18T01:29:16Z","git_url":"git://github.com/varkor/rust.git","ssh_url":"git@github.com:varkor/rust.git","clone_url":"https://github.com/varkor/rust.git","svn_url":"https://github.com/varkor/rust","homepage":"https://www.rust-lang.org","size":351733,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":true,"has_projects":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":1,"license":{"key":"other","name":"Other","spdx_id":null,"url":null},"forks":0,"open_issues":1,"watchers":0,"default_branch":"master"}},"base":{"label":"rust-lang:master","ref":"master","sha":"adf2135adc4a65a78ba053f04c29d7fe0468eb87","user":{"login":"rust-lang","id":5430905,"avatar_url":"https://avatars1.githubusercontent.com/u/5430905?v=4","gravatar_id":"","url":"https://api.github.com/users/rust-lang","html_url":"https://github.com/rust-lang","followers_url":"https://api.github.com/users/rust-lang/followers","following_url":"https://api.github.com/users/rust-lang/following{/other_user}","gists_url":"https://api.github.com/users/rust-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/rust-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rust-lang/subscriptions","organizations_url":"https://api.github.com/users/rust-lang/orgs","repos_url":"https://api.github.com/users/rust-lang/repos","events_url":"https://api.github.com/users/rust-lang/events{/privacy}","received_events_url":"https://api.github.com/users/rust-lang/received_events","type":"Organization","site_admin":false},"repo":{"id":724712,"name":"rust","full_name":"rust-lang/rust","owner":{"login":"rust-lang","id":5430905,"avatar_url":"https://avatars1.githubusercontent.com/u/5430905?v=4","gravatar_id":"","url":"https://api.github.com/users/rust-lang","html_url":"https://github.com/rust-lang","followers_url":"https://api.github.com/users/rust-lang/followers","following_url":"https://api.github.com/users/rust-lang/following{/other_user}","gists_url":"https://api.github.com/users/rust-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/rust-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rust-lang/subscriptions","organizations_url":"https://api.github.com/users/rust-lang/orgs","repos_url":"https://api.github.com/users/rust-lang/repos","events_url":"https://api.github.com/users/rust-lang/events{/privacy}","received_events_url":"https://api.github.com/users/rust-lang/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/rust-lang/rust","description":"A safe, concurrent, practical language.","fork":false,"url":"https://api.github.com/repos/rust-lang/rust","forks_url":"https://api.github.com/repos/rust-lang/rust/forks","keys_url":"https://api.github.com/repos/rust-lang/rust/keys{/key_id}","collaborators_url":"https://api.github.com/repos/rust-lang/rust/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/rust-lang/rust/teams","hooks_url":"https://api.github.com/repos/rust-lang/rust/hooks","issue_events_url":"https://api.github.com/repos/rust-lang/rust/issues/events{/number}","events_url":"https://api.github.com/repos/rust-lang/rust/events","assignees_url":"https://api.github.com/repos/rust-lang/rust/assignees{/user}","branches_url":"https://api.github.com/repos/rust-lang/rust/branches{/branch}","tags_url":"https://api.github.com/repos/rust-lang/rust/tags","blobs_url":"https://api.github.com/repos/rust-lang/rust/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/rust-lang/rust/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/rust-lang/rust/git/refs{/sha}","trees_url":"https://api.github.com/repos/rust-lang/rust/git/trees{/sha}","statuses_url":"https://api.github.com/repos/rust-lang/rust/statuses/{sha}","languages_url":"https://api.github.com/repos/rust-lang/rust/languages","stargazers_url":"https://api.github.com/repos/rust-lang/rust/stargazers","contributors_url":"https://api.github.com/repos/rust-lang/rust/contributors","subscribers_url":"https://api.github.com/repos/rust-lang/rust/subscribers","subscription_url":"https://api.github.com/repos/rust-lang/rust/subscription","commits_url":"https://api.github.com/repos/rust-lang/rust/commits{/sha}","git_commits_url":"https://api.github.com/repos/rust-lang/rust/git/commits{/sha}","comments_url":"https://api.github.com/repos/rust-lang/rust/comments{/number}","issue_comment_url":"https://api.github.com/repos/rust-lang/rust/issues/comments{/number}","contents_url":"https://api.github.com/repos/rust-lang/rust/contents/{+path}","compare_url":"https://api.github.com/repos/rust-lang/rust/compare/{base}...{head}","merges_url":"https://api.github.com/repos/rust-lang/rust/merges","archive_url":"https://api.github.com/repos/rust-lang/rust/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/rust-lang/rust/downloads","issues_url":"https://api.github.com/repos/rust-lang/rust/issues{/number}","pulls_url":"https://api.github.com/repos/rust-lang/rust/pulls{/number}","milestones_url":"https://api.github.com/repos/rust-lang/rust/milestones{/number}","notifications_url":"https://api.github.com/repos/rust-lang/rust/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/rust-lang/rust/labels{/name}","releases_url":"https://api.github.com/repos/rust-lang/rust/releases{/id}","deployments_url":"https://api.github.com/repos/rust-lang/rust/deployments","created_at":"2010-06-16T20:39:03Z","updated_at":"2018-03-18T07:41:57Z","pushed_at":"2018-03-18T08:44:47Z","git_url":"git://github.com/rust-lang/rust.git","ssh_url":"git@github.com:rust-lang/rust.git","clone_url":"https://github.com/rust-lang/rust.git","svn_url":"https://github.com/rust-lang/rust","homepage":"https://www.rust-lang.org","size":351743,"stargazers_count":27089,"watchers_count":27089,"language":"Rust","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":4772,"mirror_url":null,"archived":false,"open_issues_count":3523,"license":{"key":"other","name":"Other","spdx_id":null,"url":null},"forks":4772,"open_issues":3523,"watchers":27089,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/48639"},"html":{"href":"https://github.com/rust-lang/rust/pull/48639"},"issue":{"href":"https://api.github.com/repos/rust-lang/rust/issues/48639"},"comments":{"href":"https://api.github.com/repos/rust-lang/rust/issues/48639/comments"},"review_comments":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/48639/comments"},"review_comment":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/48639/commits"},"statuses":{"href":"https://api.github.com/repos/rust-lang/rust/statuses/8aee82c8c7637885d53f60feae157098c2700d50"}},"author_association":"CONTRIBUTOR"}}
{"actor":{"display_login":"SimonSapin"}}