580869 - Cache the frame found in nsTextFrame::GetChildFrameContainingOffset

Status: RESOLVED FIXED

(Core :: Layout: Text and Fonts, defect)

Description

[(no longer active)]

The caret code currently caches the caret position as a tuple: (DOM node, Offset, Left/right hint).  In order to calculate the coordinates at which the caret frame should be positioned, it needs to find the exact frame containing the offset of the DOM node.

Let's see how frequently that code is run: once on every time we hit the caret paining timer, and twice after typing any character in an editable fieled (possibly among others).  The "twice" there comes from once shoring the caret, and once scrolling the selection into view (see bug 240933 comment 58).

The best (?) solution here for now is to cache the frame containing the offset when we calculate it once in nsTextFrame::GetChildFrameContainingOffset as a frame property, and next time check the cache before trying to compute everything from scratch.

I'll start working on the implementation tomorrow.  Hint to self: to set a frame property, call frame->Properties().Set().

Comment 1

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Once or twice per paint or input event doesn't sound like a lot to me. Have you got profile data showing this is a significant problem?

Comment 2

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I guess you do in bug 240933.

The issue is not really that it happens a lot, but that it can be really slow when it does happen.

Comment 3

[(no longer active)]

(In reply to comment #2)
> The issue is not really that it happens a lot, but that it can be really slow
> when it does happen.

Exactly.  I've seen this take about 15% of our time when going to the end of a large textarea, and press and hold a key down.  On an optimized build with no debugger/profiler attached, the lag here is visible to the naked eye.

Comment 4

[(no longer active)]

Attachment: Patch (v1)

So, I wrote two patches for this bug.  The first patch (which is the version I recommend we should take) just caches the latest result.  The second one (which I'll attach in a moment) creates a hashtable to store all the computed results.  After profiling, I think the latter approach is overkill, and with this patch, we basically eliminate the cost of this function from the profile completely.

I got smart and added an optimization to check the next and previous content offsets as well, to make things like caret movement super fast.  Basically with this patch, for each text area, as long as you're moving left or right, we'll do the costly version of the loop only once.

Comment 5

[(no longer active)]

Attachment: Hashtable appropach

Comment 6

[(no longer active)]

Attachment: Patch (v2)

Actually, we need to take the hint into consideration as well, otherwise our cache gives us the wrong results in cases like lines containing bidi text.

Comment 7

[Robert O'Callahan (:roc) (email my personal email if necessary)]

This can lead to the creation of a lot of nsWeakFrames, which is a rather large problem since we do a linear walk of those frames on every frame destruction.

A better approach might be to use an nsIFrame*, set a bit on the textframe when it's in the cache, and in the textframe destructor if the bit is set find the primary frame for the textframe's node and clear the cache.

Comment 8

[(no longer active)]

Attachment: Patch (v3)

Right.  This patch implements the idea in comment 7.

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+  // Whether this frame is cached in the Offset Frame Cache (OffsetToFrameProperty)
+  PRPackedBool mInOffsetCache;

This adds 4-8 bytes to every text frame. We should try to avoid that.

We could use a frame state bit instead, but we've run out of type-specific frame state bits :-(.

Instead we could use another property, one that's set on the frame that's in the cache, and use that property's destructor function to do the work we need to do when the textframe is destroyed.

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

You could add a second set of type-specific frame-state bits at the top of the frame state bit range.

Comment 11

[(no longer active)]

Can't I just add a bit at offset 30 here?

http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsTextFrame.h#65

Comment 12

[Robert O'Callahan (:roc) (email my personal email if necessary)]

No, see nsTextFrameThebes.cpp

Comment 13

[(no longer active)]

But dbaron's suggestion in comment 10 should still work, right?

Comment 14

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Sure

Comment 15

[(no longer active)]

Attachment: Patch (v4)

Using the high word on the frame state bits.

Comment 16

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 462606 [details] [diff] [review]
Patch (v4)

You need to mark in nsIFrame.h which bits are reserved for implementations.

And I'd prefer if you started from the high end (i.e., use 63, and maybe reserve 60-63 for now), since we're already starting to add global bits at the low end.

Comment 17

[(no longer active)]

Attachment: Patch (v5)

Comment 18

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I don't think we need to cache mOffset. The returned offset is always aContentOffset - f->GetContentOffset().

+    // If we can't find the exact offset, try adjacent ones
+    if (offsetToFrame->mContentOffset == aContentOffset - 1) {
+      // We're still lucky, we have a frame cached for the previous offset!
+      f = static_cast<nsTextFrame*>(offsetToFrame->mFrame);
+      offset = aContentOffset - 1;
+    } else if (offsetToFrame->mContentOffset == aContentOffset + 1) {
+      // We're still lucky, we have a frame cached for the next offset!
+      f = static_cast<nsTextFrame*>(offsetToFrame->mFrame);
+      offset = aContentOffset + 1;
+    }

Why are these correct? Instead I think we should be using the cached frame as the start of the search.

But there's something big missing here: we need to invalidate this cache during reflow, the content offsets mapped by text frames can and do change during reflow.

Comment 19

[(no longer active)]

Attachment: Patch (v6)

(In reply to comment #18)
> I don't think we need to cache mOffset. The returned offset is always
> aContentOffset - f->GetContentOffset().

Right, I removed it.

> +    // If we can't find the exact offset, try adjacent ones
> +    if (offsetToFrame->mContentOffset == aContentOffset - 1) {
> +      // We're still lucky, we have a frame cached for the previous offset!
> +      f = static_cast<nsTextFrame*>(offsetToFrame->mFrame);
> +      offset = aContentOffset - 1;
> +    } else if (offsetToFrame->mContentOffset == aContentOffset + 1) {
> +      // We're still lucky, we have a frame cached for the next offset!
> +      f = static_cast<nsTextFrame*>(offsetToFrame->mFrame);
> +      offset = aContentOffset + 1;
> +    }
> 
> Why are these correct? Instead I think we should be using the cached frame as
> the start of the search.

That's exactly what I'm doing!  The search is always started from (f,offset), and I'm modifying those two variables.

> But there's something big missing here: we need to invalidate this cache during
> reflow, the content offsets mapped by text frames can and do change during
> reflow.

This patch does that.

Comment 20

[Robert O'Callahan (:roc) (email my personal email if necessary)]

What if we just cached a single frame pointer, the last frame returned by GetChildFrameContainingOffset? And we just always start our search from there? Then we only need to invalidate the cache when the frame is deleted, and the code is simpler, and the cache is useful even if the requested offset is only "near" the cached frame.

Comment 21

[(no longer active)]

(In reply to comment #20)
> What if we just cached a single frame pointer, the last frame returned by
> GetChildFrameContainingOffset? And we just always start our search from there?

I think that would lead to incorrect results, for example, consider the case where we get a request at offset 100 with hint==right, so we cache the resulting frame (which let's say has mContentOffset==100).  Then, we get a request for offset 10 this time with hint==left, so we start the search forward from the cached frame and we get an exact match here: <http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsTextFrameThebes.cpp#5292> and we return that same frame, whereas the correct answer would be the preceding frame.

> Then we only need to invalidate the cache when the frame is deleted, and the
> code is simpler, and the cache is useful even if the requested offset is only
> "near" the cached frame.

Is the last statement actually true?  I mean, sure, there could be cases where it's true, and there could be cases where it's not.  I don't see why caching the frame that way is "smarter" than the current patch (disregarding the correctness issue).

Comment 22

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #21)
> (In reply to comment #20)
> > What if we just cached a single frame pointer, the last frame returned by
> > GetChildFrameContainingOffset? And we just always start our search from there?
> 
> I think that would lead to incorrect results, for example, consider the case
> where we get a request at offset 100 with hint==right, so we cache the
> resulting frame (which let's say has mContentOffset==100).  Then, we get a
> request for offset 10 this time with hint==left, so we start the search
> forward from the cached frame and we get an exact match here:
> <http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsTextFrameThebes.cpp#5292>
> and we return that same frame, whereas the correct answer would be the
> preceding frame.

You mean a request for offset 100 with hint==left? Yes, that case would need to be fixed. So the loop needs to be fixed to be able to start at an arbitrary frame, but it certainly can be fixed.

> > Then we only need to invalidate the cache when the frame is deleted, and the
> > code is simpler, and the cache is useful even if the requested offset is only
> > "near" the cached frame.
> 
> Is the last statement actually true?  I mean, sure, there could be cases where
> it's true, and there could be cases where it's not.  I don't see why caching
> the frame that way is "smarter" than the current patch (disregarding the
> correctness issue).

In the current patch, if the requested offset is more than 1 character away from the cached offset, you don't get any benefit.

With my proposal, the time is always proportional to the number of frames between the last frame and the result frame. I think that's a good property to have. I think with my proposal the code will be simpler too.

In fact I think your patch doesn't invalidate enough. Invalidating only on reflow isn't enough, we probably need to invalidate on any change to mContentOffset, including in CharacterDataChanged and possibly bidi resolution, and not just on a change to mContentOffset in the cached frame, but also if the mContentOffset of the cached frame's next-continuation changes, because that changes the effective length of the cached frame's text which may mean the cached offset is no longer in the frame.

With my proposal we avoid having to worry about any of that.

Comment 23

[(no longer active)]

OK, I'll give your approach a try and will post a new patch.

Comment 24

[(no longer active)]

Attachment: Patch (v7)

This patch only caches the frame pointer, and starts the search from the last found frame.  If we're at a frame boundary and we have a left hint, it chooses to do a backward search to correctly find the previous frame, if any.

Comment 25

[Robert O'Callahan (:roc) (email my personal email if necessary)]

You can actually now make the property value just *be* the frame pointer. No need to allocate or free memory for the property.

nsTextFrame::ClearFrameOffsetCache doesn't need a parameter, you can always just call GetPrimaryFrame(). That is super fast now.

You don't need to call f->ClearFrameOffsetCache in GetChildFrameContainingOffset. Just clear f's state bit, since we're going to reset the property on the primary frame anyway.

Comment 26

[(no longer active)]

Attachment: Patch (v8)

This should address all of comment 25.

Comment 27

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 463382 [details] [diff] [review]
Patch (v8)

+static void DestroyOffsetToFrameProperty(void* aPropertyValue)
+{
+}
+
+NS_DECLARE_FRAME_PROPERTY(OffsetToFrameProperty, DestroyOffsetToFrameProperty)

Just pass nsnull as the destructor function

+    if (primaryFrame) {
+      primaryFrame->Properties().Delete(OffsetToFrameProperty());
+    }

Just assert primaryFrame is non-null. There must be a primary frame if there is any frame, which there clearly is if we get here...

nsTextFrame::GetChildFrameContainingOffset should assert that it's the primary frame.

This is lovely and simple now :-).

Comment 28

[(no longer active)]

Attachment: Patch (v9)

With comment 27 addressed.

Comment 29

[Boris Zbarsky [:bzbarsky]]

This is crashing on tinderbox with a stack like so:

 0  libxul.so!nsTextFrame::ClearFrameOffsetCache [FramePropertyTable.h : 251 + 0x9]
 1  0xa5d108ef
 2  libxul.so!nsContinuingTextFrame::DestroyFrom [nsTextFrameThebes.cpp:56649f2fbcdf : 3618 + 0x5]
 3  libxul.so!nsLineBox::DeleteLineList [nsLineBox.cpp:56649f2fbcdf : 336 + 0x6]

In particular, nsLineBox just deletes the frames in it, in order.  So it will generally delete the primary frame before the continuations, and the assertion in ClearFrameOffsetCache will fail.

We should either not call ClearFrameOffsetCache when aDestructRoot != this or convert the assert in ClearFrameOffsetCache into a test.  Or possibly both...

Comment 30

[(no longer active)]

http://hg.mozilla.org/mozilla-central/rev/8f8ee0543d0f

bustage fix pushed as:

http://hg.mozilla.org/mozilla-central/rev/300036f6c90f

Comment 31

[Dave Townsend [:mossop]]

Backed this and the bustage fix out due to test failures on windows 2003 debug builds

http://hg.mozilla.org/mozilla-central/rev/312fdcee7e50
http://hg.mozilla.org/mozilla-central/rev/87be0d140fd6

Comment 32

[(no longer active)]

Attachment: Patch (v10)

So, the assumption that |this == mContent->GetPrimaryFrame()| isn't apparently always true, at least from this call site: <http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsSelection.cpp#5493>, which is what was causing TestWinTSF to fail.

This patch removes that assertion.

Comment 33

[Robert O'Callahan (:roc) (email my personal email if necessary)]

If that assertion's not true, then calling  Properties().Get(OffsetToFrameProperty()) isn't going to get anything useful, and setting the property on 'this' is going to set it somewhere that won't get cleared later.

We need to ensure that assertion always holds, by fixing callers or by having GetChildFrameContainingOffset itself ensure it by re-calling itself on the primary frame if necessary.

Comment 34

[(no longer active)]

Attachment: Patch (v1)

(In reply to comment #33)
> We need to ensure that assertion always holds, by fixing callers or by having
> GetChildFrameContainingOffset itself ensure it by re-calling itself on the
> primary frame if necessary.

I think the latter makes sense.

Comment 35

[(no longer active)]

Do I need to ask for approval on this patch again?

Comment 36

[Robert O'Callahan (:roc) (email my personal email if necessary)]

No

Comment 37

[(no longer active)]

http://hg.mozilla.org/mozilla-central/rev/97dcac024d4f