1113300 - Add a way to pop the last element off of a SegmentedVector

Status: RESOLVED FIXED

(Core :: MFBT, defect)

Description

[Andrew McCreight [:mccr8]]

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?

Comment 1

[Andrew McCreight [:mccr8]]

Attachment: Add a way to use SegmentedVector like a stack. WIP

Comment 2

[Andrew McCreight [:mccr8]]

See the newest patch in bug 866681 for an example of how this could be used.

Comment 3

[Nicholas Nethercote [inactive]]

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| :)

Comment 4

[Andrew McCreight [:mccr8]]

(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

[Nathan Froyd [:froydnj]]

(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

[Nathan Froyd [:froydnj]]

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...).

Comment 7

[Andrew McCreight [:mccr8]]

Attachment: Add a way to pop the last element off a SegmentedVector.

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

[Nicholas Nethercote [inactive]]

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.

Comment 9

[Andrew McCreight [:mccr8]]

Do you have a preference for which of these two patches I should go with, Nathan?  I don't care too much.

Comment 10

[Nathan Froyd [:froydnj]]

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...

Comment 11

[Andrew McCreight [:mccr8]]

Attachment: Add a way to use SegmentedVector like a stack.

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.

Comment 12

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/68eca487cb37

Comment 13

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/68eca487cb37

Comment 14

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/68eca487cb37