Closed Bug 1552712 Opened 2 years ago Closed 2 years ago

IntervalSet::Intersection() can be slow


(Core :: Audio/Video: Playback, defect, P2)




Tracking Status
firefox69 --- fixed


(Reporter: cpearce, Assigned: cpearce)



(2 files)

As seen here, we can end up spending a lot of time doing TimeIntervals::Intersection().

As seen in this profile:

I've seen this exact problem before in my personal data mining work.

We're spending a lot of time in nsTArray<media::Interval>::AppendElement(). This is caused by reallocating the arrays' storage, and copying the old data over to the new storage. As we append in a loop, these reallocations happen enough that it ends up being expensive.

We could make this faster by either:

  1. Ensuring the array has a capacity equal to the minimum of the two input TimeIntervals' lengths before we start appending into it.
  2. Doing the intersection twice, first to calculate the length of the result without storing the result, and second time to store the result. Given that the profile shows other parts of Intersection() is slow, it's probably fastest to do option 1.

Profiling shows we can spend a lot of time in IntervalSet::Intersection().

Much of this time is spent appending elements to a temporary buffer as we
loop over the two IntervalSets' arrays comparing them. As we append, the
storage of the temporary array is reallocated as the storage must grow to
hold more elements. These reallocations are expensive, as we must copy the
old elements to the new storage.

So before starting the loop, reserve enough capacity to store the upper
bound; the minimum of the two IntervalSets' lengths. This may waste memory,
but will be faster, as expensive reallocations are avoided.

Also use SwapElements() instead of AppendElements(), to further avoid
extra copies.

Priority: -- → P2
Attachment #9065929 - Attachment description: Bug 1552712 - Reserve capacity in IntervalSet::Intersection() and use SwapElements() instead of copying temporary. r?jya → Bug 1552712 - Reserve capacity in IntervalSet::Intersection(). r?jya
Pushed by
Reserve capacity in IntervalSet::Intersection(). r=jya

Previous patch in Bug 1552712 actually didn't set the correct upper bound; it
failed to set the upper bound in cases like:

intersect({[0,10]}, {[0,1], [2,3], [4,5]})

That's clearly the maximum of the lengths of the array, not the minimum.

Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla69

Looking at comment 3 and the rev above this does not look FIXED, right?

Flags: needinfo?(cpearce)
Resolution: FIXED → ---
Pushed by
Reserve upper bound for capacity of IntervalSet::Intersection(). r=jya

(In reply to Stefan Fleiter (:sfleiter) from comment #5)

Looking at comment 3 and the rev above this does not look FIXED, right?

Yes, thank you for the need-info request!

Flags: needinfo?(cpearce)
Closed: 2 years ago2 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.