Last Comment Bug 96041 - Left or right pixels of 'F' 'J' 'M' 'W' characters overflow and lack hover color (bounding box / font metrics problem)
: Left or right pixels of 'F' 'J' 'M' 'W' characters overflow and lack hover co...
Status: RESOLVED FIXED
[CSS1-2.1]
: css1, testcase
Product: Core Graveyard
Classification: Graveyard
Component: GFX (show other bugs)
: Trunk
: All All
: P2 normal with 1 vote (vote)
: mozilla1.9beta1
Assigned To: Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
: Hixie (not reading bugmail)
Mentors:
http://jsoft.zabia.net/reblogger.php
: 197129 207926 261915 280621 317974 (view as bug list)
Depends on: 15116 333659 397734 398613 402338 410331
Blocks: 79732 236277 294733 324857 382664 397514
  Show dependency treegraph
 
Reported: 2001-08-20 01:46 PDT by Jesse Ruderman
Modified: 2009-01-22 10:17 PST (History)
33 users (show)
vladimir: blocking1.9+
reed: wanted1.9+
shaver: blocking1.8.1-
See Also:
QA Whiteboard:
Iteration: ---
Points: ---


Attachments
testcase (669 bytes, text/html)
2001-08-20 01:47 PDT, Jesse Ruderman
no flags Details
more obvious testcase (691 bytes, text/html)
2001-08-20 03:04 PDT, Alexey Chernyak
no flags Details
a testcase with a hint (715 bytes, text/html)
2002-05-13 08:17 PDT, Jaagup Irve
no flags Details
an other testcase with letter 'f' (715 bytes, text/html)
2002-12-04 10:12 PST, Alexander Weber
no flags Details
work in progress (64.78 KB, patch)
2007-05-28 21:02 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
no flags Details | Diff | Splinter Review
updated patch (61 bytes, patch)
2007-07-15 21:39 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
no flags Details | Diff | Splinter Review
real patch (66.74 KB, patch)
2007-07-16 20:50 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
no flags Details | Diff | Splinter Review
patch with Pango/Windows changes (59.31 KB, patch)
2007-07-18 16:19 PDT, Karl Tomlinson (:karlt)
no flags Details | Diff | Splinter Review
Updated patch (56.75 KB, patch)
2007-08-09 17:05 PDT, YAMASHITA Makoto
no flags Details | Diff | Splinter Review
updated patch (73.06 KB, patch)
2007-08-16 14:52 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
no flags Details | Diff | Splinter Review
alternative patch that enables accurate glyph bounds only when the textrun is in "quality" mode (86.92 KB, patch)
2007-08-17 16:06 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
no flags Details | Diff | Splinter Review
updated patch with a NeedsGlyphExtents abstraction (87.03 KB, patch)
2007-08-17 16:51 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
no flags Details | Diff | Splinter Review
updated patch (80.33 KB, patch)
2007-08-26 20:44 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
no flags Details | Diff | Splinter Review
Tp results (8.12 KB, text/plain)
2007-08-26 20:46 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
no flags Details
updated patch v2 (89.11 KB, patch)
2007-08-27 15:03 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
vladimir: review+
Details | Diff | Splinter Review
better results (8.12 KB, patch)
2007-08-27 17:13 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
no flags Details | Diff | Splinter Review
updated patch v3 (90.06 KB, patch)
2007-08-28 20:34 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
no flags Details | Diff | Splinter Review
updated patch v4 (92.94 KB, patch)
2007-09-16 21:32 PDT, Karl Tomlinson (:karlt)
no flags Details | Diff | Splinter Review
updated patch v5 (92.76 KB, patch)
2007-09-17 16:03 PDT, Karl Tomlinson (:karlt)
no flags Details | Diff | Splinter Review
updated patch v6 (92.90 KB, patch)
2007-09-20 21:49 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
dbaron: review+
dbaron: superreview+
Details | Diff | Splinter Review
updated patch v7 (124.18 KB, patch)
2007-09-23 17:06 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
dbaron: review+
dbaron: superreview+
Details | Diff | Splinter Review
Analysis (11.84 KB, text/plain)
2007-09-26 20:31 PDT, Robert O'Callahan (:roc) (Exited; email my personal email if necessary)
no flags Details

Description Jesse Ruderman 2001-08-20 01:46:54 PDT
The few pixels of a 'j' or 'J' at the beginning of a link don't change color on 
highlight.  The number of pixels varies from 0 to about 3, depending on 
capitalization, font face, and whether the text is italicized.
Comment 1 Jesse Ruderman 2001-08-20 01:47:14 PDT
Created attachment 46409 [details]
testcase
Comment 2 Christopher Aillon (sabbatical, not receiving bugmail) 2001-08-20 02:14:04 PDT
I see this on linux.  OS->All
Comment 3 Christopher Aillon (sabbatical, not receiving bugmail) 2001-08-20 02:28:20 PDT
On the URL, I also see this on the 'M' of the Jesse Malone link (bottom right)
Comment 4 Alexey Chernyak 2001-08-20 03:04:22 PDT
Created attachment 46411 [details]
more obvious testcase
Comment 5 Kevin McCluskey (gone) 2002-02-22 07:22:24 PST
Bulk moving Mozilla1.01 bugs to future-P1. I will pull from the future-P1 list
to schedule bugs for post Mozilla1.0 milestones
Comment 6 Jaagup Irve 2002-05-13 08:17:45 PDT
Created attachment 83343 [details]
a testcase with a hint

It seems that part of the letter escapes the bounding box...
Comment 7 Alexander Weber 2002-12-04 10:12:37 PST
Created attachment 108229 [details]
an other testcase with letter 'f'

The same happens with the rightmost pixel(s) at the end of a link with the
letter 'f' or 'F'.
Comment 8 Simon Montagu :smontagu 2003-06-03 13:27:05 PDT
*** Bug 207926 has been marked as a duplicate of this bug. ***
Comment 9 Simon Montagu :smontagu 2004-09-30 03:22:05 PDT
*** Bug 261915 has been marked as a duplicate of this bug. ***
Comment 10 Simon Montagu :smontagu 2004-09-30 03:29:14 PDT
This may itself be a duplicate of bug 15116
Comment 11 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2004-10-01 13:24:20 PDT
When text frames have overflowing text they probably need to set their
mCombinedArea / overflow area during reflow.
Comment 12 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2004-10-01 13:28:28 PDT
I don't know anything about our font APIs. rbs, do the MathML bounding metrics
give us what we want here?
Comment 13 rbs 2004-10-03 23:53:30 PDT
Yes, that info is contained in the MathML bounding metrics:
- the so-called .leftBearing tells how far the text protrudes on the left;
- the so-called .rightBearing tells how far the text protrudes on the right.
However, as they come at a sizeable extra cost, I feel that they are overkill
for widespread use in all textframes. 

---
I am under the impression that IE uses a very simple mechanism:

- if the containing block is positionned, then they clip its area from the
start. (That is, the text will never protrude outside. So bug 79732 doesn't
happen because the descender of j is cut right from the start.) The problem in
Gecko here seems to be that the containing block is not clipped (see screenshots
bug 79732).

- if the containing block is not positionned, then they don't clip its area. The
text can protrude, and likewise when the damage area is re-painted, the bits of
text that stick outside are repainted (i.e., DrawString overflows, but who
cares). The problem in Gecko here seems to be that the damage area gets
explicitly clipped, and so the overflow of DrawString are cut out.
Comment 14 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2004-10-04 05:47:24 PDT
It sounds like what IE does is convenient but isn't really correct.

> I feel that they are overkill for widespread use in all textframes.

Is there a way we can make it fast? Even via some ugly hack like special-casing
ASCII characters that we know "should not" overflow in non-oblique text?
Comment 15 rbs 2004-10-04 11:33:55 PDT
> It sounds like what IE does is convenient but isn't really correct.

Notice however that Gecko is not consistent with the second case (this bug). At
the first paint, DrawString is allowed to protrude. But at the next repaint, it
is prevented from protruding (due to the clipping). And that's why the bits that
stick outside go out-of-sync and look outdated.

Also note that in the first case (bug 79732), it may be that an explicit
clipping is only needed when painting the foreground text layer, thus mostly
affecting DrawString only.

> Is there a way we can make it fast?

Sure there could be a special-casing or something (e.g., a crude estimate that
doesn't involve a GDI call/measurement). But...
Comment 16 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2004-10-04 11:49:27 PDT
> Notice however that Gecko is not consistent with the second case (this bug).

I realize that what we're currently doing is wrong. But if we accurately
computed the overflow for text frames then everything should work as you'd expect.

>> Is there a way we can make it fast?
>
> Sure there could be a special-casing or something (e.g., a crude estimate that
> doesn't involve a GDI call/measurement). But...

It seems to me that only additional work required is to measure the left bearing
on the first character of the string and the right bearing on the last character
of the string. Would it still be expensive to get just those from GDI?

And it may sound ridiculous but I bet we could get a decent speedup by
identifying characters that never have left or right bearing in any
quasi-reasonable font.
Comment 17 rbs 2004-10-04 12:42:09 PDT
Two GDI calls (for the left and right) will be needed to get all the info. The
actual GDI function returns a struct with other data such as the width --
necessary to infer the overflow of the string: rbearing_string = width_string -
width_lastchar + rbearing_lastchar. GetBoundingMetrics will expose the info in a
unified way that hides the coordinate system that varies per platform. Hence no
further action is needed here. It already has a fast path for a single char
since this was a common case in MathML.

An extra perf might indeed be to skip characters that can't protrude (such as
'r', 's', ... as I type this, I wonder if they really can't protrude in all
possible fonts?!?).

I am not sure precisely what the extra cost of all this will be. I guess it can
be tried (shouldn't be hard to implement, except that those platforms that still
don't have GetBoundMetrics will miss out...). I understand that this fits nicely
with the current way that overflows are handled and that you prefer this route.
If the perf degenerates badly or storing the overflow areas creates much
overhead in memory, then we can revisit the other approaches that I mentioned.
Comment 18 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2004-10-04 12:55:15 PDT
> An extra perf might indeed be to skip characters that can't protrude (such as
> 'r', 's', ... as I type this, I wonder if they really can't protrude in all
> possible fonts?!?)

Yeah :-). Someone with a really big font collection could probably do an
experiment to figure out which characters satisfy.

By "not correct" I mean
> - if the containing block is positionned, then they clip its area from the
> start.
A relatively positioned inline span with an offset of 0,0 should look identical
to if it didn't have relative positioning. Period.
Comment 19 rbs 2004-10-05 15:45:20 PDT
Also note that even Opera does that clipping (bug 79732 comment 31). I
understand that Gecko's overflowing handling together with the
GetBoundingMetrics can fit the bill nicely. So until we see the perf hit,
considering such a clipping (or other trickeries with 'r', 's', etc) is
premature optimization however.
Comment 20 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2004-12-30 20:37:58 PST
*** Bug 197129 has been marked as a duplicate of this bug. ***
Comment 21 José Jeria 2005-02-01 02:34:09 PST
*** Bug 280621 has been marked as a duplicate of this bug. ***
Comment 22 Wayne Woods 2006-03-19 20:34:02 PST
I hope the changed bug summary reflects the more general nature of this bug.

This isn't really an obvious bug in Firefox, and as a result probably hasn't been treated with much concern. But it really stands out in Thunderbird mail composition, where backspacing over / deleting an f (in Times font, which is default) often leaves remnants of the characters in the composition window (similar to bug 197129 reported for Composer). While it's obviously not serious, turds like that can give an average user the (false) impression that the product is cheap or buggy.

It'd be nice if at least a temporary patch could be put in before Thunderbird 2 was released, or soon thereafter.
Comment 23 Tim Powell 2006-03-21 11:00:49 PST
I believe this is most frequently noticed with hover coloring in Firefox. The summary change will likely lead to more duplicates. However, the old summary was also somewhat misleading as characters could overflow on either the right or left. After looking at the dupe summaries and these, I've combined them with more keywords to hopefully make this easier to find.
 
Comment 24 Mike Shaver (:shaver -- probably not reading bugmail closely) 2006-04-18 10:34:24 PDT
Would require too invasive a change for 1.8.1.
Comment 25 Mike Cowperthwaite 2006-06-19 08:13:12 PDT
*** Bug 317974 has been marked as a duplicate of this bug. ***
Comment 26 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-05-28 19:35:43 PDT
We need to compute accurate glyph bounds so we get the right overflow area for text frames whose glyphs overflow the font box. For fancy fonts such as Zapfino this is essential for dynamic effects to work right.

The new textframe knows how to do this. We need to fix gfxTextRun to get the glyph metrics. The tricky part is doing it without regressing performance. See
http://weblogs.mozillazine.org/roc/archives/2007/05/the_glyph_bound.html
Comment 27 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-05-28 21:02:22 PDT
Created attachment 266438 [details] [diff] [review]
work in progress

This should work on all platforms but I've only tested it on Mac. It requires new-textframe. I don't plan to finish and land this until new textframe has landed.

The main idea is to aggressively cache glyph extents on gfxFonts. We take advantage of a common case: the glyph lies within the ascent and descent of the font, and has no before-bearing, and tight glyph bounds are not required (since we're going to take the union of the glyph extents and the font-box anyway). In this case we need only store the offset to the glyph's right edge. We can commonly do this in 16 bits. So we use an array of PRUint16s indexed by glyph ID, with a backup of a hashtable mapping glyph IDs to full extent rects.

Because we are doing our own glyph extents caching this way, we avoid entering cairo at all for glyph extents on Mac. We just get them directly from ATSUI.

The extents cache depends on the appUnitsToDevUnits ratio, since the glyph widths may be fractional and we're actually rounding them to appunits. Since fonts don't know the appunitstodevunits ratio, we have to handle multiple extents caches per gfxFont. It would be nice to find a way to avoid this.

I've measured the performance on Mac and observed no significant performance impact over 40 runs of Tp2.

TODO:
-- use ceil() when we convert glyph widths to appunits
-- check RTL situations
-- get this working on Windows and Linux, with performance testing for those platforms
Comment 28 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-07-15 21:39:05 PDT
Created attachment 272445 [details] [diff] [review]
updated patch

Okay, this patch is updated to trunk. There is cairo-based code that should work on Windows, Linux and anywhere else --- although performance may suck. In fact, since GetGlyphOutline is said to suck badly, I'm pretty sure this will be a performance problem on Windows. Not sure of the best way to address that. Anyway, this seems to work with RTL, and I've added the NS_ceil I mentioned in the previous comment.

What I'd like to do now is get someone to profile Windows and Linux and we'll see what the perf impact is. One option would be to hardcode particular common font names where we know no glyphs overflow font boxes. Another option would be to depend on the text-rendering CSS property and lie about the glyph bounds when that is optimizing for speed.

Actually I think I'll test Linux performance right now...
Comment 29 Vladimir Vukicevic [:vlad] [:vladv] 2007-07-16 20:15:23 PDT
Your patch is 61 bytes :)
Comment 30 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-07-16 20:50:03 PDT
Created attachment 272586 [details] [diff] [review]
real patch

Sorry about that.
Comment 31 Karl Tomlinson (:karlt) 2007-07-18 16:19:57 PDT
Created attachment 272882 [details] [diff] [review]
patch with Pango/Windows changes

Added FetchGlyphExtents calls to Pango and Windows (in addition to Atsui) to set up GlyphExtents objects with cairo-based code.  Tested successfully on Linux/Pango.
Comment 32 Karl Tomlinson (:karlt) 2007-07-18 19:42:36 PDT
Measured mean effect on Linux Tp2 page load time:     1.3%
95% confidence interval:                         -0.3 to 2.8%

Obtained from 50 cycles of the 40 Tp2 pages.

                  mean   stderr
20070716 trunk:   137.7   0.5
with patch:       139.4   0.6
Comment 33 YAMASHITA Makoto 2007-08-07 01:52:51 PDT
Karl's patch has become old and won't apply to the current tree.  An updated patch (with other mathml fixes) is posted on bug 324857.  If you need a stripped-off version for this bug alone, please let me know.
Comment 34 Vladimir Vukicevic [:vlad] [:vladv] 2007-08-07 16:39:44 PDT
Marking blocking since it's blocking other things (:first-letter, etc.)
Comment 35 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-07 20:37:51 PDT
Yamashita-san, please attach your updated patch (with the MathML stuff removed). THanks!
Comment 36 YAMASHITA Makoto 2007-08-09 17:05:14 PDT
Created attachment 276046 [details] [diff] [review]
Updated patch
Comment 37 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-10 02:19:25 PDT
Tempting as it is, I can't review my own code. I need someone who can produce trustworthy Windows performance numbers to get some for this patch.
Comment 38 Vladimir Vukicevic [:vlad] [:vladv] 2007-08-10 10:10:05 PDT
I can do that; will do so either later today or monday.
Comment 39 Vladimir Vukicevic [:vlad] [:vladv] 2007-08-10 15:49:28 PDT
On windows... not sure how to fix this in a straightforward way; basically nsAutoTArray<nsAutoPtr<gfxGlyphExtents>,1> is causing the problem.

