1478337 - avoid useless work in nsTArray::RemoveElement

Status: RESOLVED FIXED

(Core :: XPCOM, enhancement)

Description

[Nathan Froyd [:froydnj]]

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.

Comment 1

[Nathan Froyd [:froydnj]]

Attachment: avoid useless work in nsTArray::RemoveElement

Inspired by looking at other things.

Comment 2

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

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

Comment 3

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/cfcce8ee55fc
avoid useless work in nsTArray::RemoveElement; r=erahm

Comment 4

[Natalia Csoregi [:nataliaCs]]

https://hg.mozilla.org/mozilla-central/rev/cfcce8ee55fc