1431122 - Add SwapRemoveElementsAt to nsTArray

Status: RESOLVED FIXED

(Core :: XPCOM, enhancement)

Description

[Nika Layzell [:nika] (ni? for response)]

jeff was requesting a method for performing O(1) unordered removes from nsTArray, so I threw this patch together.

Comment 1

[Nika Layzell [:nika] (ni? for response)]

Attachment: Add SwapRemoveElementsAt to nsTArray

Comment 2

[Nika Layzell [:nika] (ni? for response)]

Comment on attachment 8943291 [details] [diff] [review]
Add SwapRemoveElementsAt to nsTArray

Review of attachment 8943291 [details] [diff] [review]:
-----------------------------------------------------------------

::: xpcom/ds/nsTArray-inl.h
@@ +295,5 @@
> +
> +  // Perform swap (change units to bytes first)
> +  index_type sourceBytes = mHdr->mLength * aElemSize;
> +  index_type destBytes = aStart * aElemSize;
> +  

Sorry about this trailing whitespace. Was trying out a different editor set up I'm not used to for this patch.

Comment 3

[Nathan Froyd [:froydnj]]

Comment on attachment 8943291 [details] [diff] [review]
Add SwapRemoveElementsAt to nsTArray

Review of attachment 8943291 [details] [diff] [review]:
-----------------------------------------------------------------

Tests for these would be splendid.  I think there are some other things to fix, see below.

I'm not super-convinced about the names, but I also haven't thought about them very hard.

::: xpcom/ds/nsTArray-inl.h
@@ +287,5 @@
> +
> +  // Check that we have enough elements in the tail and if we don't, clamp down
> +  // the number of elements we shift in.
> +  size_type tail = mHdr->mLength - (aStart + aCount);
> +  size_type toShift = std::min(aCount, tail);

This clamping would need to be reflected in the documentation somewhere.

@@ +294,5 @@
> +  mHdr->mLength -= aCount;
> +
> +  // Perform swap (change units to bytes first)
> +  index_type sourceBytes = mHdr->mLength * aElemSize;
> +  index_type destBytes = aStart * aElemSize;

Do you need to actually compute in bytes here, or can you pass in &Elements()[mHdr->mLength] and &Elements()[aStart] for src and dest below?

@@ +297,5 @@
> +  index_type sourceBytes = mHdr->mLength * aElemSize;
> +  index_type destBytes = aStart * aElemSize;
> +  
> +  char* baseAddr = reinterpret_cast<char*>(mHdr + 1) + aStart;
> +  Copy::MoveNonOverlappingRegion(baseAddr + destBytes,

We need some assertions that the regions are not, in fact, overlapping, either in MoveNonOverlappingRegion itself or here.  Documentation of this fact would be good as well.

::: xpcom/ds/nsTArray.h
@@ +410,5 @@
>    void ShiftData(index_type aStart, size_type aOldLen, size_type aNewLen,
>                   size_type aElemSize, size_t aElemAlign);
>  
> +  // This method may be called to swap elements from the end of the array to 
> +  // fill a "gap" in the array. If the resulting array has zero elements, then 

Nit: trailing whitespace on these two lines.

@@ +411,5 @@
>                   size_type aElemSize, size_t aElemAlign);
>  
> +  // This method may be called to swap elements from the end of the array to 
> +  // fill a "gap" in the array. If the resulting array has zero elements, then 
> +  // the array's memory is free'd.

This business about the array's memory being freed does not appear in the actual code, AFAICS.  Is is really possible for the array to have zero size after this anyway?  You're just moving elements in the array around, so assuming you move a non-zero # of elements, you have to have a non-zero length array at the end, right?

@@ +1728,5 @@
>    void RemoveElementAt(index_type aIndex) { RemoveElementsAt(aIndex, 1); }
> +  
> +  // This method removes a range of elements from this array. Unlike
> +  // RemoveElementAt, this method does not preserve the order of the array.
> +  // The removed elements are replaces by the tail elements of the vector.

Nit: "replaced".

@@ +1729,5 @@
> +  
> +  // This method removes a range of elements from this array. Unlike
> +  // RemoveElementAt, this method does not preserve the order of the array.
> +  // The removed elements are replaces by the tail elements of the vector.
> +  // This method is O(N) where N is the number of elements being removed.