c:\proj\mozilla-cvs\firefox-opt\dist\include\xpcom\nsTArray.h(194) : error C2558: class 'nsAutoPtr<T>' : no copy constructor available or copy constructor is declared 'explicit'
        with
        [
            T=gfxGlyphExtents
        ]
        c:\proj\mozilla-cvs\firefox-opt\dist\include\xpcom\nsTArray.h(712) : see reference to function template instantiation 'void nsTArrayElementTraits<E>::Construct<Item>(E *,const A &)' being compiled
        with
        [
            E=nsAutoPtr<gfxGlyphExtents>,
            Item=nsAutoPtr<gfxGlyphExtents>,
            A=nsAutoPtr<gfxGlyphExtents>
        ]
        c:\proj\mozilla-cvs\firefox-opt\dist\include\xpcom\nsTArray.h(446) : see reference to function template instantiation 'void nsTArray<E>::AssignRange<Item>(nsTArray_base::index_type,nsTArray_base::size_type,const Item *)' being compiled
        with
        [
            E=nsAutoPtr<gfxGlyphExtents>,
            Item=nsAutoPtr<gfxGlyphExtents>
        ]
        c:\proj\mozilla-cvs\firefox-opt\dist\include\xpcom\nsTArray.h(291) : see reference to function template instantiation 'nsAutoPtr<T> *nsTArray<E>::ReplaceElementsAt<nsAutoPtr<T>>(nsTArray_base::index_type,nsTArray_base::size_type,const Item *,nsTArray_base::size_type)' being compiled
        with
        [
            T=gfxGlyphExtents,
            E=nsAutoPtr<gfxGlyphExtents>,
            Item=nsAutoPtr<gfxGlyphExtents>
        ]
        c:\proj\mozilla-cvs\firefox-opt\dist\include\xpcom\nsTArray.h(290) : while compiling class template member function 'nsTArray<E> &nsTArray<E>::operator =(const nsTArray<E> &)'
        with
        [
            E=nsAutoPtr<gfxGlyphExtents>
        ]
        c:\proj\mozilla-cvs\firefox-opt\dist\include\xpcom\nsTArray.h(718) : see reference to class template instantiation 'nsTArray<E>' being compiled
        with
        [
            E=nsAutoPtr<gfxGlyphExtents>
        ]
        c:\proj\mozilla-cvs\firefox-opt\dist\include\thebes\gfxFont.h(509) : see reference to class template instantiation 'nsAutoTArray<E,N>' being compiled
        with
        [
            E=nsAutoPtr<gfxGlyphExtents>,
            N=1
        ]
Comment 40 Vladimir Vukicevic [:vlad] [:vladv] 2007-08-10 16:39:29 PDT
Tried:
   - using nsTArray instead of nsAutoTArray
   - using nsTArray<gfxGlyphExtents,1> (which worked, as far as that goes, but the rest of the code didn't)
   - adding a template<typename T> nsTArrayElementTraits<nsAutoPtr<T> > specialization with an undefined Construct() variant that used the copy constructor; this didn't work -- that version of Construct is called (failed at link time)
   - adding a template<typename T> nsTArrayElementTraits<nsAutoPtr<T> > that implemented the copying-construct by allocating a new T and copying the old pointed-to- thing there.  This compiled in gfx, but failed in layout/generic due to some odd nsTHashtable error.

Also, nsTextFrameBase.h was missing from the latest patch; it also needs an updated license block (e.g. it says 1998 in there or whatever).
Comment 41 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-16 14:52:26 PDT
Created attachment 277014 [details] [diff] [review]
updated patch

This updates to trunk (fixing some conflicts) and fixes the Windows build issues. It also includes nsTextFrameBase which was missing from the previous patch. It works just fine on Windows, although performance is still a big question...
Comment 42 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-17 16:06:15 PDT
Created attachment 277174 [details] [diff] [review]
alternative patch that enables accurate glyph bounds only when the textrun is in "quality" mode
Comment 43 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-17 16:51:24 PDT
Created attachment 277179 [details] [diff] [review]
updated patch with a NeedsGlyphExtents abstraction
Comment 44 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-26 20:44:49 PDT
Created attachment 278363 [details] [diff] [review]
updated patch

okay, this patch is based on 277179 and adds a fix in cairo for Windows bitmap fonts; GetGlyphBounds only works for Truetype fonts so for non-Truetype fonts we just assume that glyphs have no left bearing or right bearing, and vertically the bounds are the font ascent and descent.

I profiled this carefully on Windows and see no significant performance impact over 40 cycles of Tp.
Comment 45 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-26 20:46:43 PDT
Created attachment 278364 [details]
Tp results

These are the before and after Tp results I got.
Comment 46 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-26 20:47:31 PDT
Comment on attachment 278363 [details] [diff] [review]
updated patch

I think we should go for this now.
Comment 47 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-26 22:35:07 PDT
Comment on attachment 278363 [details] [diff] [review]
updated patch

oops, there's a bug with MakeSpaceTextRun, we're not setting up glyph extents for the space in some cases.
Comment 48 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-26 22:36:30 PDT
Also IIRC Stuart requested that we pass around gfxContext* instead of cairo_t*. I'll do that.
Comment 49 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-27 15:03:10 PDT
Created attachment 278456 [details] [diff] [review]
updated patch v2

Okay, this is updated with a fix for the space-glyph problem and the changes that Stuart wanted, we don't pass around cairo_ts anymore.
Comment 50 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-27 15:08:36 PDT
Comment on attachment 278456 [details] [diff] [review]
updated patch v2

The layout changes need review from dbaron. These changes are to properly recompute the overflow rect for text frames when justification has alters the positions of glyphs.
Comment 51 Vladimir Vukicevic [:vlad] [:vladv] 2007-08-27 16:01:26 PDT
Comment on attachment 278456 [details] [diff] [review]
updated patch v2

Looks ok to me.  We need to get our win32 font changes upstream into cairo, though; there's some others as well.
Comment 52 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-27 17:13:43 PDT
Created attachment 278495 [details] [diff] [review]
better results

These numbers seem more accurate. The results for the as-is patch seem to show a 0-2% slowdown on most pages, with some outliers that are likely as not just noise. Turning on NeedsGlyphBounds for all text adds an additional very slight slowdown, except for hotwired.lycos.com which shows a significant jump as we saw before. Not sure what's going on there, possibly we're getting an overflow rect added which is causing extra repainting or something.

I'll add an extra optimization to FetchGlyphExtents to see if that helps the default "disable bounds on fast path" case.
Comment 53 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-28 20:34:35 PDT
Created attachment 278709 [details] [diff] [review]
updated patch v3

This is a slightly improved patch with an additional optimization to MeasureText so that we don't get/create a gfxGlyphExtents if it's not going to be needed. This  doesn't have any noticeable impact on the results though.
Comment 54 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-08-28 20:39:19 PDT
I profiled the Tp2 hotwired.lycos.com page, 100 cycles alternating with about:blank, with VTune. With patch v3, it doesn't show any of the new functions in the patch showing up in any way. And in fact there is no difference in the before-patch and after-patch results for the page when I test it this way.

I've run out of ideas for now; I think we should just land it.
Comment 55 Karl Tomlinson (:karlt) 2007-09-16 21:32:10 PDT
Created attachment 281145 [details] [diff] [review]
updated patch v4

Updated to trunk (-NS_STATIC_CAST-).
Included nsTextFrameBase.h from attachment in comment #44.

I'm a bit concerned that the #ifdef DEBUG in nsLineLayout::RelativePositionFrames may one day end up causing different behaviour for debug versions.
Comment 56 Karl Tomlinson (:karlt) 2007-09-17 16:03:44 PDT
Created attachment 281245 [details] [diff] [review]
updated patch v5

removed #ifdef DEBUG section in nsLineLayout::RelativePositionFrames.
Comment 57 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-17 17:15:35 PDT
Comment on attachment 281245 [details] [diff] [review]
updated patch v5

Updated patch ... still need dbaron review on the non-gfx bits
Comment 58 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2007-09-20 17:41:04 PDT
Why do we want nsTextFrameBase and the ensuing virtual functions?

In nsCanvasRenderingContext2D.cpp, it seems like you may as well fix the indentation of both of the lines that you're changing, rather than just one.

Why does nsTextFrame::HitTest use nsSize(0, 0)?  That seems like it would make it always return null.

mTextRun->MeasureText is returning a cached result in RecomputeOverflowRect, right?

I don't think that long list of people contributed to nsTextFrameBase.

You might want a blank line to separate these comments:
   // XXX what about adjusting bounding metrics?
+  // probably should not measure text in ::Reflow, but wait for
+  // RecomputeOverflowRect to be called
Comment 59 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-20 21:32:53 PDT
(In reply to comment #58)
> Why do we want nsTextFrameBase and the ensuing virtual functions?

So nsLineLayout can call RecomputeOverflowRect.

> In nsCanvasRenderingContext2D.cpp, it seems like you may as well fix the
> indentation of both of the lines that you're changing, rather than just one.

OK

> Why does nsTextFrame::HitTest use nsSize(0, 0)?  That seems like it would make
> it always return null.

Er, yeah. I don't know what I was thinking... It should be mFrame->GetSize().

> mTextRun->MeasureText is returning a cached result in RecomputeOverflowRect,
> right?

The glyph metrics will have been cached in the textrun, yes, so we won't compute them again. The overall result must be recomputed (it varies here because we may have added justification spacing since we measured the text in Reflow). Note, though, that RecomputeOverflowRect only gets called when text-align:justify is in effect, so it should not be a significant performance issue anyway.

> I don't think that long list of people contributed to nsTextFrameBase.

Oh yeah, I'll fix that.

> You might want a blank line to separate these comments:
>    // XXX what about adjusting bounding metrics?
> +  // probably should not measure text in ::Reflow, but wait for
> +  // RecomputeOverflowRect to be called

OK. Actually I might just delete that comment since it might not be right.
Comment 60 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-20 21:49:48 PDT
Created attachment 281783 [details] [diff] [review]
updated patch v6

updated to those comments
Comment 61 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2007-09-21 15:26:20 PDT
Comment on attachment 281783 [details] [diff] [review]
updated patch v6

The alternative to having nsTextFrameBase seems like having an nsTextFrame.h header file.  In the past we've had some ugly hacks to work around the lack of such a header file -- seems like we may as well have it.

r+sr=dbaron either way

Sorry for the long delay (again).
Comment 62 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-22 05:44:11 PDT
checked in. Watching for performance impact.
Comment 63 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-22 06:29:03 PDT
It caused various platforms to go orange so I backed it out.
Comment 64 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-22 13:32:41 PDT
The problems were reftest failures on all platforms plus a startup failure on fxdbug-linux-tbox. The good news is that performance metrics didn't budge anywhere, as far as I can tell from the one cycle I got.
Comment 65 philippe (part-time) 2007-09-22 23:40:06 PDT
Not sure if the failed reftests revealed this:
with this patch, all type of list-markers (<ul>,<ol>) are completely missing.Tested with the 2007092205 Minefield/3.0a9pre Mac OS X build
(20070922_0557_firefox-3.0a9pre.en-US.mac.dmg
from http://hourly-archive.localgho.st/)
Comment 66 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-23 15:22:03 PDT
Yeah, they did. But thanks for mentioning it.
Comment 67 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-23 17:06:20 PDT
Created attachment 282043 [details] [diff] [review]
updated patch v7

Okay, there are four small changes here:
1) nsTextFrameBase.h converted to nsTextFrame.h as David suggested
2) change in nsBulletFrame.cpp to set mOverflowArea (fixes bullets not appearing, and fixes lots of assertions about overflow area not including glyph bounds; these assertions fire with this patch because we never called FinishAndStoreOverflow on bullet frames before). We set the trivial overflow area, equal to the frame size; handling overflowing bullet glyphs is future work (and anyway, not a regression)
3) Reftest 392435-1.html/392435-1-ref.html needs to be fixed; first-letter is allowed to change the text ascent/descent values, so we should not require that the text background and strike-through be drawn the same way in test vs reference
4) Don't change the advance of first-letters:
-    textMetrics.mAdvanceWidth = textMetrics.mBoundingBox.XMost();
This was causing reftest failures when we compare first-letter vs explicit markup of the first letter, and there is no need for it as far as I can tell.

These fix all the reftest failures as far as I can tell. fxdbug-linux-tbox probably went orange due to a fatal assertion, hopefully fixed by change #2.
Comment 68 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2007-09-23 18:07:34 PDT
(In reply to comment #67)
> fxdbug-linux-tbox
> probably went orange due to a fatal assertion, hopefully fixed by change #2.

You should be able to tell whether it was due to a fatal assertion by looking at the log.
Comment 69 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2007-09-23 18:13:31 PDT
Comment on attachment 282043 [details] [diff] [review]
updated patch v7

File a bug on the XXX comment in nsBulletFrame.cpp and cite it in the comment, and r+sr=dbaron on the content/layout parts.
Comment 70 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-23 19:21:04 PDT
Thanks! Relanded, we'll see how this one goes.
Comment 71 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-23 21:48:16 PDT
Okay, tests are green on all platforms. All performance numbers look normal so far except for about a 1% Tp2 regression on bl-bldlnx03. I'll recheck the numbers later when we have more data. This is one of those situations where we sometimes just have to do more work.
Comment 72 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-25 15:27:25 PDT
This seems to have caused about a 1MB increase in memory usage on Talos/XP:
http://graphs.mozilla.org/graph.html#spst=range&spss=1190464697.2857144&spse=1190724307.4285715&spstart=1180657203&spend=1190753153&bpst=Cursor&bpstart=1190464697.2857144&bpend=1190724307.4285715&m1tid=8&m1bl=0&m1avg=0

I'll try to figure out why.
Comment 73 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-26 12:37:46 PDT
The issue seems to be getting glyph extents for CJK characters. Even if we need extents for just a few glyphs in a font, if the glyphID is, say, 30,000, then we need at least 60K of memory for the font's simple glyph-width table. We're getting glyph extents for at least two reasons:
1) image alt text, which uses nsIRenderingContext APIs and therefore does not set OPTIMIZE_SPEED, which currently is taken as a cue that glyph extents will be needed
2) prefilled text in textfields

The first reason is bogus. nsIRenderingContext APIs currently do not use glyph extents. Therefore I've done a patch which resurrects the NEED_BOUNDING_BOX textrun flag to provide callers with direct control over whether glyph extents will be needed or not. nsTextFrameThebes and SVG set it, currently no-one else does.

The second reason is not bogus. We need a better strategy for storing glyph widths when we have widths for only a few glyphs out of thousands.

After fixing the first issue, here are some numbers using instrumentation I added, over about 1.5 runs of the top500 pageset:

Total number of fonts=7958
Total glyph extents allocated=317 (size 12680)
Average simple array size: 6433.116699
Average tight-bounds table size: 13.022082
Number of simple glyph extents eagerly requested=2254
Number of tight glyph extents eagerly requested=128
Number of tight glyph extents lazily requested=0
Number of simple glyph extent setups that fell back to tight=0

This means we needed some glyph extents for about 1 font in every 26 (7958/317). The average capacity of the simple glyph width array was about 3200 elements, so it's still 2MB of storage just for those arrays --- although not all those will be alive at the same time, so the actual footprint impact will be considerably less. But only 2254 glyph extents were requested, so that's only about 7 glyphs per font (2254/317) on average, so the simple glyph width array occupancy is about 0.22%, which is rather sad.
Comment 74 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-26 13:01:09 PDT
Designing a more efficient data structure is a bit tricky, because sometimes the glyph IDs are sparse, but sometimes they're dense, sometimes both in different regions of glyph ID space in the same font. So a hashtable isn't efficient, but neither is the array we have now.

An array of pointers to arrays of N glyph widths, where null pointers can be used to indicate that all N glyph widths are unknown, is one way to go, but choosing N is tricky. Given G sparse glyphs with a max glyphID of M, this will use about S = M/N*4 + G*N*2 bytes on a 32-bit machine. Minimising S/G with example values of G = 8 and M = 30000, the minimum value of S/G for powers-of-2 N is N=64, which still uses about 362 bytes per glyph, which is better than 7500 with our current plain array, but still not great.

One possible optimization to the block scheme would be to encode a block containing a single glyph width directly overloaded into the block pointer (we only need the bottom log2(N) bits of the glyph ID plus the 16-bit glyph width). Then we could up the block size a bit; say choosing N=128, if there are still no two glyphs in the same block, we end up about 29 bytes per glyph in the above example. That's probably a pretty good approach.

I'll capture the glyph IDs we're actually using in the top500 tests and determine what the optimal parameters are.
Comment 75 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2007-09-26 20:31:08 PDT
Created attachment 282496 [details]
Analysis 

This file contains an instrumentation patch, the results from a performance run, and an analysis script to compute estimated storage requirements for the simple glyph widths using different schemes. The results:

Trunk check: 1794226
Simple blocks:
N=1: 3598894
N=2: 1804492
N=4: 910912
N=8: 471220
N=16: 263292
N=32: 178072
N=64: 170176
N=128: 221096
N=256: 359024
N=512: 627080
N=1024: 1040404
N=2048: 1710436
N=4096: 2729492
N=8192: 4621484
N=16384: 9176160
N=32768: 17761340
N=65536: 35521596
Simple blocks with 1-element block optimization:
N=1: 3595224
N=2: 1798072
N=4: 900736
N=8: 453940
N=16: 232796
N=32: 127256
N=64: 90560
N=128: 78504
N=256: 125552
N=512: 249224
N=1024: 495636
N=2048: 1005924
N=4096: 1885716
N=8192: 3474604
N=16384: 6947936
N=32768: 13763644
N=65536: 27526204

So basically, using simple 64-glyph blocks reduces the memory requirements by a factor of 10. Using the additional optimization for blocks containing only one glyph reduces memory by another factor of 2. I think I'll go with that optimization and N=128 until/unless we get better data.

Note You need to log in before you can comment on or make changes to this bug.