[Masonry] dense-packing: include open end of tracks when finding eligible track opening [chromium/src : main]
Celeste Pan (Gerrit)
Celeste Pan added 12 comments![]( "Open in Gerrit")
Rebased + restructured our usage of `track_collection_openings_.` `running_positions_` has been removed. There may be minor changes after the rebase that cause breaks, but I was hoping to get feedback on the actually changed parts.
[Masonry] dense-packing: include open tracks when finding track openingCeleste Pannit: empty
Personally I don't love the use of "empty" because the track isn't necessarily fully empty, it's more like the track has an open end which would align with the track opening we're building.
If we have a track opening which spans 30px to 50px, the "open track" we build into maybe has one item which goes until 25px, but we can still lay out a multi-span item into the open track. There's a good example of this that I added in masonry_running_positions.h!
I used an in-between here of "open ending of tracks", let me know if you feel like that gives enough clairty!
This change builds track openings across open tracks as needed in orderCeleste PanSame here, and other references to "open" below, since that could be confused with other kinds of "openings"
Done
To account for open tracks: 1) inCeleste Pannit: I'd add a new line before this to make it clear all of these list items are related to "To account for open tracks"
The current version of this has a newline!
openings as needed, we can handle "open track" cases separately.Celeste Panempty
Done
// which spans from the track's running position to infinity.Celeste PanIf we already have track running positions, I wonder if we can just use that vector directly for this instead and assume that is from that index to infinity as additional openings.
Or maybe, IIRC track_collection_openings_ is in order, so maybe we can get rid of running_positions_ and just use track_collection_openings_ (with the assumption that the running position is always the last item in each subvector (not sure if that would be less performant in the non-dense packing case, though)
Discussed offline, I will go with this idea! A TODO was added in GetFirstEligibleLine for a possible optimization (which this idea would remove).
// case where a multi-span item is densely-packed across the "open" part of aCeleste PanI think using "open" here is a little confusing since there is also the concept of an opening. Maybe "empty" or something along the lines of "the part of the track after the current running position"
Responded in above comment, with a compromise, please lmk if that would make things more clear!
// If the previous track opening has an intersecting range with where the
// current track fully "opens", add a temporary track opening that spans fromCeleste Pan"the area of the track below the current running position"
Comment removed because of structural change!
// current track fully "opens", add a temporary track opening that spans from
// the current running position of this track to infinity.Celeste PanSimilar to a comment in the .h file, I wonder if it make sense to track running positions in this way in general, that way, we don't need to do anything special at this point
Ended up doing as suggested in the .h file!
if (running_positions_[track_to_check_for_openings] <=
previous_track_opening_end_position) {Celeste PanCan we replace this check with the check in this section below?
`if (current_track_opening.end_position == LayoutUnit::Max()) {`
...and get rid of the temporary opening addition and removal?
Celeste PanIt doesn't quite work to just replace the check, because that check only works inside the for-loop once we've started working with the track opening that we add in line 213.
We also would never enter the for-loop if we don't add this temporary TrackOpening; ie in the case of a completely empty track.
We could get rid of the temporary TrackOpening addition/removal, but then we'd have to have a separate outside statement, which would probably add a bit of duplicate code for calculating the overlap range, checking the number of tracks and entering the recursive method again.
Edit: comment removed as a result of a structural change.
// If we were working with the "open" ending section of a track, thereCeleste PanSimilar comment as elsewhere here
Done.
Related details
- Alison Maher
- Ian Kilpatrick
- Kurt Catti-Schmidt
Code-Coverage
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Kurt Catti-Schmidt (Gerrit)
Kurt Catti-Schmidt added 13 comments![]( "Open in Gerrit")
// If we are placing a 2-span item with a block size of 30px, then we should30px is a little confusing here, because it would fit in Track 1 without spanning. A value between 30px and 60px would be more clear.
// If we are placing a 2-span item with a block size of 30px, then we shouldInline size?
LayoutUnit GetRunningPositionForTrack(wtf_size_t track_index) const {This could use a comment "The current running position for a given track is the start position of the final opening."
// a 1D vector OR the first dimension of a 2D vector.This comment should be updated to indicate when it's 1D vs 2D.
// Constructor for 2D vector.Like the comment above, this comment should indicate when this should be used.
auto opening_end_index = track_collection_openings_[track_idx].size() - 1;`const auto`
TrackOpening{new_running_position, LayoutUnit::Max()};Can this be `new_track_opening` instead of creating a new object?
Vector<LayoutUnit> running_positions_for_span(span_size, LayoutUnit());You shouldn't use the `Vector` constructor that initializes it with values if you're going to immediately override the values afterwards. The best option here is to create an empty vector and then `ReserveInitialCapacity`.
```
Vector<LayoutUnit> running_positions_for_span;
running_positions_for_span.ReserveInitialCapacity(span_size);
```
..then in the loop, you can `emplace_back` instead of inserting at a specific position.
GetRunningPositionForTrack(span.StartLine() + index);This can be cached in a const variable so it's not looked up each iteration
Vector<TrackOpening>& current_track_openings =Can this `const` stay?
// If the first track opening opening is already greater than the highest"first track opening" seems like the very first opening, is "the first opening in the current track" more accurate?
if ((span_size > 1 && !track_collection_openings_[current_track].empty()) &&This comment should also account for span size
if (span_size == 1) {
return running_positions_;
}Was this the optimization we lose with this approach? You should add a TODO to re-introduce it.
Related details
- Alison Maher
- Celeste Pan
- Ian Kilpatrick
Code-Coverage
Code-Owners
Code-Review
No-Unresolved-Comments
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alison Maher (Gerrit)
Alison Maher added 16 comments![]( "Open in Gerrit")
1b) Because of 1aa), we can remove the `running_positions_` vector andnit: double "a"
2) set `highest_eligible_track_opening` innit: Missing capitalization
// This method accounts for laying multi-span items out into the open ending
// tracks, which spans from the track's running position to infinity.nit: "open ending of each track"
track_collection_openings_[index].emplace_back(
TrackOpening(running_positions[index], LayoutUnit::Max()));
}Should this check there isn't already an entry with a max value in each vector?
bool IsValid() const { return !track_opening_indices.empty(); }Now that every track will be represented here, will these always be valid?
We also have a case where we set start to Max in the constructor (for collapsed tracks), so should we keep that as invalid?
LayoutUnit GetRunningPositionForTrack(wtf_size_t track_index) const {
return track_collection_openings_[track_index].back().start_position;
}
Can this be made private?
// the direction in which we iterate through the vector. This can iterate over
// a 1D vector OR the first dimension of a 2D vector.I'd remove this, and expand on the second ctr comment to note that it specifically iterates over the first dimension of track collection openings
auto opening_end_index = track_collection_openings_[track_idx].size() - 1;nit: maybe last_opening_index or running_position_idx
auto opening_end_index = track_collection_openings_[track_idx].size() - 1;This one may be useful to add a helper for. Or maybe even better, since we are only using this to get `track_collection_openings_[track_idx][opening_end_index]`, maybe a helper that gets this, and gets that idx within that helper method
// means that a opening will be formed after placement. We should only ever
// be accounting for track openings in the case of dense packing.nit: This is no longer fully true
track_collection_openings_[track_idx].emplace_back(new_track_opening);Instead of adding a new one, can we just update the existing one's start? Could be another helper too
TrackOpening{new_running_position, LayoutUnit::Max()};Same here, can the start of this opening just be updated instead?
const Vector<TrackOpening>& current_track_openings =Is removing this needed anymore?
for (wtf_size_t index = 0; index < span_size; ++index) {
running_positions_for_span[index] =
GetRunningPositionForTrack(span.StartLine() + index);
}
return *(std::max_element(running_positions_for_span.begin(),
running_positions_for_span.end()));Can we calculate this max as we loop in the new for-loop instead? This would avoid double looping
// with the existing auto-placed location of the item.nit: "against"
if ((span_size > 1 && !track_collection_openings_[current_track].empty()) &&Why do we only do this if span_size is > 1? Might be worth calling out in the comment above
Related details
- Celeste Pan
- Ian Kilpatrick
Celeste Pan (Gerrit)
Celeste Pan added 29 comments![]( "Open in Gerrit")
1b) Because of 1aa), we can remove the `running_positions_` vector andCeleste Pannit: double "a"
Done
2) set `highest_eligible_track_opening` inCeleste Pannit: Missing capitalization
Done
// If we are placing a 2-span item with a block size of 30px, then we should30px is a little confusing here, because it would fit in Track 1 without spanning. A value between 30px and 60px would be more clear.
I can say that it has an inline size of 50px, but I think I should keep the block size of the item to demonstrate that it can be packed into the track opening!
// If we are placing a 2-span item with a block size of 30px, then we shouldCeleste PanInline size?
It should be block size, since the item would have a height of 30px, which means it can fit into the track opening in Track 2 which has a block size/height of 30px.
I realized that the diagram is a bit confusing, so I specified that the dotted lines represent OCCUPIED tracks.
// This method accounts for laying multi-span items out into the open ending
// tracks, which spans from the track's running position to infinity.nit: "open ending of each track"
Done
track_collection_openings_[index].emplace_back(
TrackOpening(running_positions[index], LayoutUnit::Max()));
}Should this check there isn't already an entry with a max value in each vector?
This was fixed with the upload after responding to Kurt's comments!
bool IsValid() const { return !track_opening_indices.empty(); }Now that every track will be represented here, will these always be valid?
We also have a case where we set start to Max in the constructor (for collapsed tracks), so should we keep that as invalid?
When we're creating the path in `AccumulateTrackOpeningsToAccommodateItem`, we only ever start populating `track_opening_indices` once we've reached the end of what is a path that can accommodate the item, and as we go back "up" the recursive path, we add add the track opening index to the `track_opening_indices` vector. So this is still a valid indicator of whether or not we've found a series of track openings / open end of tracks to accommodate the item.
If the start position of a track opening is set to "max", then nothing will ever be valid when we attempt to create a path across that track because the overlap range with that track will always be 0.
LayoutUnit GetRunningPositionForTrack(wtf_size_t track_index) const {
return track_collection_openings_[track_index].back().start_position;
}
Can this be made private?
Done
LayoutUnit GetRunningPositionForTrack(wtf_size_t track_index) const {This could use a comment "The current running position for a given track is the start position of the final opening."
Done
// a 1D vector OR the first dimension of a 2D vector.This comment should be updated to indicate when it's 1D vs 2D.
Done
// the direction in which we iterate through the vector. This can iterate over
// a 1D vector OR the first dimension of a 2D vector.I'd remove this, and expand on the second ctr comment to note that it specifically iterates over the first dimension of track collection openings
This was done in response to kurt's comments in the most recent iteration.
Like the comment above, this comment should indicate when this should be used.
Done
auto opening_end_index = track_collection_openings_[track_idx].size() - 1;This one may be useful to add a helper for. Or maybe even better, since we are only using this to get `track_collection_openings_[track_idx][opening_end_index]`, maybe a helper that gets this, and gets that idx within that helper method
I'm not entirely sure what you're looking for here, I did implement a getter for a reference to the last element though!
auto opening_end_index = track_collection_openings_[track_idx].size() - 1;nit: maybe last_opening_index or running_position_idx
Changed to something in between, `open_ending_of_track_idx`, let me know if that works!
auto opening_end_index = track_collection_openings_[track_idx].size() - 1;Celeste Pan`const auto`
Done
// means that a opening will be formed after placement. We should only ever
// be accounting for track openings in the case of dense packing.nit: This is no longer fully true
Technically we should only ever be creating new track openings in this method if dense-packing is enabled; I changed the wording so that it's more accurate to our current situation.
track_collection_openings_[track_idx].emplace_back(new_track_opening);Instead of adding a new one, can we just update the existing one's start? Could be another helper too
Well in the previous line we're already updating the existing one's start, and then here we're adding a new track opening to account for the existing one being updated. We need to have a net addition of 1 new track opening, since we enter this conditional if a new track opening is created.
TrackOpening{new_running_position, LayoutUnit::Max()};Same here, can the start of this opening just be updated instead?
In this case, yes we can just update it, but I do feel like it would be less lines of code and less error-prone as well. If you feel strongly that we should just update instead, please let me know!
TrackOpening{new_running_position, LayoutUnit::Max()};Can this be `new_track_opening` instead of creating a new object?
Yes!
Vector<LayoutUnit> running_positions_for_span(span_size, LayoutUnit());You shouldn't use the `Vector` constructor that initializes it with values if you're going to immediately override the values afterwards. The best option here is to create an empty vector and then `ReserveInitialCapacity`.
```
Vector<LayoutUnit> running_positions_for_span;
running_positions_for_span.ReserveInitialCapacity(span_size);
```..then in the loop, you can `emplace_back` instead of inserting at a specific position.
Done
GetRunningPositionForTrack(span.StartLine() + index);This can be cached in a const variable so it's not looked up each iteration
Done
const Vector<TrackOpening>& current_track_openings =Is removing this needed anymore?
Hm, I don't see what's being removed here. Would you mind clarifying?
for (wtf_size_t index = 0; index < span_size; ++index) {
running_positions_for_span[index] =
GetRunningPositionForTrack(span.StartLine() + index);
}
return *(std::max_element(running_positions_for_span.begin(),
running_positions_for_span.end()));Can we calculate this max as we loop in the new for-loop instead? This would avoid double looping
Done
Vector<TrackOpening>& current_track_openings =Celeste PanCan this `const` stay?
yup, thanks for the catch!
// with the existing auto-placed location of the item.Celeste Pannit: "against"
Done
// If the first track opening opening is already greater than the highest"first track opening" seems like the very first opening, is "the first opening in the current track" more accurate?
yes, I'll make that more clear.
if ((span_size > 1 && !track_collection_openings_[current_track].empty()) &&Why do we only do this if span_size is > 1? Might be worth calling out in the comment above
This was removed in response to kurt's comment!
if ((span_size > 1 && !track_collection_openings_[current_track].empty()) &&This comment should also account for span size
The span size was actually leftover code from when we were using our previous structure, so removing the span size check!
if (span_size == 1) {
return running_positions_;
}Was this the optimization we lose with this approach? You should add a TODO to re-introduce it.
Yes, I added the TODO in `GetFirstEligibleLine` since that is the location where we'd re-account for the loss.
Related details
- Alison Maher
- Ian Kilpatrick
- Kurt Catti-Schmidt
Code-Coverage
Code-Owners
Code-Review
No-Unresolved-Comments
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |