about summary refs log tree commit diff
path: root/compiler/rustc_data_structures/src
AgeCommit message (Collapse)AuthorLines
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-07Add support for artifact size profilingRyan Levick-3/+40
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-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-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
2021-09-12Rollup merge of #88711 - Mark-Simulacrum:fix-dfs-bug, r=jackh726Manish Goregaokar-3/+69
Rework DepthFirstSearch API This expands the API to be more flexible, allowing for more visitation patterns on graphs. This will be useful to avoid extra datasets (and allocations) in cases where the expanded DFS API is sufficient. This also fixes a bug with the previous DFS constructor, which left the start node not marked as visited (even though it was immediately returned). Commit written by ```@nikomatsakis``` originally, cherry picked from several commits in work on never type stabilization, but stands alone.
2021-09-10rustc: Remove local variable IDs from `Export`sVadim Petrochenkov-0/+7
Local variables can never be exported.
2021-09-08Bump stage0 compiler to 1.56Mark Rousskov-2/+1
2021-09-08Rework DepthFirstSearch APINiko Matsakis-3/+69
This expands the API to be more flexible, allowing for more visitation patterns on graphs. This will be useful to avoid extra datasets (and allocations) in cases where the expanded DFS API is sufficient. This also fixes a bug with the previous DFS constructor, which left the start node not marked as visited (even though it was immediately returned).
2021-09-06Rollup merge of #88659 - est31:update_smallvec_name, r=matthewjasperRyan Levick-1/+1
Remove SmallVector mention SmallVector is long gone, as it's been first replaced by OneVector in commit e5e6375352636360add297c1f5a1f37ce71506e9, which then has been removed entirely in favour of SmallVec in commit 130a32fa7259d348dc3a684b38e688da398c30bb.
2021-09-05Remove SmallVector mentionest31-1/+1
SmallVector is long gone, as it's been first replaced by OneVector in commit e5e6375352636360add297c1f5a1f37ce71506e9, which then has been removed entirely in favour of SmallVec in commit 130a32fa7259d348dc3a684b38e688da398c30bb.
2021-09-01Rollup merge of #88053 - bjorn3:fix_flock_fallback_impl, r=cjgillotMara Bos-0/+4
Fix the flock fallback implementation
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-01-16 21:30:13 +0000