We need to say something about what happens if the range you're swapping into and the range that you're swapping from overlap, don't we?

@@ +1737,5 @@
> +
> +  // A variation on the SwapRemoveElementsAt method defined above.
> +  //
> +  // This method is O(1), but does not preserve the order of the elements.
> +  void SwapRemoveElementAt(index_type aIndex) { SwapRemoveElementsAt(aIndex, 1); }

This should fail on single-element arrays, right?  Do we catch that?

@@ +2079,5 @@
> +nsTArray_Impl<E, Alloc>::SwapRemoveElementsAt(index_type aStart, size_type aCount)
> +{
> +  MOZ_ASSERT(aCount == 0 || aStart < Length(), "Invalid aStart index");
> +
> +  mozilla::CheckedInt<index_type> rangeEnd = aStart;

++ for using CheckedInt.

Comment 4

[Nika Layzell [:nika] (ni? for response)]

Attachment: Part 1: Add SwapRemoveElement{s,}At to nsTArray

I've tried to address your comments, however in some cases, I think you misunderstood what some functions were doing. I've tried to add a bunch of comments to make what's happening as clear as possible.

> Do you need to actually compute in bytes here, or can you pass in &Elements()[mHdr->mLength] and &Elements()[aStart] for src and dest below?

Unfortunately, this method is on nsTArray_base, not nsTArray proper, so the `Elements` method is not defined.

MozReview-Commit-ID: H0oqG7H7299

Comment 5

[Nika Layzell [:nika] (ni? for response)]

Attachment: Part 2: Add tests for the new SwapRemoveElement{s}At method

MozReview-Commit-ID: DuB2oiT8l49

Comment 6

[Nathan Froyd [:froydnj]]

Comment on attachment 8944108 [details] [diff] [review]
Part 1: Add SwapRemoveElement{s,}At to nsTArray

Review of attachment 8944108 [details] [diff] [review]:
-----------------------------------------------------------------

I was indeed getting a few things screwed up, thanks for all the clarifications.

I'm not a super fan of the name, though, especially because we're only swapping in about half of the cases.  RemoveElement{,s}WithoutPreservingOrder is a bit of a mouthful, though.  RemoveElements{,s}AtScramblingOrder? =D

::: xpcom/ds/nsTArray-inl.h
@@ +294,5 @@
> +  mHdr->mLength -= aCount;
> +
> +  if (mHdr->mLength == 0) {
> +    // If we have no elements remaining in the array, we can free our buffer.
> +    ShrinkCapacity(aElemSize, aElemAlign);

Maybe we should just `return;` out of this `if`, and then we wouldn't need the extra level of indentation below and the control flow would be a little clearer?

@@ +299,5 @@
> +  } else {
> +    // Determine how many elements we need to move from the end of the array into
> +    // the now-removed section. This will either be the number of elements which
> +    // were removed (if there are more elements in the tail of the array), or the
> +    // entire tail of the array. Whichever is smaller.

Nit: "...array, whichever is smaller."

@@ +316,5 @@
> +    // contains only invalid entries which need to be overwritten.
> +    MOZ_ASSERT(sourceBytes >= destBytes,
> +               "The source should be after the destination.");
> +    MOZ_ASSERT(sourceBytes - destBytes <= relocCount,
> +               "The range should be nonoverlapping");

The left side of the condition here is in units of bytes, whereas the right side is in units of elements.  Is that a correct interpretation of the assert as written?  That's not what we want to be testing, is it?

::: xpcom/ds/nsTArray.h
@@ +1728,5 @@
>    // A variation on the RemoveElementsAt method defined above.
>    void RemoveElementAt(index_type aIndex) { RemoveElementsAt(aIndex, 1); }
>  
> +  // This method performs index-based removals from an array without preserving
> +  // the order of the array.

Maybe say something about how this is useful if you are using the array as a set data structure?

@@ +1731,5 @@
> +  // This method performs index-based removals from an array without preserving
> +  // the order of the array.
> +  //
> +  // These removals are efficient, as they keep as many elements in the array in
> +  // the same place that they started as possible. At most N elements, where N

"as many elements in the array in the same place that they started as possible" seems like a mouthful.

WDYT about "as they move as few elements as possible"?

Comment 7

[Nathan Froyd [:froydnj]]

Comment on attachment 8944109 [details] [diff] [review]
Part 2: Add tests for the new SwapRemoveElement{s}At method

Review of attachment 8944109 [details] [diff] [review]:
-----------------------------------------------------------------

I think we need a few more tests, but this is pretty reasonable.  If we *really* wanted to test things, we'd write tests with elements having custom construction/destruction/move behaviors, and then count that we only constructed/destroyed/moved the number of expected elements.  But I think this will be OK.

::: xpcom/tests/gtest/TestTArray.cpp
@@ +205,5 @@
>  
> +TEST(TArray, SwapRemoveElements)
> +{
> +  // When removing an element from the end of the array, it can be removed in
> +  // place, by destroying it and decrementing the length.

Please add tests that make sure we DTRT for removing all the elements in the array with both SwapRemoveElementAt and SwapRemoveElementsAt.

@@ +257,5 @@
> +    ASSERT_EQ(array, goal);
> +  }
> +
> +  // And if fewer elements are removed than exist after the removed section,
> +  // elements will be moved from the end of the array to fill the vacated space.

Can you add a test that ensures that if the # of elements removed exactly equals the number of elements remaining after the removed section, everything works OK?  For both SwapRemoveElementAt and SwapRemoveElementsAt, please.

Adding some tests that ensure removing from the absolute beginning of the array works would probably be a good idea.  I think such cases are likely duplicates of what you test above, but they'd be good to make sure we aren't corrupting memory or something like that?

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e9724b1b77c3
Part 1: Add UnorderedRemoveElement[s]At to nsTArray, r=froydnj
https://hg.mozilla.org/integration/mozilla-inbound/rev/20d68972562d
Part 2: Add tests for UnorderedRemoveElement[s]At, r=froydnj

Comment 9

[Narcis Beleuzu [:NarcisB]]

https://hg.mozilla.org/mozilla-central/rev/e9724b1b77c3
https://hg.mozilla.org/mozilla-central/rev/20d68972562d

Comment 10

[Natalia Csoregi [:nataliaCs]]

There are some Gtest failures that started occuring (mostly) on Inbound, and later on m-c and autoland after the merges (just a few though).
Failure log: https://treeherder.mozilla.org/logviewer.html#?job_id=158452982&repo=mozilla-inbound&lineNumber=2895
Snippet: 
task 2018-01-25T13:48:21.795Z] 13:48:21     INFO -  TEST-START | AllocReplacement.posix_memalign_check
2895
[task 2018-01-25T13:48:21.795Z] 13:48:21  WARNING -  TEST-UNEXPECTED-FAIL | AllocReplacement.posix_memalign_check | Value of: (ValidateHookedAllocation([] { void* p = nullptr; int result = posix_memalign(&p, sizeof(void*), kAllocAmount); if (result != 0) { return static_cast<void*>(nullptr); } return p; }, free))
2896
[task 2018-01-25T13:48:21.795Z] 13:48:21     INFO -    Actual: false
2897
[task 2018-01-25T13:48:21.795Z] 13:48:21     INFO -  Expected: true @ /builds/worker/workspace/build/src/xpcom/tests/gtest/TestAllocReplacement.cpp:140
2898
[task 2018-01-25T13:48:21.796Z] 13:48:21  WARNING -  TEST-UNEXPECTED-FAIL | AllocReplacement.posix_memalign_check | test completed (time: 0ms)

Retriggering the jobs on Linux opt, it lead us to this push https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=20d68972562ded3b6fa6fe48c4b8db9022591b31&filter-searchStr=linux%20gtest as the one that has triggered them. 

@mystor can you please take a look into this?

Comment 11

[Nika Layzell [:nika] (ni? for response)]

(In reply to Natalia Csoregi [:nataliaCs] from comment #10)

> @mystor can you please take a look into this?

I think this is probably related to what nathan was referring to here: https://bugzilla.mozilla.org/show_bug.cgi?id=1433015#c6

Going to try that fix and hopefully it'll fix the root problem.