https://github.com/rust-lang/rust http://git.dreamy.place/mirrors/rust/atom?h=1.26.2 2018-04-22T00:04:01+00:00 2018-04-22T00:04:01+00:00 Michael Lamparski diagonaldevice@gmail.com 2018-04-18T20:48:34+00:00 urn:sha1:bbfc486d112a9e601f6b1afeb7660c8ba015c849 and add one for non-mut slicing since I touched that method too 2018-04-22T00:03:58+00:00 Michael Lamparski diagonaldevice@gmail.com 2018-04-16T20:34:09+00:00 urn:sha1:7ef7f38d5ee330605ddbb977ac90a1a1a2744e70 2018-03-29T11:12:49+00:00 Simon Sapin simon.sapin@exyr.org 2018-03-19T08:01:17+00:00 urn:sha1:c3a63970dee2422e2fcc79d8b99303b4b046f444 The stable reexport `std::collections::Bound` is now deprecated. Another deprecated reexport could be added in `alloc`, but that crate is unstable. 2018-03-27T08:47:44+00:00 kennytm kennytm@gmail.com 2018-03-27T08:47:44+00:00 urn:sha1:42de36d4aa74f0be9856dbac0cacda97b865647c Add slice::sort_by_cached_key as a memoised sort_by_key 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. To 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. Where there are `n` elements and the key function is `O(m)`: - `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)`. - `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`.) `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. Benchmarks (for a vector of 100 `i32`s): ``` # Lexicographic: `|x| x.to_string()` test bench_sort_by_key ... bench: 112,638 ns/iter (+/- 19,563) test bench_sort_by_cached_key ... bench: 15,038 ns/iter (+/- 4,814) # Identity: `|x| *x` test bench_sort_by_key ... bench: 1,346 ns/iter (+/- 238) test bench_sort_by_cached_key ... bench: 1,839 ns/iter (+/- 765) # Power: `|x| x.pow(31)` test bench_sort_by_key ... bench: 3,624 ns/iter (+/- 738) test bench_sort_by_cached_key ... bench: 1,997 ns/iter (+/- 311) # Abs: `|x| x.abs()` test bench_sort_by_key ... bench: 1,546 ns/iter (+/- 174) test bench_sort_by_cached_key ... bench: 1,668 ns/iter (+/- 790) ``` (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.) I'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. Resolves #34447. 2018-03-19T00:11:47+00:00 varkor github@varkor.com 2018-03-19T00:11:47+00:00 urn:sha1:eca1e18cd7021f01757640c0c5ef63717870686c 2018-03-17T18:24:49+00:00 Niv Kaminer nivkner@zoho.com 2018-03-16T23:09:36+00:00 urn:sha1:3753e1a55a2ed118121779e05f77164da3269a86 2018-03-17T17:25:23+00:00 varkor github@varkor.com 2018-03-16T16:35:27+00:00 urn:sha1:b430cba343743783cee517bf93c7f255827cccc5 2018-03-16T14:39:53+00:00 varkor github@varkor.com 2018-03-16T14:37:17+00:00 urn:sha1:f41a26f2040dfa752825a7d1fdfbd5a8ae3310cf 2018-03-16T13:57:07+00:00 varkor github@varkor.com 2018-03-01T13:39:52+00:00 urn:sha1:9fbee359d7eb3a621604bc2067a375f6d4b757e5 2018-03-16T00:09:14+00:00 bors bors@rust-lang.org 2018-03-16T00:09:14+00:00 urn:sha1:36b66873187e37a9d79adad89563088a9cb86028 Rollup of 17 pull requests - Successful merges: #48706, #48875, #48892, #48922, #48957, #48959, #48961, #48965, #49007, #49024, #49042, #49050, #48853, #48990, #49037, #49049, #48972 - Failed merges: