Closed Bug 1479996 Opened 2 years ago Closed 2 years ago

micro-optimize frame properties - avoid ptr->index->ptr dance


(Core :: Layout, enhancement, P3)




Tracking Status
firefox63 --- fixed


(Reporter: gerald, Assigned: gerald)


(Blocks 2 open bugs)



(1 file)

Bug 1478138 introduced an optimization in FrameProperties::{G,S}etInternal where following nsTArray::IndexOf, we know the returned index *must* be valid, so it is more efficient to use nsTArray::operator[] instead of ElementAt (the latter does a bound check).

In bug 1478138 comment 4 I suggested a further optimization:
Because IndexOf converts a pointer in the array to an index, and then operator[] converts the index back into the original pointer, it would be more efficient to directly get a pointer from an IndexOf-like function.
Or, for better safety, the IndexOf-like function could be given lambdas, one to call with the found element and the other one if nothing is found.

Simple proof of concept showing the apparent benefit in generated code:
E.g., results with clang 6.0.0 -O3: Something like FrameProperties::GetInternal() takes 32 instructions with IndexOf+operator[], only 23 instructions with lambda-friendly function.

This could benefit other users of nsTArray, if they have similar needs.

Note: Optimizing RemoveInternal is trickier and probably won't be touched in this bug.
In many places, nsTArray::IndexOf is followed by accessing that element
(hopefully with `Elements() + index`, which skips unnecessary bounds checks.)
But this pattern introduces operations that could be avoided:
- IndexOf converts the address of the found element into an index,
- The caller must test for a special `NoIndex` value,
- On success, accesses convert that index back into the original address.

This patch introduces new 'ApplyIf...' functions that combine all these
operations in a more efficient ensemble: If the sought element is found, it is
passed by reference to a given callable object (usually a lambda); if not
found, another callable is invoked.
On top of removing the pointer->index->pointer operations, invoking callables
directly from ApplyIf is safer, as the array is guaranteed to be untouched at
this time.
Also, being templates taking function objects, in most cases the compiler should
be able to inline and optimize the search and its callables' code.

This patch gives example uses in nsTArray::Contains, and in
FrameProperties::GetInternal, SetInternal.
And FrameProperties::Has now calls Contains, which is more efficient.
Depends on: 1482046
Comment on attachment 8997764 [details]
Bug 1479996 - Combine nsTArray::IndexOf and element access into lambda-friendly functions - r?froydnj

Nathan Froyd [:froydnj] has approved the revision.
Attachment #8997764 - Flags: review+
Pushed by
Combine nsTArray::IndexOf and element access into lambda-friendly functions - r=froydnj
Blocks: 1486941
Blocks: 1486967
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla63
You need to log in before you can comment on or make changes to this bug.