Closed
Bug 1113300
Opened 10 years ago
Closed 10 years ago
Add a way to pop the last element off of a SegmentedVector
Categories
(Core :: MFBT, defect)
Core
MFBT
Tracking
()
RESOLVED
FIXED
mozilla41
Tracking | Status | |
---|---|---|
firefox41 | --- | fixed |
People
(Reporter: mccr8, Assigned: mccr8)
References
Details
Attachments
(1 file, 2 obsolete files)
(deleted),
patch
|
froydnj
:
review+
|
Details | Diff | Splinter Review |
We have a number of incremental destroyers in the browser. These are basically a big bag of owning pointers to some kind of data structures, which we periodically remove things from and destroy. We don't really care about the order they are destroyed in. SegmentedVector seems like a good data structure for this use case, but it does not have a way to remove things from the vector, except by destroying the entire thing.
I was thinking one way to add this would be to add two methods, GetLast(), which returns a reference to the very last thing in the vector, and PopLast(), which removes the last thing from the vector. Then you could write a while loop with !IsEmpty(), breaking out of the loop after some period of time has passed. (Maybe PopLast() could just do some kind of move return, but I don't know how that would work.) This isn't the most efficient thing in the world, but we can implement each of those operations in constant time.
Does anybody have thoughts about what sort of API would be good for this use case?
Assignee | ||
Updated•10 years ago
|
Summary: Add a way to remove things from SegmentedVector → Add a way to incrementally remove things from SegmentedVector
Assignee | ||
Comment 1•10 years ago
|
||
Assignee | ||
Comment 2•10 years ago
|
||
See the newest patch in bug 866681 for an example of how this could be used.
Assignee | ||
Updated•10 years ago
|
Attachment #8538690 -
Flags: feedback?(nfroyd)
Comment 3•10 years ago
|
||
Comment on attachment 8538690 [details] [diff] [review]
Add a way to use SegmentedVector like a stack. WIP
Review of attachment 8538690 [details] [diff] [review]:
-----------------------------------------------------------------
Please add testing to mfbt/tests/TestSegmentedVector.cpp.
::: mfbt/SegmentedVector.h
@@ +207,5 @@
> + const T& GetLast() const
> + {
> + MOZ_ASSERT(!IsEmpty());
> + Segment* last = mSegments.getLast();
> + return (*last)[last->Length() - 1];
This feels a bit dangerous. Presumably GetLast() and PopLast() will typically be called in pairs. It'll be fine if you complete all your uses of the element obtained by GetLast() before calling PopLast(). But if you don't, I think you'll end up with use-after-free errors.
Making PopLast() instead return a copy would be safer. As Olli said, ideally it'd be a move instead of a copy but is that possible?
@@ +215,5 @@
> + {
> + MOZ_ASSERT(!IsEmpty());
> + Segment* last = mSegments.getLast();
> + last->PopLast();
> + if (!last->Length()) {
This idiom is a pet hate of mine; please use |last->Length() != 0| or |last->Length() > 0| :)
Assignee | ||
Comment 4•10 years ago
|
||
(In reply to Nicholas Nethercote [:njn] from comment #3)
> Please add testing to mfbt/tests/TestSegmentedVector.cpp.
Yeah, I was going to do that at some point.
> ::: mfbt/SegmentedVector.h
> @@ +207,5 @@
> This feels a bit dangerous.
Well, that's the same as any other array getter I think. ;)
> As Olli said, ideally it'd be a move instead of a copy but is that possible?
Where did Olli say that? Yeah, the other way I was thinking of doing it would be just having a PopLast() instruction that somehow uses move semantics to return the element, but I'm not sure how you write that. For the particular case I'm interested in, the vector will hold COMptrs so the move will just do a forget() which will work nicely.
> This idiom is a pet hate of mine; please use |last->Length() != 0| or
> |last->Length() > 0| :)
I suppose it is a bit extra ridiculous for non-pointers. Maybe it isn't idiomatic then, I'm not sure.
Comment 5•10 years ago
|
||
(In reply to Andrew McCreight [:mccr8] (away-ish Dec 17-26) from comment #4)
> > As Olli said, ideally it'd be a move instead of a copy but is that possible?
>
> Where did Olli say that? Yeah, the other way I was thinking of doing it
> would be just having a PopLast() instruction that somehow uses move
> semantics to return the element, but I'm not sure how you write that. For
> the particular case I'm interested in, the vector will hold COMptrs so the
> move will just do a forget() which will work nicely.
Well, the way to do it would be to have |T PopLast()|, and that T would support move construction and assignment, so that you'd have:
T PopLast() {
Segment* lastSegment = mSegments.getLast();
T lastElement(Move((*last)[last->Length() - 1]));
// ...whatever bookkeeping needs to be done;
return lastElement; // assume NRVO will take care of the copy constructor.
};
T element(vector->PopLast());
should just magically work. But you have a pretty inefficient API if T is not movable...
Comment 6•10 years ago
|
||
Comment on attachment 8538690 [details] [diff] [review]
Add a way to use SegmentedVector like a stack. WIP
Review of attachment 8538690 [details] [diff] [review]:
-----------------------------------------------------------------
Agreed that the GetLast/PopLast pairing requirement is a footgun, but C++ has had these kind of footguns for a while now (any of the std:: containers have a similar problem; the SGI folks even documented this problem where the STL was being developed: http://www.sgi.com/tech/stl/stack.html There's also concerns around exception safety, which we don't have to care about...).
Attachment #8538690 -
Flags: feedback?(nfroyd) → feedback+
Assignee | ||
Updated•10 years ago
|
Assignee: nobody → continuation
Assignee | ||
Updated•10 years ago
|
Summary: Add a way to incrementally remove things from SegmentedVector → Add a way to pop the last element off of a SegmentedVector
Assignee | ||
Comment 7•10 years ago
|
||
This is basically what you described in comment 5. I like it a little more, though I don't know if it just won't compile if the type isn't movable or if you just get a nice little hidden perf fault.
Comment 8•10 years ago
|
||
Comment on attachment 8540176 [details] [diff] [review]
Add a way to pop the last element off a SegmentedVector.
Review of attachment 8540176 [details] [diff] [review]:
-----------------------------------------------------------------
> I don't know if it just won't compile if the type isn't movable or if you just get a nice little hidden perf fault.
In TestSegmentedVector.cpp there is a function TestConstructorsAndDestructors() which does some testing to make sure the right kind of constructors and destructors are called the right number of times for different cases. You should be able to determine what happens in there, and test for it.
Assignee | ||
Comment 9•10 years ago
|
||
Do you have a preference for which of these two patches I should go with, Nathan? I don't care too much.
Flags: needinfo?(nfroyd)
Comment 10•10 years ago
|
||
I think the way in attachment 8538690 [details] [diff] [review] is slightly better; Gecko hasn't really bought into the returning-aggregates-is-OK C++ style yet.
I think attachment 8540176 [details] [diff] [review] would be OK if you added a polyfill in TypeTraits.h for std::{is_trivially_copyable,is_move_constructable} (and maybe is_copy_constructable) and made SegmentedVector static_assert the appropriate properties, so we didn't get the hidden perf-faults...
Flags: needinfo?(nfroyd)
Assignee | ||
Updated•10 years ago
|
Attachment #8540176 -
Attachment is obsolete: true
Assignee | ||
Comment 11•10 years ago
|
||
No hurry on the review, my patches that use this code are having some unrelated issues that I haven't figured out yet.
try run: https://treeherder.mozilla.org/#/jobs?repo=try&revision=e3135008e064
The problems are later in the stack, and I think unrelated to the SegmentedVector.
Attachment #8538690 -
Attachment is obsolete: true
Attachment #8602797 -
Flags: review?(nfroyd)
Updated•10 years ago
|
Attachment #8602797 -
Flags: review?(nfroyd) → review+
Assignee | ||
Updated•10 years ago
|
Keywords: checkin-needed
Comment 12•10 years ago
|
||
Keywords: checkin-needed
Comment 13•10 years ago
|
||
Comment 14•10 years ago
|
||
Status: NEW → RESOLVED
Closed: 10 years ago
status-firefox41:
--- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla41
You need to log in
before you can comment on or make changes to this bug.
Description
•