Merge "Fix the way we maintain the list of Pictures in PictureSet. This improves drawing performances on the base surface by a decent amount."

3 files changed, 195 insertions, 106 deletions

diff --git a/Source/WebKit/android/jni/PictureSet.cpp b/Source/WebKit/android/jni/PictureSet.cpp
index 6dafd26..e4bd89c 100644
--- a/Source/WebKit/android/jni/PictureSet.cpp
+++ b/Source/WebKit/android/jni/PictureSet.cpp
@@ -40,6 +40,26 @@
 
 #define MAX_DRAW_TIME 100
 #define MIN_SPLITTABLE 400
+#define MAX_ADDITIONAL_AREA 0.65
+#define MAX_ADDITIONAL_PICTURES 32
+
+#include <wtf/CurrentTime.h>
+
+//#define DEBUG
+#ifdef DEBUG
+
+#include <cutils/log.h>
+#include <wtf/text/CString.h>
+
+#undef XLOG
+#define XLOG(...) android_printLog(ANDROID_LOG_DEBUG, "PictureSet", __VA_ARGS__)
+
+#else
+
+#undef XLOG
+#define XLOG(...)
+
+#endif // DEBUG
 
 #if PICTURE_SET_DEBUG
 class MeasureStream : public SkWStream {
@@ -58,6 +78,7 @@ namespace android {
 PictureSet::PictureSet()
 {
     mWidth = mHeight = 0;
+    mBaseArea = mAdditionalArea = 0;
 }
 
 PictureSet::~PictureSet()
@@ -73,118 +94,182 @@ void PictureSet::add(const Pictures* temp)
     mPictures.append(pictureAndBounds);
 }
 
+// This function is used to maintain the list of Pictures.
+// Pictures contain an SkPicture covering a specific area; some
+// Pictures are "base" Pictures -- i.e. there is no Pictures
+// underneath them.
+// The idea here is to keep a balance between the number of Pictures
+// we have (more Pictures slow us down) and the area of Pictures that
+// need to be repainted (obviously, smaller areas are better).
+// To do so, we try to not update/repaint the base pictures -- by
+// construction, they usually cover a large area (the entire page).
+// We only reset a base picture if the new invalidated area entirely
+// contains it.
+// Most of the time we thus work on smaller pictures on top of the
+// base ones; We compute the total area of all pictures intersecting
+// with the passed invalidated area (as they would need to be invalidated),
+// and use that as the basis for the correct area we want to invalidate
+// (we then can simply delete the pictures we intersect with).
+// In addition, we do a couple of things to limit the total number of pictures
+// we keep in the list:
+// - if the total area of additional textures reach 65% of the base pictures,
+//   we delete the additional pictures and mark the base pictures as
+//   needing a full repaint
+// - we limit the number of pictures to 32 -- above that, we do the same
+//   things (deleting additional pictures + full repaint of base pictures)
 void PictureSet::add(const SkRegion& area, SkPicture* picture,
     uint32_t elapsed, bool split, bool empty)
 {
-    DBG_SET_LOGD("%p area={%d,%d,r=%d,b=%d} pict=%p elapsed=%d split=%d", this,
-        area.getBounds().fLeft, area.getBounds().fTop,
-        area.getBounds().fRight, area.getBounds().fBottom, picture,
-        elapsed, split);
-    SkSafeRef(picture);
-    /* if nothing is drawn beneath part of the new picture, mark it as a base */
-    SkRegion diff = SkRegion(area);
-    Pictures* last = mPictures.end();
-    for (Pictures* working = mPictures.begin(); working != last; working++)
-        diff.op(working->mArea, SkRegion::kDifference_Op);
-    Pictures pictureAndBounds = {area, picture, area.getBounds(),
-        elapsed, split, false, diff.isEmpty() == false, empty};
-    mPictures.append(pictureAndBounds);
-}
+    bool checkForNewBases = false;
 
-/*
-Pictures are discarded when they are fully drawn over.
-When a picture is partially drawn over, it is discarded if it is not a base, and
-its rectangular bounds is reduced if it is a base.
-*/
-bool PictureSet::build()
-{
-    bool rebuild = false;
-    DBG_SET_LOGD("%p", this);
-    // walk pictures back to front, removing or trimming obscured ones
-    SkRegion drawn;
-    SkRegion inval;
     Pictures* first = mPictures.begin();
     Pictures* last = mPictures.end();
-    Pictures* working;
-    bool checkForNewBases = false;
-    for (working = last; working != first; ) {
-        --working;
-        SkRegion& area = working->mArea;
-        SkRegion visibleArea(area);
-        visibleArea.op(drawn, SkRegion::kDifference_Op);
-#if PICTURE_SET_DEBUG
-        const SkIRect& a = area.getBounds();
-        const SkIRect& d = drawn.getBounds();
-        const SkIRect& i = inval.getBounds();
-        const SkIRect& v = visibleArea.getBounds();
-        DBG_SET_LOGD("%p [%d] area={%d,%d,r=%d,b=%d} drawn={%d,%d,r=%d,b=%d}"
-            " inval={%d,%d,r=%d,b=%d} vis={%d,%d,r=%d,b=%d}",
-            this, working - first,
-            a.fLeft, a.fTop, a.fRight, a.fBottom,
-            d.fLeft, d.fTop, d.fRight, d.fBottom,
-            i.fLeft, i.fTop, i.fRight, i.fBottom,
-            v.fLeft, v.fTop, v.fRight, v.fBottom);
+#ifdef DEBUG
+    XLOG("--- before adding the new inval ---");
+    for (Pictures* working = mPictures.begin(); working != mPictures.end(); working++) {
+        SkIRect currentArea = working->mArea.getBounds();
+        XLOG("picture %d (%d, %d, %d, %d - %d x %d) (isRect? %c) base: %c",
+             working - first,
+             currentArea.fLeft, currentArea.fTop, currentArea.fRight, currentArea.fBottom,
+             currentArea.width(), currentArea.height(),
+             working->mArea.isRect() ? 'Y' : 'N',
+             working->mBase ? 'Y' : 'N');
+    }
+    XLOG("----------------------------------");
 #endif
-        bool tossPicture = false;
-        if (working->mBase == false) {
-            if (area != visibleArea) {
-                if (visibleArea.isEmpty() == false) {
-                    DBG_SET_LOGD("[%d] partially overdrawn", working - first);
-                    inval.op(visibleArea, SkRegion::kUnion_Op);
-                } else
-                    DBG_SET_LOGD("[%d] fully hidden", working - first);
-                area.setEmpty();
-                tossPicture = true;
-            }
-        } else {
-            const SkIRect& visibleBounds = visibleArea.getBounds();
-            const SkIRect& areaBounds = area.getBounds();
-            if (visibleBounds != areaBounds) {
-                DBG_SET_LOGD("[%d] base to be reduced", working - first);
-                area.setRect(visibleBounds);
-                checkForNewBases = tossPicture = true;
-            }
-            if (area.intersects(inval)) {
-                DBG_SET_LOGD("[%d] base to be redrawn", working - first);
-                tossPicture = true;
+
+    // let's gather all the Pictures intersecting with the new invalidated
+    // area, collect their area and remove their picture
+    SkIRect totalArea = area.getBounds();
+    for (Pictures* working = first; working != last; working++) {
+        SkIRect inval = area.getBounds();
+        bool remove = false;
+        if (!working->mBase && working->mArea.intersects(inval))
+            remove = true;
+        if (working->mBase) {
+            SkIRect baseArea = working->mArea.getBounds();
+            if (area.contains(baseArea)) {
+                remove = true;
+                checkForNewBases = true;
             }
         }
-        if (tossPicture) {
+
+        if (remove) {
+            SkIRect currentArea = working->mArea.getBounds();
+            if (working->mBase)
+                mBaseArea -= currentArea.width() * currentArea.height();
+            else
+                mAdditionalArea -= currentArea.width() * currentArea.height();
+
+            totalArea.join(currentArea);
+            XLOG("picture %d (%d, %d, %d, %d - %d x %d) (isRect? %c) intersects with the new inval area (%d, %d, %d, %d - %d x %d) (isRect? %c, we remove it",
+                 working - first,
+                 currentArea.fLeft, currentArea.fTop, currentArea.fRight, currentArea.fBottom,
+                 currentArea.width(), currentArea.height(),
+                 working->mArea.isRect() ? 'Y' : 'N',
+                 inval.fLeft, inval.fTop, inval.fRight, inval.fBottom,
+                 inval.width(), inval.height(),
+                 area.isRect() ? 'Y' : 'N');
+            working->mArea.setEmpty();
+            SkSafeUnref(working->mPicture);
+            working->mPicture = 0;
+
+        }
+    }
+
+    // Now we can add the new Picture to the list, with the correct area
+    // that need to be repainted
+    SkRegion collect;
+    collect.setRect(totalArea);
+    Pictures pictureAndBounds = {collect, 0, collect.getBounds(),
+        elapsed, split, false, false, empty};
+    mPictures.append(pictureAndBounds);
+    mAdditionalArea += totalArea.width() * totalArea.height();
+    last = mPictures.end();
+    first = mPictures.begin();
+
+    // Then, let's see if we have to clear up the pictures in order to keep
+    // the total number of pictures under our limit
+    bool clearUp = false;
+    if (last - first > MAX_ADDITIONAL_PICTURES) {
+        XLOG("--- too many pictures, only keeping the bases : %d", last - first);
+        clearUp = true;
+    }
+
+    if (!clearUp) {
+        if (mBaseArea > 0 && mBaseArea * MAX_ADDITIONAL_AREA <= mAdditionalArea) {
+            XLOG("+++ the sum of the additional area is > %.2f\% of the base Area (%.2f (%.2f) <= %.2f",
+                 MAX_ADDITIONAL_AREA * 100, baseArea * 0.65, baseArea, addArea);
+            clearUp = true;
+        }
+    }
+
+    if (clearUp) {
+        for (Pictures* working = mPictures.begin(); working != mPictures.end(); working++) {
+            if (!working->mBase)
+                working->mArea.setEmpty();
             SkSafeUnref(working->mPicture);
-            working->mPicture = NULL; // mark to redraw
+            working->mPicture = 0;
         }
-        if (working->mPicture == NULL) // may have been set to null elsewhere
-            rebuild = true;
-        drawn.op(area, SkRegion::kUnion_Op);
     }
-    // collapse out empty regions
+
+#ifdef DEBUG
+    XLOG("--- after adding the new inval, but before collapsing ---");
+    for (Pictures* working = mPictures.begin(); working != mPictures.end(); working++) {
+        SkIRect currentArea = working->mArea.getBounds();
+        XLOG("picture %d (%d, %d, %d, %d - %d x %d) (isRect? %c) base: %c",
+             working - first,
+             currentArea.fLeft, currentArea.fTop, currentArea.fRight, currentArea.fBottom,
+             currentArea.width(), currentArea.height(),
+             working->mArea.isRect() ? 'Y' : 'N',
+             working->mBase ? 'Y' : 'N');
+    }
+    XLOG("----------------------------------");
+    XLOG("let's collapse...");
+#endif
+
+    // Finally, let's do a pass to collapse out empty regions
     Pictures* writer = first;
-    for (working = first; working != last; working++) {
-        if (working->mArea.isEmpty())
+    for (Pictures* working = first; working != last; working++) {
+        if (working && working->mArea.isEmpty())
             continue;
         *writer++ = *working;
     }
-#if PICTURE_SET_DEBUG
-    if ((unsigned) (writer - first) != mPictures.size())
-        DBG_SET_LOGD("shrink=%d (was %d)", writer - first, mPictures.size());
-#endif
+    XLOG("shiking of %d elements", writer - first);
     mPictures.shrink(writer - first);
-    /* When a base is discarded because it was entirely drawn over, all  
-       remaining pictures are checked to see if one has become a base. */
+
+#ifdef DEBUG
+    XLOG("--- after adding the new inval ---");
+    for (Pictures* working = mPictures.begin(); working != mPictures.end(); working++) {
+        SkIRect currentArea = working->mArea.getBounds();
+        XLOG("picture %d (%d, %d, %d, %d - %d x %d) (isRect? %c) base: %c picture %x",
+             working - first,
+             currentArea.fLeft, currentArea.fTop, currentArea.fRight, currentArea.fBottom,
+             currentArea.width(), currentArea.height(),
+             working->mArea.isRect() ? 'Y' : 'N',
+             working->mBase ? 'Y' : 'N', working->mPicture);
+    }
+    XLOG("----------------------------------");
+#endif
+
+    // Base pictures might have been removed/added -- let's recompute them
+    SkRegion drawn;
     if (checkForNewBases) {
         drawn.setEmpty();
         Pictures* last = mPictures.end();
-        for (working = mPictures.begin(); working != last; working++) {
+        XLOG("checkForNewBases...");
+        for (Pictures* working = mPictures.begin(); working != last; working++) {
             SkRegion& area = working->mArea;
+            const SkIRect& a = area.getBounds();
             if (drawn.contains(working->mArea) == false) {
                 working->mBase = true;
-                DBG_SET_LOGD("[%d] new base", working - mPictures.begin());
+                float area = a.width() * a.height();
+                mBaseArea += area;
+                mAdditionalArea -= area;
             }
             drawn.op(working->mArea, SkRegion::kUnion_Op);
         }
     }
-    validate(__FUNCTION__);
-    return rebuild;
 }
 
 void PictureSet::checkDimensions(int width, int height, SkRegion* inval)
diff --git a/Source/WebKit/android/jni/PictureSet.h b/Source/WebKit/android/jni/PictureSet.h
index b177958..907fb92 100644
--- a/Source/WebKit/android/jni/PictureSet.h
+++ b/Source/WebKit/android/jni/PictureSet.h
@@ -56,15 +56,25 @@ namespace android {
         PictureSet(const PictureSet& src) { set(src); }
         virtual ~PictureSet();
         void add(const SkRegion& area, SkPicture* picture,
-            uint32_t elapsed, bool split) 
+            uint32_t elapsed, bool split)
         {
-            add(area, picture, elapsed, split, emptyPicture(picture));
+            if (area.isRect()) {
+                add(area, picture, elapsed, split, false);
+            } else {
+                SkRegion::Iterator cliperator(area);
+                while (!cliperator.done()) {
+                    SkIRect ir = cliperator.rect();
+                    SkRegion newArea;
+                    newArea.setRect(ir);
+                    add(newArea, picture, elapsed, split, false);
+                    cliperator.next();
+                }
+            }
         }
         void add(const SkRegion& area, SkPicture* picture,
             uint32_t elapsed, bool split, bool empty);
         const SkIRect& bounds(size_t i) const {
             return mPictures[i].mArea.getBounds(); }
-        bool build();
         // Update mWidth/mHeight, and adds any additional inval region
         void checkDimensions(int width, int height, SkRegion* inval);
         void clear();
@@ -94,6 +104,8 @@ namespace android {
             bool mBase : 8; // true if nothing is drawn underneath this
             bool mEmpty : 8; // true if the picture only draws white
         };
+        float mBaseArea;
+        float mAdditionalArea;
         void add(const Pictures* temp);
         WTF::Vector<Pictures> mPictures;
         int mHeight;
diff --git a/Source/WebKit/android/jni/WebViewCore.cpp b/Source/WebKit/android/jni/WebViewCore.cpp
index 0b5845b..494ebea 100644
--- a/Source/WebKit/android/jni/WebViewCore.cpp
+++ b/Source/WebKit/android/jni/WebViewCore.cpp
@@ -664,25 +664,12 @@ void WebViewCore::recordPictureSet(PictureSet* content)
 
     content->checkDimensions(width, height, &m_addInval);
 
-    // The inval region may replace existing pictures. The existing pictures
-    // may have already been split into pieces. If reuseSubdivided() returns
-    // true, the split pieces are the last entries in the picture already. They
-    // are marked as invalid, and are rebuilt by rebuildPictureSet().
-
-    // If the new region doesn't match a set of split pieces, add it to the end.
-    if (!content->reuseSubdivided(m_addInval)) {
-        const SkIRect& inval = m_addInval.getBounds();
-        SkPicture* picture = rebuildPicture(inval);
-        DBG_SET_LOGD("{%d,%d,w=%d,h=%d}", inval.fLeft,
-            inval.fTop, inval.width(), inval.height());
-        content->add(m_addInval, picture, 0, false);
-        SkSafeUnref(picture);
-    }
-    // Remove any pictures already in the set that are obscured by the new one,
-    // and check to see if any already split pieces need to be redrawn.
-    if (content->build())
-        rebuildPictureSet(content);
+    // Add the current inval rects to the PictureSet, and rebuild it.
+    content->add(m_addInval, 0, 0, false);
+    rebuildPictureSet(content);
+
     } // WebViewCoreRecordTimeCounter
+
     WebCore::Node* oldFocusNode = currentFocus();
     m_frameCacheOutOfDate = true;
     WebCore::IntRect oldBounds;
@@ -879,7 +866,9 @@ BaseLayerAndroid* WebViewCore::createBaseLayer()
     BaseLayerAndroid* base = new BaseLayerAndroid();
     base->setContent(m_content);
 
+    m_skipContentDraw = true;
     bool layoutSucceeded = layoutIfNeededRecursive(m_mainFrame);
+    m_skipContentDraw = false;
     // Layout only fails if called during a layout.
     LOG_ASSERT(layoutSucceeded, "Can never be called recursively");
 
@@ -927,7 +916,10 @@ BaseLayerAndroid* WebViewCore::recordContent(SkRegion* region, SkIPoint* point)
     }
     region->set(m_addInval);
     m_addInval.setEmpty();
+#if USE(ACCELERATED_COMPOSITING)
+#else
     region->op(m_rebuildInval, SkRegion::kUnion_Op);
+#endif
     m_rebuildInval.setEmpty();
     point->fX = m_content.width();
     point->fY = m_content.height();