about summary refs log tree commit diff
path: root/src/librustc_data_structures
AgeCommit message (Collapse)AuthorLines
2018-08-15Rollup merge of #53271 - llogiq:simplify-maybe-map, r=joshtriplettGuillaume Gomez-6/+1
use ? to simplify `TransitiveRelation.maybe_map` I think this looks much clearer than the original.
2018-08-13use ? to simplify `TransitiveRelation.maybe_map`Andre Bogus-6/+1
2018-08-13Move SmallVec and ThinVec out of libsyntaxljedrz-0/+125
2018-08-13Auto merge of #53161 - michaelwoerister:cstrings, r=wesleywiserbors-0/+175
Avoid many allocations for CStrings during codegen. Giving in to my irrational fear of dynamic allocations. Let's see what perf says to this.
2018-08-12Rollup merge of #53230 - memoryruins:nll_bootstrap_4, r=nikomatsakisGuillaume Gomez-1/+2
[nll] enable feature(nll) on various crates for bootstrap: part 4 #53172 r? @nikomatsakis
2018-08-12Rollup merge of #53223 - ljedrz:cleanup_data_structures, r=oli-obkGuillaume Gomez-39/+38
A few cleanups for rustc_data_structures - remove a redundant `clone()` - make some calls to `.iter()` implicit - collapse/simplify a few operations - remove some explicit `return`s - make `SnapshotMap::{commit, rollback_to}` take references - remove unnecessary struct field names - change `transmute()`s in `IdxSet::{from_slice, from_slice_mut}` to casts - remove some unnecessary lifetime annotations - split 2 long literals
2018-08-12Rollup merge of #53019 - ljedrz:bad_collects, r=estebankGuillaume Gomez-1/+6
Don't collect() when size_hint is useless This adjusts PRs #52738 and #52697 by falling back to calculating capacity and extending or pushing in a loop where `collect()` can't be trusted to calculate the right capacity. It is a performance win.
2018-08-10Introduce SmallCStr and use it where applicable.Michael Woerister-0/+132
2018-08-10Introduce const_cstr!() macro and use it where applicable.Michael Woerister-0/+43
2018-08-09[nll] librustc_data_structures: remove unused mut annotation in testmemoryruins-1/+1
2018-08-09A few cleanups for rustc_data_structuresljedrz-24/+27
2018-08-09Change transmute()s in IdxSet::{from_slice, from_slice_mut} to castsljedrz-6/+2
2018-08-09Make SnapshotMap::{commit, rollback_to} take referencesljedrz-9/+9
2018-08-09Move Fingerprint to data structuresMark Rousskov-1/+113
2018-08-09Reuse Hash impls for session data structuresMark Rousskov-4/+7
2018-08-09Move SVH structure to data structuresMark Rousskov-0/+86
2018-08-09[nll] librustc_data_structures: enable feature(nll) for bootstrapmemoryruins-0/+1
2018-08-06Auto merge of #52644 - varkor:lib-feature-gate-2, r=withoutboatsbors-1/+0
Add errors for unknown, stable and duplicate feature attributes - Adds an error for unknown (lang and lib) features. - Extends the lint for unnecessary feature attributes for stable features to libs features (this already exists for lang features). - Adds an error for duplicate (lang and lib) features. ```rust #![feature(fake_feature)] //~ ERROR unknown feature `fake_feature` #![feature(i128_type)] //~ WARNING the feature `i128_type` has been stable since 1.26.0 #![feature(non_exhaustive)] #![feature(non_exhaustive)] //~ ERROR duplicate `non_exhaustive` feature attribute ``` Fixes #52053, fixes #53032 and address some of the problems noted in #44232 (though not unused features). There are a few outstanding problems, that I haven't narrowed down yet: - [x] Stability attributes on macros do not seem to be taken into account. - [x] Stability attributes behind `cfg` attributes are not taken into account. - [x] There are failing incremental tests.
2018-08-05Remove unnecessary feature attributes that sneaked invarkor-1/+0
2018-08-03Don't collect() when size_hint is uselessljedrz-1/+6
2018-08-02make TinyList more readable and optimize remove(_)Andre Bogus-32/+49
also add benchmarks Before: ``` test tiny_list::test::bench_insert_empty ... bench: 1 ns/iter (+/- 0) test tiny_list::test::bench_insert_one ... bench: 16 ns/iter (+/- 0) test tiny_list::test::bench_remove_empty ... bench: 2 ns/iter (+/- 0) test tiny_list::test::bench_remove_one ... bench: 6 ns/iter (+/- 0) test tiny_list::test::bench_remove_unknown ... bench: 4 ns/iter (+/- 0) ``` After: ``` test tiny_list::test::bench_insert_empty ... bench: 1 ns/iter (+/- 0) test tiny_list::test::bench_insert_one ... bench: 16 ns/iter (+/- 0) test tiny_list::test::bench_remove_empty ... bench: 0 ns/iter (+/- 0) test tiny_list::test::bench_remove_one ... bench: 3 ns/iter (+/- 0) test tiny_list::test::bench_remove_unknown ... bench: 2 ns/iter (+/- 0) ```
2018-08-01Rollup merge of #52942 - llogiq:smallvec-opt, r=Mark-SimulacrumPietro Albini-12/+5
Another SmallVec.extend optimization This improves SmallVec.extend even more over #52859 while making the code easier to read. Before ``` test small_vec::tests::fill_small_vec_1_10_with_cap ... bench: 31 ns/iter (+/- 5) test small_vec::tests::fill_small_vec_1_10_wo_cap ... bench: 70 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_1_50_with_cap ... bench: 36 ns/iter (+/- 3) test small_vec::tests::fill_small_vec_1_50_wo_cap ... bench: 256 ns/iter (+/- 17) test small_vec::tests::fill_small_vec_32_10_with_cap ... bench: 31 ns/iter (+/- 5) test small_vec::tests::fill_small_vec_32_10_wo_cap ... bench: 26 ns/iter (+/- 1) test small_vec::tests::fill_small_vec_32_50_with_cap ... bench: 49 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_32_50_wo_cap ... bench: 219 ns/iter (+/- 11) test small_vec::tests::fill_small_vec_8_10_with_cap ... bench: 32 ns/iter (+/- 2) test small_vec::tests::fill_small_vec_8_10_wo_cap ... bench: 61 ns/iter (+/- 12) test small_vec::tests::fill_small_vec_8_50_with_cap ... bench: 37 ns/iter (+/- 3) test small_vec::tests::fill_small_vec_8_50_wo_cap ... bench: 210 ns/iter (+/- 10) ``` After: ``` test small_vec::tests::fill_small_vec_1_10_wo_cap ... bench: 31 ns/iter (+/- 3) test small_vec::tests::fill_small_vec_1_50_with_cap ... bench: 39 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_1_50_wo_cap ... bench: 35 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_32_10_with_cap ... bench: 37 ns/iter (+/- 3) test small_vec::tests::fill_small_vec_32_10_wo_cap ... bench: 32 ns/iter (+/- 2) test small_vec::tests::fill_small_vec_32_50_with_cap ... bench: 52 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_32_50_wo_cap ... bench: 46 ns/iter (+/- 0) test small_vec::tests::fill_small_vec_8_10_with_cap ... bench: 35 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_8_10_wo_cap ... bench: 31 ns/iter (+/- 0) test small_vec::tests::fill_small_vec_8_50_with_cap ... bench: 40 ns/iter (+/- 15) test small_vec::tests::fill_small_vec_8_50_wo_cap ... bench: 36 ns/iter (+/- 2) ```
2018-08-01Split out growth functionality into BitVector typeMark Rousskov-59/+77
2018-08-01Another SmallVec.extend optimizationAndre Bogus-12/+5
This improves SmallVec.extend even more over #52859 Before (as of #52859): ``` test small_vec::tests::fill_small_vec_1_10_with_cap ... bench: 31 ns/iter (+/- 5) test small_vec::tests::fill_small_vec_1_10_wo_cap ... bench: 70 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_1_50_with_cap ... bench: 36 ns/iter (+/- 3) test small_vec::tests::fill_small_vec_1_50_wo_cap ... bench: 256 ns/iter (+/- 17) test small_vec::tests::fill_small_vec_32_10_with_cap ... bench: 31 ns/iter (+/- 5) test small_vec::tests::fill_small_vec_32_10_wo_cap ... bench: 26 ns/iter (+/- 1) test small_vec::tests::fill_small_vec_32_50_with_cap ... bench: 49 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_32_50_wo_cap ... bench: 219 ns/iter (+/- 11) test small_vec::tests::fill_small_vec_8_10_with_cap ... bench: 32 ns/iter (+/- 2) test small_vec::tests::fill_small_vec_8_10_wo_cap ... bench: 61 ns/iter (+/- 12) test small_vec::tests::fill_small_vec_8_50_with_cap ... bench: 37 ns/iter (+/- 3) test small_vec::tests::fill_small_vec_8_50_wo_cap ... bench: 210 ns/iter (+/- 10) ``` After: ``` test small_vec::tests::fill_small_vec_1_10_wo_cap ... bench: 31 ns/iter (+/- 3) test small_vec::tests::fill_small_vec_1_50_with_cap ... bench: 39 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_1_50_wo_cap ... bench: 35 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_32_10_with_cap ... bench: 37 ns/iter (+/- 3) test small_vec::tests::fill_small_vec_32_10_wo_cap ... bench: 32 ns/iter (+/- 2) test small_vec::tests::fill_small_vec_32_50_with_cap ... bench: 52 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_32_50_wo_cap ... bench: 46 ns/iter (+/- 0) test small_vec::tests::fill_small_vec_8_10_with_cap ... bench: 35 ns/iter (+/- 4) test small_vec::tests::fill_small_vec_8_10_wo_cap ... bench: 31 ns/iter (+/- 0) test small_vec::tests::fill_small_vec_8_50_with_cap ... bench: 40 ns/iter (+/- 15) test small_vec::tests::fill_small_vec_8_50_wo_cap ... bench: 36 ns/iter (+/- 2) ```
2018-08-01Rollup merge of #52859 - ljedrz:smallvec_true_extend, r=Mark-SimulacrumPietro Albini-4/+128
Use Vec::extend in SmallVec::extend when applicable As calculated in #52738, `Vec::extend` is much faster than `push`ing to it in a loop. We can take advantage of this method in `SmallVec` too - at least in cases when its underlying object is an `AccumulateVec::Heap`. ~~This approach also accidentally improves the `push` loop of the `AccumulateVec::Array` variant, because it doesn't utilize `SmallVec::push` which performs `self.reserve(1)` with every iteration; this is unnecessary, because we're already reserving the whole space we will be needing by performing `self.reserve(iter.size_hint().0)` at the beginning.~~
2018-07-31Benchmarks for SmallVecljedrz-0/+116
2018-07-30Use Vec::extend in SmallVec::extend when applicableljedrz-4/+12
2018-07-30Auto merge of #52697 - ljedrz:misc_data_structures, r=Mark-Simulacrumbors-11/+5
Simplify a few functions in rustc_data_structures - drop `try!()` where it's superfluous - change `try!()` to `?` - squash a `push` with `push_str` - refactor a push loop into an iterator
2018-07-29Remove unused `mut`sMatthew Jasper-1/+1
2018-07-27Auto merge of #52336 - ishitatsuyuki:dyn-rollup, r=Mark-Simulacrumbors-2/+0
Rollup of bare_trait_objects PRs All deny attributes were moved into bootstrap so they can be disabled with a line of config. Warnings for external tools are allowed and it's up to the tool's maintainer to keep it warnings free. r? @Mark-Simulacrum cc @ljedrz @kennytm
2018-07-26fix `sparse_matrix_iter` unit testNiko Matsakis-1/+1
2018-07-26add type parameters to `BitMatrix` and `SparseBitMatrix` unit testsNiko Matsakis-3/+3
2018-07-26convert tests of `BitVector` to use `BitVector<usize>`Niko Matsakis-5/+5
2018-07-25SparseBitMatrix: add `insert_all` and `add_all` methodsNiko Matsakis-0/+13
2018-07-25SparseBitMatrix: add `ensure_row` helper fnNiko Matsakis-9/+9
2018-07-25split into two matricesNiko Matsakis-0/+61
2018-07-25parameterize `BitVector` and `BitMatrix` by their index typesNiko Matsakis-46/+63
2018-07-25Deny bare_trait_objects globallyTatsuyuki Ishi-2/+0
2018-07-25implement `Step` for `Idx` typesNiko Matsakis-0/+29
This way, we can iterate over a `Range<T>` where `T: Idx`
2018-07-24Simplify a few functions in rustc_data_structuresljedrz-11/+5
2018-07-22Auto merge of #52250 - nnethercote:no-SparseBitMatrix, r=nikomatsakisbors-208/+28
Speed up `SparseBitMatrix` use in `RegionValues`. In practice, these matrices range from 10% to 90%+ full once they are filled in, so the dense representation is better. This reduces the runtime of Check Nll builds of `inflate` by 32%, and several other benchmarks by 1--5%. It also increases max-rss of `clap-rs` by 30% and a couple of others by up to 5%, while decreasing max-rss of `coercions` by 14%. I think the speed-ups justify the max-rss increases. r? @nikomatsakis
2018-07-20data_structures: Add a reference wrapper for pointer-indexed maps/setsVadim Petrochenkov-10/+56
Use `ptr::eq` for comparing pointers
2018-07-20Speed up `SparseBitMatrix`.Nicholas Nethercote-208/+28
Using a `BTreeMap` to represent rows in the bit matrix is really slow. This patch changes things so that each row is represented by a `BitVector`. This is a less sparse representation, but a much faster one. As a result, `SparseBitSet` and `SparseChunk` can be removed. Other minor changes in this patch. - It renames `BitVector::insert()` as `merge()`, which matches the terminology in the other classes in bitvec.rs. - It removes `SparseBitMatrix::is_subset()`, which is unused. - It reinstates `RegionValueElements::num_elements()`, which #52190 had removed. - It removes a low-value `debug!` call in `SparseBitMatrix::add()`.
2018-07-18Auto merge of #52342 - nnethercote:CanonicalVar, r=nikomatsakisbors-0/+11
Avoid most allocations in `Canonicalizer`. Extra allocations are a significant cost of NLL, and the most common ones come from within `Canonicalizer`. In particular, `canonical_var()` contains this code: indices .entry(kind) .or_insert_with(|| { let cvar1 = variables.push(info); let cvar2 = var_values.push(kind); assert_eq!(cvar1, cvar2); cvar1 }) .clone() `variables` and `var_values` are `Vec`s. `indices` is a `HashMap` used to track what elements have been inserted into `var_values`. If `kind` hasn't been seen before, `indices`, `variables` and `var_values` all get a new element. (The number of elements in each container is always the same.) This results in lots of allocations. In practice, most of the time these containers only end up holding a few elements. This PR changes them to avoid heap allocations in the common case, by changing the `Vec`s to `SmallVec`s and only using `indices` once enough elements are present. (When the number of elements is small, a direct linear search of `var_values` is as good or better than a hashmap lookup.) The changes to `variables` are straightforward and contained within `Canonicalizer`. The changes to `indices` are more complex but also contained within `Canonicalizer`. The changes to `var_values` are more intrusive because they require defining a new type `SmallCanonicalVarValues` -- which is to `CanonicalVarValues` as `SmallVec` is to `Vec -- and passing stack-allocated values of that type in from outside. All this speeds up a number of NLL "check" builds, the best by 2%. r? @nikomatsakis
2018-07-17Auto merge of #52433 - kennytm:rollup, r=kennytmbors-3/+8
Rollup of 9 pull requests Successful merges: - #52286 (Deny bare trait objects in src/librustc_errors) - #52306 (Reduce the number of clone()s needed in obligation_forest) - #52338 (update miri) - #52385 (Pass edition flags to compiler from rustdoc as expected) - #52392 (AsRef doc wording tweaks) - #52430 (update nomicon) - #52434 (Enable incremental independent of stage) - #52435 (Calculate the exact capacity for 2 HashMaps) - #52446 (Block beta if clippy breaks.) r? @ghost
2018-07-17Auto merge of #52190 - davidtwco:issue-52028, r=nikomatsakisbors-9/+66
html5ever in the rustc-perf repository is memory-intensive Part of #52028. Rebased atop of #51987. r? @nikomatsakis
2018-07-17Rollup merge of #52306 - ljedrz:obligation_forest_clone, r=varkorkennytm-3/+8
Reduce the number of clone()s needed in obligation_forest Some can be avoided by using `remove_entry` instead of `remove`.
2018-07-17Auto merge of #52335 - nnethercote:BitSlice-fixes, r=nikomatsakisbors-17/+11
`BitSlice` fixes `propagate_bits_into_entry_set_for` and `BitSlice::bitwise` are hot for some benchmarks under NLL. I tried and failed to speed them up. (Increasing the size of `bit_slice::Word` from `usize` to `u128` caused a slowdown, even though decreasing the size of `bitvec::Word` from `u128` to `u64` also caused a slowdown. Weird.) Anyway, along the way I fixed up several problems in and around the `BitSlice` code. r? @nikomatsakis
2018-07-16Generate region values directly to reduce memory usage.David Wood-9/+66
Also modify `SparseBitMatrix` so that it does not require knowing the dimensions in advance, but instead grows on demand.
2018-07-17Avoid most allocations in `Canonicalizer`.Nicholas Nethercote-0/+11
Extra allocations are a significant cost of NLL, and the most common ones come from within `Canonicalizer`. In particular, `canonical_var()` contains this code: indices .entry(kind) .or_insert_with(|| { let cvar1 = variables.push(info); let cvar2 = var_values.push(kind); assert_eq!(cvar1, cvar2); cvar1 }) .clone() `variables` and `var_values` are `Vec`s. `indices` is a `HashMap` used to track what elements have been inserted into `var_values`. If `kind` hasn't been seen before, `indices`, `variables` and `var_values` all get a new element. (The number of elements in each container is always the same.) This results in lots of allocations. In practice, most of the time these containers only end up holding a few elements. This PR changes them to avoid heap allocations in the common case, by changing the `Vec`s to `SmallVec`s and only using `indices` once enough elements are present. (When the number of elements is small, a direct linear search of `var_values` is as good or better than a hashmap lookup.) The changes to `variables` are straightforward and contained within `Canonicalizer`. The changes to `indices` are more complex but also contained within `Canonicalizer`. The changes to `var_values` are more intrusive because they require defining a new type `SmallCanonicalVarValues` -- which is to `CanonicalVarValues` as `SmallVec` is to `Vec -- and passing stack-allocated values of that type in from outside. All this speeds up a number of NLL "check" builds, the best by 2%.
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-26 09:21:59 +0000