Optimize speed of QTextLayout and QPainter::drawText

QFontEngine::boundingBox() is potentially an expensive function, because
the font engines have to consult the underlying font system for the
values and usually do not cache the results. To account for negative
right bearing in the case of text layouts, we would call the
boundingBox() function at every potential break point in the text,
causing a great performance hit on text drawing. To minimize the impact
of this, we only calculate the right bearing when we have to:

1. If subtracting the minimum right bearing from the width would cause
   the line to expand beyond its maximum line width, then we have to
   get the actual metrics of the last glyph to check if we need to break.

2. The line's final textWidth should include the negative right bearing,
   so unless it has already been calculated, we calculate it when the
   correct line width has been found.

This gives us a potentially huge speed-up, since boundingBox() will in
the common case only be called once for the last glyph in each text
line.

Task-number: QTBUG-9074
Reviewed-by: Simon Hausmann

1 files changed, 82 insertions, 40 deletions

diff --git a/src/gui/text/qtextlayout.cpp b/src/gui/text/qtextlayout.cpp
index af91603..204effa 100644
--- a/src/gui/text/qtextlayout.cpp
+++ b/src/gui/text/qtextlayout.cpp
@@ -1644,28 +1644,67 @@ namespace {
 
     struct LineBreakHelper
     {
-        LineBreakHelper() : glyphCount(0), maxGlyphs(0), manualWrap(false) {}
+        LineBreakHelper()
+            : glyphCount(0), maxGlyphs(0), currentPosition(0), fontEngine(0), logClusters(0),
+              manualWrap(false)
+        {
+        }
+
 
         QScriptLine tmpData;
         QScriptLine spaceData;
 
+        QGlyphLayout glyphs;
+
         int glyphCount;
         int maxGlyphs;
+        int currentPosition;
 
         QFixed minw;
         QFixed softHyphenWidth;
         QFixed rightBearing;
+        QFixed minimumRightBearing;
+
+        QFontEngine *fontEngine;
+        const unsigned short *logClusters;
 
         bool manualWrap;
 
         bool checkFullOtherwiseExtend(QScriptLine &line);
+
+        QFixed calculateNewWidth(const QScriptLine &line) const {
+            return line.textWidth + tmpData.textWidth + spaceData.textWidth + softHyphenWidth
+                    - qMin(rightBearing, QFixed());
+        }
+
+        inline glyph_t currentGlyph() const
+        {
+            Q_ASSERT(currentPosition > 0);
+            return glyphs.glyphs[logClusters[currentPosition - 1]];
+        }
+
+        inline void adjustRightBearing()
+        {
+            if (currentPosition <= 0)
+                return;
+
+            glyph_metrics_t gi = fontEngine->boundingBox(currentGlyph());
+            if (gi.isValid())
+                rightBearing = qMin(QFixed(), gi.xoff - gi.x - gi.width);
+        }
+
+        inline void resetRightBearing()
+        {
+            rightBearing = QFixed(1); // Any positive number is defined as invalid since only
+                                      // negative right bearings are interesting to us.
+        }
     };
 
 inline bool LineBreakHelper::checkFullOtherwiseExtend(QScriptLine &line)
 {        
     LB_DEBUG("possible break width %f, spacew=%f", tmpData.textWidth.toReal(), spaceData.textWidth.toReal());
 
-    QFixed newWidth = line.textWidth + tmpData.textWidth + spaceData.textWidth + softHyphenWidth + rightBearing;
+    QFixed newWidth = calculateNewWidth(line);
     if (line.length && !manualWrap && (newWidth > line.width || glyphCount > maxGlyphs))
         return true;
 
@@ -1741,13 +1780,12 @@ void QTextLine::layout_helper(int maxGlyphs)
     Qt::Alignment alignment = eng->option.alignment();
 
     const HB_CharAttributes *attributes = eng->attributes();
-    int pos = line.from;
+    lbh.currentPosition = line.from;
     int end = 0;
-    QGlyphLayout glyphs;
-    const unsigned short *logClusters = eng->layoutData->logClustersPtr;
+    lbh.logClusters = eng->layoutData->logClustersPtr;
 
     while (newItem < eng->layoutData->items.size()) {
-        lbh.rightBearing = 0;
+        lbh.resetRightBearing();
         lbh.softHyphenWidth = 0;
         if (newItem != item) {
             item = newItem;
@@ -1755,13 +1793,19 @@ void QTextLine::layout_helper(int maxGlyphs)
             if (!current.num_glyphs) {
                 eng->shape(item);
                 attributes = eng->attributes();
-                logClusters = eng->layoutData->logClustersPtr;
+                lbh.logClusters = eng->layoutData->logClustersPtr;
             }
-            pos = qMax(line.from, current.position);
+            lbh.currentPosition = qMax(line.from, current.position);
             end = current.position + eng->length(item);
-            glyphs = eng->shapedGlyphs(&current);
+            lbh.glyphs = eng->shapedGlyphs(&current);
         }
         const QScriptItem &current = eng->layoutData->items[item];
+        QFontEngine *fontEngine = eng->fontEngine(current);
+        if (lbh.fontEngine != fontEngine) {
+            lbh.fontEngine = fontEngine;
+            lbh.minimumRightBearing = qMin(QFixed(),
+                                           QFixed::fromReal(fontEngine->minRightBearing()));
+        }
 
         lbh.tmpData.leading = qMax(lbh.tmpData.leading + lbh.tmpData.ascent,
                                    current.leading + current.ascent) - qMax(lbh.tmpData.ascent,
@@ -1791,8 +1835,8 @@ void QTextLine::layout_helper(int maxGlyphs)
             if (!line.length && !lbh.tmpData.length)
                 line.setDefaultHeight(eng);
             if (eng->option.flags() & QTextOption::ShowLineAndParagraphSeparators) {
-                addNextCluster(pos, end, lbh.tmpData, lbh.glyphCount,
-                               current, logClusters, glyphs);
+                addNextCluster(lbh.currentPosition, end, lbh.tmpData, lbh.glyphCount,
+                               current, lbh.logClusters, lbh.glyphs);
             } else {
                 lbh.tmpData.length++;
             }
@@ -1811,10 +1855,10 @@ void QTextLine::layout_helper(int maxGlyphs)
             ++lbh.glyphCount;
             if (lbh.checkFullOtherwiseExtend(line))
                 goto found;
-        } else if (attributes[pos].whiteSpace) {
-            while (pos < end && attributes[pos].whiteSpace)
-                addNextCluster(pos, end, lbh.spaceData, lbh.glyphCount,
-                               current, logClusters, glyphs);
+        } else if (attributes[lbh.currentPosition].whiteSpace) {
+            while (lbh.currentPosition < end && attributes[lbh.currentPosition].whiteSpace)
+                addNextCluster(lbh.currentPosition, end, lbh.spaceData, lbh.glyphCount,
+                               current, lbh.logClusters, lbh.glyphs);
 
             if (!lbh.manualWrap && lbh.spaceData.textWidth > line.width) {
                 lbh.spaceData.textWidth = line.width; // ignore spaces that fall out of the line.
@@ -1823,19 +1867,19 @@ void QTextLine::layout_helper(int maxGlyphs)
         } else {
             bool sb_or_ws = false;
             do {
-                addNextCluster(pos, end, lbh.tmpData, lbh.glyphCount,
-                               current, logClusters, glyphs);
+                addNextCluster(lbh.currentPosition, end, lbh.tmpData, lbh.glyphCount,
+                               current, lbh.logClusters, lbh.glyphs);
 
-                if (attributes[pos].whiteSpace || attributes[pos-1].lineBreakType != HB_NoBreak) {
+                if (attributes[lbh.currentPosition].whiteSpace || attributes[lbh.currentPosition-1].lineBreakType != HB_NoBreak) {
                     sb_or_ws = true;
                     break;
-                } else if (breakany && attributes[pos].charStop) {
+                } else if (breakany && attributes[lbh.currentPosition].charStop) {
                     break;
                 }
-            } while (pos < end);
+            } while (lbh.currentPosition < end);
             lbh.minw = qMax(lbh.tmpData.textWidth, lbh.minw);
 
-            if (pos && attributes[pos - 1].lineBreakType == HB_SoftHyphen) {
+            if (lbh.currentPosition && attributes[lbh.currentPosition - 1].lineBreakType == HB_SoftHyphen) {
                 // if we are splitting up a word because of
                 // a soft hyphen then we ...
                 //
@@ -1853,41 +1897,39 @@ void QTextLine::layout_helper(int maxGlyphs)
                 //     and thus become invisible again.
                 //
                 if (line.length)
-                    lbh.softHyphenWidth = glyphs.advances_x[logClusters[pos - 1]];
+                    lbh.softHyphenWidth = lbh.glyphs.advances_x[lbh.logClusters[lbh.currentPosition - 1]];
                 else if (breakany)
-                    lbh.tmpData.textWidth += glyphs.advances_x[logClusters[pos - 1]];
+                    lbh.tmpData.textWidth += lbh.glyphs.advances_x[lbh.logClusters[lbh.currentPosition - 1]];
             }
 
             // The actual width of the text needs to take the right bearing into account. The
             // right bearing is left-ward, which means that if the rightmost pixel is to the right
             // of the advance of the glyph, the bearing will be negative. We flip the sign
             // for the code to be more readable. Logic borrowed from qfontmetrics.cpp.
-            if (pos) {
-                QFontEngine *fontEngine = eng->fontEngine(current);
-                glyph_t glyph = glyphs.glyphs[logClusters[pos - 1]];
-                glyph_metrics_t gi = fontEngine->boundingBox(glyph);
-                if (gi.isValid())
-                    lbh.rightBearing = qMax(QFixed(), -(gi.xoff - gi.x - gi.width));
-            }
+            // We ignore the right bearing if the minimum negative bearing is too little to
+            // expand the text beyond the edge.
+            if (sb_or_ws|breakany) {
+                if (lbh.calculateNewWidth(line) + lbh.minimumRightBearing > line.width)
+                    lbh.adjustRightBearing();
+                if (lbh.checkFullOtherwiseExtend(line)) {
+                    if (!breakany) {
+                        line.textWidth += lbh.softHyphenWidth;
+                    }
 
-            if ((sb_or_ws|breakany) && lbh.checkFullOtherwiseExtend(line)) {
-                if (!breakany) {
-                    line.textWidth += lbh.softHyphenWidth;
+                    goto found;
                 }
-
-                line.textWidth += lbh.rightBearing;
-
-                goto found;
             }
         }
-        if (pos == end)
+        if (lbh.currentPosition == end)
             newItem = item + 1;
     }
     LB_DEBUG("reached end of line");
     lbh.checkFullOtherwiseExtend(line);
-    line.textWidth += lbh.rightBearing;
-
 found:       
+    if (lbh.rightBearing > 0) // If right bearing has not yet been adjusted
+        lbh.adjustRightBearing();
+    line.textWidth -= qMin(QFixed(), lbh.rightBearing);
+
     if (line.length == 0) {
         LB_DEBUG("no break available in line, adding temp: length %d, width %f, space: length %d, width %f",
                lbh.tmpData.length, lbh.tmpData.textWidth.toReal(),