349206 - Consider some sort of locality cache for nsBlockFrame::FindLineFor

Status: NEW

(Core :: Layout, defect)

Description

[Boris Zbarsky [:bzbarsky]]

On the reflow branch, nsBlockFrame::FindLineFor is used in the following cases:

1) Computing the hypothetical box of an abs pos frame (find the line for the
   placeholder).
2) Marking a line dirty if a frame returns NS_FRAME_REFLOW_NEXTINFLOW.
3) Marking a line dirty if a descendant of the block becomes dirty.

I don't know much about #2, but generally speaking for #1 we would call FindLineFor() for several placeholders, in content order.  For #3, in full generality there is no locality of refence, but in practice I would think there often is if many changes happen in a row -- those tend to happen in content order (e.g. the alt text stuff in bug 64858).

So I was wondering whether we could cache the last-found line (and frame in that line?) in a useful way.  The hard part, of course, is figuring out when to invalidate the cache and how to best do it (e.g. if we delete a linebox, should we move the cache to the next line, or just mark it invalid?).

Thoughts?

Comment 1

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

We already have a cached line cursor for painting and hit detection. Either we can reuse that, or we can cache two cursors and update them both at the same time ... given that the first cursor already exists, invalidation should be already solved.

Comment 2

[Boris Zbarsky [:bzbarsky]]

The problem is that we blow away the existing line cursor on any child list change; since it's only needed for painting and hit detection, we don't need to worry about updating it during a bunch of DOM changes -- we just invlidate it and then recover it when the JS stops messing with the DOM.  Unfortunately, we call FindLineFor during frame construction on reflow branch (whenever we add or remove a descendant of a block), so if there are a bunch of document mutations in a row we'd have a good chance of blowing away the cursor a lot exactly when we want to be using it.

Comment 3

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

Also that cursor really has different semantics from the cursor you want here; the existing line cursor only exists if the line boxes' y-coordinates are non-decreasing.

How is your proposed line box cache going to work? If we cache a line box pointer, and we are given a frame we want to find the line box for, do we start the line search at the cached line box and move forward?

We'd have to be careful with this. In principle adding checks at each modification of the block's main line list would be OK, but in some places we cut the line list and push the second group of lines onto the overflow list. I suppose in that case you could just invalidate the cached line box unconditionally.

Comment 4

[Boris Zbarsky [:bzbarsky]]

> do we start the line search at the cached line box and move forward?

That's what I was thinking, yes.

> I suppose in that case you could just invalidate the cached line box
> unconditionally.

Yeah.  I don't expect this to happen much for blocks that on the one hand have tens of thousands of lines and on the other hand are having dynamic stuff happening to them.

Comment 5

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

In that case, go for it :-)