Optimize SVGTextQuery's character offset ligature adjustment query

Optimize SVGTextQuery's character offset ligature adjustment query

For queries that take a code unit to compute some property for (basically
all *OfChar calls), the <start, end> range is mapped to the closest
glyph-boundary to allow queries within ligatures.
This adjustment step is O(N), N=number of glyphs within a text node, and
is performed for each fragment within a text box.
This means that for text boxes with a large number of fragments - and,
consequently, a large number of glyphs - there'll be O(N^2) behavior.
Since the <start, end> range is invariant for most queries, it should
suffice to compute the adjusted range once per text node [1].
The easiest way to achieve this is by adding a simple cache and reuse the
result of an adjustment query (for every fragment in a text box.)

This improves the runtime of the test in the bug from ~13s to ~120ms (or
approximately a factor 100) locally.

[1] This CL however only perform caching per text box in order to minimize
modifications to the actual adjustment code.

BUG=267504
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=176937

[fs, 2014-06-23 14:42:12]

(The getCharNumAtPosition() code-path is still appalling, and isn't helped by
this cache at all. It's probably better to rewrite that one though to not use
the mapStartEndPositionsIntoFragmentCoordinates method at all, and just walk the
metrics vector directly. Needs TC though.)

[pdr., 2014-06-24 21:18:48]

https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
File Source/core/rendering/svg/SVGTextQuery.cpp (right):

https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGTextQuery.cpp:57: // Invalidate the
ligature-adjustment cache.
Is it possible to invalidate the cache when it really becomes invalid (when
start/end Position or processedCharacters changes) instead of doing it
explicitly here?

https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGTextQuery.cpp:66: // Ligature adjustment cache.
The cache key is pretty much {startPosition, processedCharacters} so I think it
would be better to put this on SVGTextQuery instead of Data.

https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGTextQuery.cpp:168:
modifyStartEndPositionsRespectingLigaturesCached(queryData, startPosition,
endPosition);
This name was confusing until I read the implementation, since I wasn't sure
when one would call x() vs xCached(). Since this is the only caller, can you
move the cache logic into the top of modifyStartEndPositionsRespectingLigatures?

[fs, 2014-06-25 10:29:50]

https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
File Source/core/rendering/svg/SVGTextQuery.cpp (right):

https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGTextQuery.cpp:57: // Invalidate the
ligature-adjustment cache.
On 2014/06/24 21:18:48, pdr wrote:
> Is it possible to invalidate the cache when it really becomes invalid (when
> start/end Position or processedCharacters changes) instead of doing it
> explicitly here?

That pretty much what it does ATM - in the loop in executeQuery(),
processedCharacters is set at the end up the loop-body, and this is performed at
the start of the loop-body. Start/end positions will be invariant in the cases
where this matter - _except_ the positions queried are first adjusted by
processedCharacters (i.e. they're dependent.)

https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGTextQuery.cpp:66: // Ligature adjustment cache.
On 2014/06/24 21:18:48, pdr wrote:
> The cache key is pretty much {startPosition, processedCharacters} so I think
it
> would be better to put this on SVGTextQuery instead of Data.

I suppose there could be some merit to that... To me it seems though that
keeping it as Data would enable further changes that would better clarify which
state is required by which query (not all queries use this cache after all). As
an example we might have "CharacterRangeQueryData" (derived from Data), that
contains "position", "length" and the cache/state used for adjustment.
Somewhat on a tangent, but it also feels a bit wrong to add additional state to
something that only has redundant state ATM (getting rid of m_textBoxes ought to
be trivial) =). An on the same note, it seems kind of redundant with all the
"double this" going on (since SVGTextQuery is stateless, and Data is what's
actually used).

But, if none of the above tickles your fancy I can move the cache state.

https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGTextQuery.cpp:168:
modifyStartEndPositionsRespectingLigaturesCached(queryData, startPosition,
endPosition);
On 2014/06/24 21:18:48, pdr wrote:
> This name was confusing until I read the implementation, since I wasn't sure
> when one would call x() vs xCached(). Since this is the only caller, can you
> move the cache logic into the top of
modifyStartEndPositionsRespectingLigatures?

Although it didn't like having the additional indirection, I felt that it
"packaged" the relevant bits in a good way (and allowed me to not worry about
multiple exit-points). Will fold as requested though.

[pdr., 2014-06-25 16:05:09]

On 2014/06/25 10:29:50, fs wrote:
>
https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
> File Source/core/rendering/svg/SVGTextQuery.cpp (right):
> 
>
https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
> Source/core/rendering/svg/SVGTextQuery.cpp:57: // Invalidate the
> ligature-adjustment cache.
> On 2014/06/24 21:18:48, pdr wrote:
> > Is it possible to invalidate the cache when it really becomes invalid (when
> > start/end Position or processedCharacters changes) instead of doing it
> > explicitly here?
> 
> That pretty much what it does ATM - in the loop in executeQuery(),
> processedCharacters is set at the end up the loop-body, and this is performed
at
> the start of the loop-body. Start/end positions will be invariant in the cases
> where this matter - _except_ the positions queried are first adjusted by
> processedCharacters (i.e. they're dependent.)
> 
>
https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
> Source/core/rendering/svg/SVGTextQuery.cpp:66: // Ligature adjustment cache.
> On 2014/06/24 21:18:48, pdr wrote:
> > The cache key is pretty much {startPosition, processedCharacters} so I think
> it
> > would be better to put this on SVGTextQuery instead of Data.
> 
> I suppose there could be some merit to that... To me it seems though that
> keeping it as Data would enable further changes that would better clarify
which
> state is required by which query (not all queries use this cache after all).
As
> an example we might have "CharacterRangeQueryData" (derived from Data), that
> contains "position", "length" and the cache/state used for adjustment.
> Somewhat on a tangent, but it also feels a bit wrong to add additional state
to
> something that only has redundant state ATM (getting rid of m_textBoxes ought
to
> be trivial) =). An on the same note, it seems kind of redundant with all the
> "double this" going on (since SVGTextQuery is stateless, and Data is what's
> actually used).
> 
> But, if none of the above tickles your fancy I can move the cache state.
> 
>
https://codereview.chromium.org/349223003/diff/1/Source/core/rendering/svg/SV...
> Source/core/rendering/svg/SVGTextQuery.cpp:168:
> modifyStartEndPositionsRespectingLigaturesCached(queryData, startPosition,
> endPosition);
> On 2014/06/24 21:18:48, pdr wrote:
> > This name was confusing until I read the implementation, since I wasn't sure
> > when one would call x() vs xCached(). Since this is the only caller, can you
> > move the cache logic into the top of
> modifyStartEndPositionsRespectingLigatures?
> 
> Although it didn't like having the additional indirection, I felt that it
> "packaged" the relevant bits in a good way (and allowed me to not worry about
> multiple exit-points). Will fold as requested though.


LGTM!

[fs, 2014-06-25 17:06:14]

The CQ bit was checked by fs@opera.com

[commit-bot: I haz the power, 2014-06-25 17:06:27]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/fs@opera.com/349223003/40001

[commit-bot: I haz the power, 2014-06-25 17:09:11]

Change committed as 176937