about summary refs log tree commit diff
path: root/compiler/rustc_data_structures
AgeCommit message (Collapse)AuthorLines
2021-12-06Annotate comments onto the LT algorithmMark Rousskov-2/+102
2021-12-06Avoid using Option where values are always SomeMark Rousskov-9/+13
2021-12-06Create newtype around the pre order indexMark Rousskov-32/+41
2021-12-06Use variables rather than lengths directlyMark Rousskov-10/+13
2021-12-06Optimize: reuse the real-to-preorder mapping as the visited setMark Rousskov-4/+2
2021-12-06Remove separate RPO traversalMark Rousskov-17/+7
This integrates the preorder and postorder traversals into one.
2021-12-06Use preorder indices for data structuresMark Rousskov-53/+38
This largely avoids remapping from and to the 'real' indices, with the exception of predecessor lookup and the final merge back, and is conceptually better.
2021-12-06Avoid inserting into buckets if not necessaryMark Rousskov-1/+7
2021-12-06Optimization: process buckets only onceMark Rousskov-7/+8
2021-12-06Optimization: Merge parent and ancestor arraysMark Rousskov-10/+21
As the paper indicates, the unprocessed vertices in the DFS tree and processed vertices are disjoint, and we can use them in the same space, tracking only the index of the split.
2021-12-06Implement the simple Lengauer-Tarjan algorithmMark Rousskov-39/+116
This replaces the previous implementation with the simple variant of Lengauer-Tarjan, which performs better in the general case. Performance on the keccak benchmark is about equivalent between the two, but we don't see regressions (and indeed see improvements) on other benchmarks, even on a partially optimized implementation. The implementation here follows that of the pseudocode in "Linear-Time Algorithms for Dominators and Related Problems" thesis by Loukas Georgiadis. The next few commits will optimize the implementation as suggested in the thesis. Several related works are cited in the comments within the implementation, as well. Implement the simple Lengauer-Tarjan algorithm This replaces the previous implementation (from #34169), which has not been optimized since, with the simple variant of Lengauer-Tarjan which performs better in the general case. A previous attempt -- not kept in commit history -- attempted a replacement with a bitset-based implementation, but this led to regressions on perf.rust-lang.org benchmarks and equivalent wins for the keccak benchmark, so was rejected. The implementation here follows that of the pseudocode in "Linear-Time Algorithms for Dominators and Related Problems" thesis by Loukas Georgiadis. The next few commits will optimize the implementation as suggested in the thesis. Several related works are cited in the comments within the implementation, as well. On the keccak benchmark, we were previously spending 15% of our cycles computing the NCA / intersect function; this function is quite expensive, especially on modern CPUs, as it chases pointers on every iteration in a tight loop. With this commit, we spend ~0.05% of our time in dominator computation.
2021-12-05Stop enabling `in_band_lifetimes` in rustc_data_structuresScott McMurray-15/+13
There's a conversation in the tracking issue about possibly unaccepting `in_band_lifetimes`, but it's used heavily in the compiler, and thus there'd need to be a bunch of PRs like this if that were to happen. So here's one to see how much of an impact it has. (Oh, and I removed `nll` while I was here too, since it didn't seem needed. Let me know if I should put that back.)
2021-12-03Rollup merge of #88906 - Kixunil:box-maybe-uninit-write, r=dtolnayMatthias Krüger-4/+2
Implement write() method for Box<MaybeUninit<T>> This adds method similar to `MaybeUninit::write` main difference being it returns owned `Box`. This can be used to elide copy from stack safely, however it's not currently tested that the optimization actually occurs. Analogous methods are not provided for `Rc` and `Arc` as those need to handle the possibility of sharing. Some version of them may be added in the future. This was discussed in #63291 which this change extends.
2021-12-02Implement write() method for Box<MaybeUninit<T>>Martin Habovstiak-4/+2
This adds method similar to `MaybeUninit::write` main difference being it returns owned `Box`. This can be used to elide copy from stack safely, however it's not currently tested that the optimization actually occurs. Analogous methods are not provided for `Rc` and `Arc` as those need to handle the possibility of sharing. Some version of them may be added in the future. This was discussed in #63291 which this change extends.
2021-12-02Remove no-longer used `IdFunctor::map_id`Alan Egerton-9/+0
2021-11-27Use intrinsic pointer methodsAlan Egerton-7/+5
2021-11-27Delegate from `map_id` to `try_map_id`Alan Egerton-57/+7
2021-11-27Avoid UB when short-circuiting try_map_id for VecAlan Egerton-4/+11
2021-11-26Make `TypeFoldable` implementors short-circuit on errorLeSeulArtichaut-1/+69
Co-authored-by: Alan Egerton <eggyal@gmail.com>
2021-11-11Add `#[inline]`s to `SortedIndexMultiMap`Yuki Okushi-0/+10
2021-11-07more clippy fixesMatthias Krüger-1/+1
2021-10-29Auto merge of #90380 - Mark-Simulacrum:revert-89558-query-stable-lint, r=lcnrbors-1/+0
Revert "Add rustc lint, warning when iterating over hashmaps" Fixes perf regressions introduced in https://github.com/rust-lang/rust/pull/90235 by temporarily reverting the relevant PR.
2021-10-28Revert "Add rustc lint, warning when iterating over hashmaps"Mark Rousskov-1/+0
2021-10-28Auto merge of #90145 - cjgillot:sorted-map, r=michaelwoeristerbors-5/+22
Use SortedMap in HIR. Closes https://github.com/rust-lang/rust/issues/89788 r? `@ghost`
2021-10-25Auto merge of #90042 - pietroalbini:1.56-master, r=Mark-Simulacrumbors-1/+0
Bump bootstrap compiler to 1.57 Fixes https://github.com/rust-lang/rust/issues/90152 r? `@Mark-Simulacrum`
2021-10-25Use SmallVec in Hash map stable hashingJakub Beránek-1/+2
2021-10-24Rollup merge of #89558 - lcnr:query-stable-lint, r=estebankMatthias Krüger-0/+1
Add rustc lint, warning when iterating over hashmaps r? rust-lang/wg-incr-comp
2021-10-23update cfg(bootstrap)Pietro Albini-1/+0
2021-10-23Specialize HashStable for [u8] slicesMark Rousskov-0/+7
Particularly for ctfe-stress-4, the hashing of byte slices as part of the MIR Allocation is quite hot. Previously, we were falling back on byte-by-byte copying of the slice into the SipHash buffer (64 bytes long) before hashing a 64 byte chunk, and then doing that again and again. This should hopefully be an improvement for that code.
2021-10-21Use SortedMap in HIR.Camille GILLOT-5/+22
2021-10-15allow `potential_query_instability` everywherelcnr-0/+1
2021-10-10Remove for loop rangeClemens Wasser-2/+2
2021-10-10Apply clippy suggestionsClemens Wasser-41/+28
2021-10-07Update to measureme v10Ryan Levick-1/+1
2021-10-07Add support for artifact size profilingRyan Levick-4/+41
2021-10-04Rollup merge of #87993 - kornelski:try_reserve_stable, r=joshtriplettJubilee-2/+2
Stabilize try_reserve Stabilization PR for the [`try_reserve` feature](https://github.com/rust-lang/rust/issues/48043#issuecomment-898040475).
2021-10-04Rollup merge of #89508 - jhpratt:stabilize-const_panic, r=joshtriplettJubilee-1/+1
Stabilize `const_panic` Closes #51999 FCP completed in #89006 ```@rustbot``` label +A-const-eval +A-const-fn +T-lang cc ```@oli-obk``` for review (not `r?`'ing as not on lang team)
2021-10-04Stabilize try_reserveKornel-2/+2
2021-10-04Stabilize `const_panic`Jacob Pratt-1/+1
2021-10-02Remove various unused feature gatesbjorn3-1/+0
2021-09-28More tracing instrumentationOli Scherer-14/+6
2021-09-25Rollup merge of #89216 - r00ster91:bigo, r=dtolnayManish Goregaokar-2/+2
Consistent big O notation This makes the big O time complexity notation in places with markdown support more consistent. Inspired by #89210
2021-09-25arrr caught ya callerEllen-4/+5
awd
2021-09-24consistent big O notationr00ster91-2/+2
2021-09-21Auto merge of #89158 - the8472:rollup-3e4ijth, r=the8472bors-1/+0
Rollup of 12 pull requests Successful merges: - #88795 (Print a note if a character literal contains a variation selector) - #89015 (core::ascii::escape_default: reduce struct size) - #89078 (Cleanup: Remove needless reference in ParentHirIterator) - #89086 (Stabilize `Iterator::map_while`) - #89096 ([bootstrap] Improve the error message when `ninja` is not found to link to installation instructions) - #89113 (dont `.ensure()` the `thir_abstract_const` query call in `mir_build`) - #89114 (Fixes a technicality regarding the size of C's `char` type) - #89115 (:arrow_up: rust-analyzer) - #89126 (Fix ICE when `indirect_structural_match` is allowed) - #89141 (Impl `Error` for `FromSecsError` without foreign type) - #89142 (Fix match for placeholder region) - #89147 (add case for checking const refs in check_const_value_eq) Failed merges: r? `@ghost` `@rustbot` modify labels: rollup
2021-09-21Rollup merge of #89086 - WaffleLapkin:stabilize_iter_map_while, r=kennytmthe8472-1/+0
Stabilize `Iterator::map_while` Per the FCP: https://github.com/rust-lang/rust/issues/68537#issuecomment-922385035 This PR stabilizes `Iterator::map_while` and `iter::MapWhile` in Rust 1.57.
2021-09-21Auto merge of #89103 - Mark-Simulacrum:migrate-2021, r=estebankbors-1/+1
Migrate in-tree crates to 2021 This replaces #89075 (cherry picking some of the commits from there), and closes #88637 and fixes #89074. It excludes a migration of the library crates for now (see tidy diff) because we have some pending bugs around macro spans to fix there. I instrumented bootstrap during the migration to make sure all crates moved from 2018 to 2021 had the compatibility warnings applied first. Originally, the intent was to support cargo fix --edition within bootstrap, but this proved fairly difficult to pull off. We'd need to architect the check functionality to support running cargo check and cargo fix within the same x.py invocation, and only resetting sysroots on check. Further, it was found that cargo fix doesn't behave too well with "not quite workspaces", such as Clippy which has several crates. Bootstrap runs with --manifest-path ... for all the tools, and this makes cargo fix only attempt migration for that crate. We can't use e.g. --workspace due to needing to maintain sysroots for different phases of compilation appropriately. It is recommended to skip the mass migration of Cargo.toml's to 2021 for review purposes; you can also use `git diff d6cd2c6c877110748296760aefddc21a0ea1d316 -I'^edition = .20...$'` to ignore the edition = 2018/21 lines in the diff.
2021-09-20Migrate to 2021Mark Rousskov-1/+1
2021-09-18Use <[T; N]>::map in Sharded instead of SmallVec and unsafe codebjorn3-19/+1
This results in a lot less assembly
2021-09-17Stabilize `Iterator::map_while`Maybe Waffle-1/+0
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-27 14:08:39 +0000