html5ever in the rustc-perf repository is memory-intensive#52190
Merged
bors merged 1 commit intorust-lang:masterfrom Jul 17, 2018
Merged
html5ever in the rustc-perf repository is memory-intensive#52190bors merged 1 commit intorust-lang:masterfrom
bors merged 1 commit intorust-lang:masterfrom
Conversation
Member
Author
|
This doesn't currently pass tests - the error is related to the SCC stuff and I've not had a great deal of time to look into it. |
Contributor
|
The job Click to expand the log.I'm a bot! I can only do what humans tell me to, so if this was not helpful or you have suggestions for improvements, please ping or otherwise contact |
Contributor
|
The job Click to expand the log.I'm a bot! I can only do what humans tell me to, so if this was not helpful or you have suggestions for improvements, please ping or otherwise contact |
Contributor
|
The job Click to expand the log.I'm a bot! I can only do what humans tell me to, so if this was not helpful or you have suggestions for improvements, please ping or otherwise contact |
Collaborator
|
☔ The latest upstream changes (presumably #51987) made this pull request unmergeable. Please resolve the merge conflicts. |
Contributor
|
The job Click to expand the log.I'm a bot! I can only do what humans tell me to, so if this was not helpful or you have suggestions for improvements, please ping or otherwise contact |
nikomatsakis
requested changes
Jul 14, 2018
Contributor
nikomatsakis
left a comment
There was a problem hiding this comment.
First round of review, on the changes to Sparse etc
| pub fn add(&mut self, row: R, column: C) -> bool { | ||
| self.vector[row].insert(column) | ||
| if let None = self.vector.get(row) { | ||
| self.vector.push(SparseBitSet::new()); |
Contributor
There was a problem hiding this comment.
This doesn't seem right -- imagine that the vector starts out as empty, but we invoke add(2, 0) -- then we have to push two things. I think the method you want is either resize or -- perhaps mildly more efficient -- resize_with. If index where a plain vector, you would do something like this:
self.vector.resize_with(row + 1, || SparseBitSet::new())However, that won't work because vector is an IndexVec and it doesn't offer resize_with. You could use self.vector.raw.resize_with, but better would be to add a method to IndexVec:
impl<I, T> IndexVec<I, T> {
fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
let min_new_len = elem.as_usize() + 1;
self.raw.resize_with(min_new_len, fill_value);
}
}and then invoke self.vector.resize_to_elem(row, || SparseBitSet::new());.
| self.vector.push(SparseBitSet::new()); | ||
| } | ||
|
|
||
| if let Some(row) = self.vector.get_mut(row) { |
Contributor
There was a problem hiding this comment.
Now this can be self.vector[row].insert(column) as before
|
|
||
| /// Merge a row, `from`, into the `into` row. | ||
| pub fn merge_into(&mut self, into: R, from: &SparseBitSet<C>) -> bool { | ||
| match self.vector.get_mut(into) { |
Contributor
There was a problem hiding this comment.
This should again use the resize_to_elem helper;
self.vector.resize_to_elem(into, || SparseBitSet::new());
self.vector[row].merge_into(from);| } | ||
|
|
||
| /// Merge two sparse bit sets. | ||
| pub fn merge_into(&mut self, from: &SparseBitSet<I>) -> bool { |
Contributor
There was a problem hiding this comment.
I think should be called insert_from.
nikomatsakis
requested changes
Jul 14, 2018
| let p2 = location_table.mid_index(*location); | ||
| iter::once((r, p1)).chain(iter::once((r, p2))) | ||
| })); | ||
| for (r, _) in regioncx.liveness_constraints() { |
Contributor
There was a problem hiding this comment.
We could also generate these during typeck -- we generate other facts then iirc
| } | ||
|
|
||
| for constraint in self.constraint_graph.outgoing_edges(current_region) { | ||
| assert_eq!(self.constraints[constraint].sup, current_region); |
Contributor
There was a problem hiding this comment.
wait — why this diff?
| mod graphviz; | ||
| mod values; | ||
| use self::values::{RegionValueElements, RegionValues}; | ||
| crate use self::values::{RegionElement, RegionElementIndex, RegionValueElements, RegionValues}; |
Contributor
There was a problem hiding this comment.
In this code, I've been trying to stick to a style that avoids crate use and I'd prefer to keep doing so. In particular, I want to have things have just one home and that is where you import them from (unlike the rest of the compiler where I cannot tell, based on the filename where I find some code, what path I am supposed to use).
|
|
||
| for (region, location_set) in liveness_constraints.iter_enumerated() { | ||
| let scc = constraint_sccs.scc(region); | ||
| scc_values.merge_into(scc, location_set); |
| self.liveness_constraints.iter_enumerated() | ||
| } | ||
|
|
||
| /// Number of liveness constaints in region inference context. |
Contributor
There was a problem hiding this comment.
Typo: s/containts/constraints
Contributor
There was a problem hiding this comment.
I would usually call this num_liveness_constraints, but then again I've been trying to use fewer and fewer contractions...
| } | ||
|
|
||
| /// Returns all the elements contained in a given region's value. | ||
| crate fn elements_contained_in<'a>( |
Contributor
There was a problem hiding this comment.
I think should be called something like region_live_at or region_liveness_elements
| cx.constraints.liveness_set.push((live_region, location)); | ||
| if let Some(borrowck_context) = cx.borrowck_context { | ||
| let region_vid = borrowck_context.universal_regions.to_region_vid(live_region); | ||
| borrowck_context.constraints.liveness_constraints.add_element(region_vid, location); |
Contributor
There was a problem hiding this comment.
Here we can also do
if let Some(all_facts) = &mut borrowck_context.all_facts {
all_facts.region_live_at.push(...);
}and then -- I suspect -- we can remove that big awkward loop above.
| reported_errors: FxHashSet<(Ty<'tcx>, Span)>, | ||
| constraints: MirTypeckRegionConstraints<'tcx>, | ||
| borrowck_context: Option<BorrowCheckContext<'a, 'tcx>>, | ||
| borrowck_context: &'a mut Option<BorrowCheckContext<'a, 'tcx>>, |
Contributor
There was a problem hiding this comment.
Seems odd for this to be &mut Option<> and not Option<&mut>, but it doesn't really matter. If you did the latter, you would have to do:
if let Some(borrowck_context) = &mut self.borrowck_contextinstead of this
if let Some(borrowck_context) = self.borrowck_context| late_bound_region); | ||
| borrowck_context.constraints | ||
| .liveness_constraints | ||
| .add_element(region_vid, term_location); |
Contributor
There was a problem hiding this comment.
We wouldn't need to modify all-facts here necessarily -- iirc, polonius only cares about liveness in variables -- i.e., regions that exist across many points in the CFG.
Member
Author
|
Pushed a commit that addresses the comments above. This still ICEs in the SCC code and I've yet to find time to dig into why that is. |
Contributor
|
The job Click to expand the log.I'm a bot! I can only do what humans tell me to, so if this was not helpful or you have suggestions for improvements, please ping or otherwise contact |
Contributor
nikomatsakis
left a comment
There was a problem hiding this comment.
Seems good to me -- let me check the travis errors..
| /// Returns true if this changed the matrix, and false otherwise. | ||
| pub fn add(&mut self, row: R, column: C) -> bool { | ||
| self.vector.resize_to_elem(row, || SparseBitSet::new()); | ||
| if let None = self.vector.get(row) { |
Contributor
There was a problem hiding this comment.
I think this if let is dead-code now, right?
Member
Author
There was a problem hiding this comment.
Yes, must have forgot to clean that up. I'll remove this in my next commit.
| ); | ||
|
|
||
| if let Some(borrowck_context) = &mut self.borrowck_context { | ||
| if let Some(ref mut borrowck_context) = self.borrowck_context { |
Contributor
There was a problem hiding this comment.
These two are equivalent, no? I moderately prefer Some(foo) = &mut self.borrowck_context but it doesn't matter much.
Member
Author
There was a problem hiding this comment.
Ah, I misread your previous comment about Option<&mut T> rather than &mut Option<T> and made this change due to that. I can change it back if you'd prefer.
Contributor
There was a problem hiding this comment.
I'd prefer to change it back, yes.
Contributor
There was a problem hiding this comment.
ref mut is dead to me now :)
| .. | ||
| } = match &mut self.borrowck_context { | ||
| Some(borrowck_context) => borrowck_context, | ||
| } = match self.borrowck_context { |
Contributor
There was a problem hiding this comment.
likely, here I personally prefer the more modern style
nikomatsakis
approved these changes
Jul 16, 2018
Contributor
|
OK, I fixed the problems I see locally. I'm going to try for a try run so we can measure the impact. I'm quite curious. |
Contributor
|
@bors try |
Collaborator
bors
added a commit
that referenced
this pull request
Jul 16, 2018
WIP: html5ever in the rustc-perf repository is memory-intensive Part of #52028. Rebased atop of #51987. r? @nikomatsakis
Contributor
|
@rust-timer build c1ea2d1 |
Collaborator
|
Success: Queued c1ea2d1 with parent 3d5753f, comparison URL. |
Contributor
|
11% on instructions and 83.5% max-rss for |
Also modify `SparseBitMatrix` so that it does not require knowing the dimensions in advance, but instead grows on demand.
cf3f9b9 to
8b94d16
Compare
Contributor
|
@davidtwco I took the liberty of squashing the commits |
Contributor
|
@bors r+ p=1 Giving high priority because this high memory usage is a major NLL problem |
Collaborator
|
📋 Looks like this PR is still in progress, ignoring approval. Hint: Remove WIP from this PR's title when it is ready for review. |
Contributor
|
@bors r+ p=1 Giving high priority because this high memory usage is a major NLL problem |
Collaborator
|
📌 Commit 8b94d16 has been approved by |
Collaborator
|
⌛ Testing commit 8b94d16 with merge 3395384319ccc52765a13627ad41f72b40ae650b... |
Collaborator
|
💔 Test failed - status-travis |
Contributor
|
The job Click to expand the log.I'm a bot! I can only do what humans tell me to, so if this was not helpful or you have suggestions for improvements, please ping or otherwise contact |
1 similar comment
Contributor
|
The job Click to expand the log.I'm a bot! I can only do what humans tell me to, so if this was not helpful or you have suggestions for improvements, please ping or otherwise contact |
Member
|
@bors retry |
Member
|
@bors p=15 |
Collaborator
bors
added a commit
that referenced
this pull request
Jul 17, 2018
html5ever in the rustc-perf repository is memory-intensive Part of #52028. Rebased atop of #51987. r? @nikomatsakis
Collaborator
|
☀️ Test successful - status-appveyor, status-travis |
nnethercote
added a commit
to nnethercote/rust
that referenced
this pull request
Jul 20, 2018
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 rust-lang#52190 had removed. - It removes a low-value `debug!` call in `SparseBitMatrix::add()`.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
8 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Part of #52028. Rebased atop of #51987.
r? @nikomatsakis