Closed Bug 1478337 Opened 4 years ago Closed 4 years ago

avoid useless work in nsTArray::RemoveElement


(Core :: XPCOM, enhancement)

Not set



Tracking Status
firefox63 --- fixed


(Reporter: froydnj, Assigned: froydnj)



(1 file)

When removing an element that exists in the array, there's no need to
perform extra bounds checks for actually removing the element; the
presence of the element guarantees that we have a valid index and a
valid range to remove.  So split RemoveElementsAt into a safe interface
and an unsafe interface, and let RemoveElement call the latter as an
internal optimization.  The same logic applies to RemoveElementSorted.

We call RemoveElement depressingly often, so this is a nice little win.
Inspired by looking at other things.
Attachment #8994819 - Flags: review?(erahm)
Attachment #8994819 - Flags: review?(erahm) → review+
Chasing you around bugs, always arriving too late! :-D

(In reply to Nathan Froyd [:froydnj] from bug 1478138 comment #5)
> (In reply to Gerald Squelart [:gerald] from bug 1478138 comment #4)
> > Idea:
> > Instead of doing an IndexOf (which goes through the elements already, and
> > calculates an index from a pointer) followed by operator[] (which needs to
> > recalculate the pointer from the index), why not have a search function that
> > returns a pointer to the element or nullptr?
> > A less scary option could be a function that takes a lambda and runs it on
> > the reference of the found element (if any).

My idea was only related to FrameProperties::SetInternal, where work is done on the found element and there is no need for the index itself.

> The frame property manipulation functions indicate that we're missing some
> kind of interface: both RemoveInternal and DeleteInternal are needlessly
> inefficient, because the RemoveElementAt will do unnecessary bounds checks. 
> I'm not quite sure what the right interface is, though.  For those cases, if
> you returned a pointer to the element, or even ran a lambda on the found
> element, you'd need to add a RemoveElementByPointer or something, which is
> very sketchy.

You could have a function that runs a lambda on the found element, and then removes that element from the array. This would remove all index<->pointer computations -- it would be interesting to see if compilers can optimize those out in your code.

> For RemoveInternal, at least, some RemoveElement-style function that returns
> a Maybe<T> would be about right.  I guess that would work for
> DeleteInternal, too?

You mean return a copy of the removed element in a Maybe<elem_type>? That could work, yes.
The lambda-accepting function has the advantage of taking a reference while the object is still in the array, which would help for big element types.

But your patch here does the job too, though it's playing with fire. :-)
Pushed by
avoid useless work in nsTArray::RemoveElement; r=erahm
Closed: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla63
You need to log in before you can comment on or make changes to this bug.