538669 - Improve idle crawler

Status: RESOLVED FIXED

(Firefox for Android Graveyard :: General, defect)

Description

[Benjamin Stover (:stechz)]

Attachment: Patch

Several changes to the idle crawler.  Zooming feels faster.  Panning doesn't stall as much.  There is a *lot* less checkerboarding.

Lots of changes here, it is a work in progress.

Comment 1

[Benjamin Stover (:stechz)]

Attachment: v2

Now broken up into three patches, with this one focusing on two things:
1) endCriticalMove no longer releases the tiles--that is now the job of the first critical paint.  Now nothing can evict the last critical rect, and the minimal amount of work is done for holding and releasing tiles.
2) Complete rewrite of the iterator, that more or less uses the same algorithm.  It needs to be tested with trace, but so far profiling has shown the rewrite perform better.

Comment 2

[Benjamin Stover (:stechz)]

Attachment: traced

Stay on trace

Comment 3

[Roy Frostig :froystig]

Comment on attachment 421372 [details] [diff] [review]
traced

>-      window.QueryInterface(Ci.nsIInterfaceRequestor)
>-        .getInterface(Ci.nsIDOMWindowUtils).processUpdates();
>+//      window.QueryInterface(Ci.nsIInterfaceRequestor)
>+//        .getInterface(Ci.nsIDOMWindowUtils).processUpdates();

What's this change do?  (I'm not sure what it did before.)

>-  /**
>-   * @param dx Guess delta to destination x coordinate
>-   * @param dy Guess delta to destination y coordinate
>-   */
>-  onBeforeVisibleMove: function onBeforeVisibleMove(dx, dy) {
>-    let vs = this._browserViewportState;
>-    let vr = this.getVisibleRect();
>-
>-    let destCR = BrowserView.Util.visibleRectToCriticalRect(vr.translate(dx, dy), vs);
>-
>-    this._tileManager.beginCriticalMove(destCR);
>-  },
>-

Fine with removing this only if we can promise to maintain the invariant "tile is not dirty if and only if it is appended", which seems to be the case as discussed in IRC.  Might be worth documenting somewhere. :S


>-  /* remember these values to reduce the recenterEvictionQueue cost */
>-  this._ctr = new Point(0, 0);
[...]
>-      // waiting to be rendered. Make sure crawler knows about them.
>-      this.recenterCrawler();
>+      // waiting to be rendered. Make sure crawler and eviction knows about them.
>+      this.recenterCrawler(this._ctr);

|this._ctr| isn't going to exist there.


>+    // used to remember tiles that we've reused during this crawl
>+    this._visited = {}
>+    // filters the tiles we've already reused once from being considered victims
>+    // for reuse when we ask the tile cache to create a new tile
>+    let visited = this._visited;
>+    // XXX is this function not in the prototype so that a "this" lookup is saved?
>+    this._notVisited = function(tile) { return !visited[tile.i + "," + tile.j]; };

In response to XXX:  Yes and no.  The filter function is passed to getTile() which then calls it as |fn()|, so |this| will be |window| without the above, which gives us |visited| in the closure.  No need to keep the XXX comment.


Patch changes a lot but looks good and I'm glad to see crawl re-centering and re-triggering separate now.  I hope you tested it in the wild more than I did. :)

r+ with answers/fixes to the above.

Comment 4

[Vivien Nicolas (:vingtetun) (:21) - (NOT reading bugmails, needinfo? please)]

>diff --git a/chrome/content/BrowserView.js b/chrome/content/BrowserView.js
>--- a/chrome/content/BrowserView.js
>+++ b/chrome/content/BrowserView.js
>@@ -325,18 +325,18 @@ BrowserView.prototype = {
>       rect = rect || vis;
>       let zoomRatio = vis.width / rect.width;
>       let viewBuffer = Elements.viewBuffer;
>       viewBuffer.width = vis.width;
>       viewBuffer.height = vis.height;
> 
>       this._tileManager.renderRectToCanvas(rect, viewBuffer, zoomRatio, zoomRatio, false);
>       viewBuffer.style.display = "block";
>-      window.QueryInterface(Ci.nsIInterfaceRequestor)
>-        .getInterface(Ci.nsIDOMWindowUtils).processUpdates();
>+//      window.QueryInterface(Ci.nsIInterfaceRequestor)
>+//        .getInterface(Ci.nsIDOMWindowUtils).processUpdates();
>       this.pauseRendering();
>     }
>     this._offscreenDepth++;
>   },

I think I have heard mfinkle says this is here for perfs reasons in some other part of the code, let's keep the call if you don't really need to remove it.

>-  /**
>-   * @param dx Guess delta to destination x coordinate
>-   * @param dy Guess delta to destination y coordinate
>-   */
>-  onBeforeVisibleMove: function onBeforeVisibleMove(dx, dy) {
>-    let vs = this._browserViewportState;
>-    let vr = this.getVisibleRect();
>-
>-    let destCR = BrowserView.Util.visibleRectToCriticalRect(vr.translate(dx, dy), vs);
>-
>-    this._tileManager.beginCriticalMove(destCR);
>-  },
>-
>   onAfterVisibleMove: function onAfterVisibleMove() {
>     let vs = this._browserViewportState;
>     let vr = this.getVisibleRect();
> 
>     vs.visibleX = vr.left;
>     vs.visibleY = vr.top;


Since you remove all the onBeforeVisibleMove/beginCriticalMove, I'm fine with the onAfterVisibleMove change but could we also rename the endCriticalMove to something like onAfterCriticalMove or something which doesn't sounds like this function come in pair with something else. Also thinking of it the "on" prefix sounds like a react to event.

> TileManager.prototype = {
>@@ -157,22 +157,21 @@ TileManager.prototype = {
>     let tc = this._tileCache;
> 
>     let iBoundOld = tc.iBound;
>     let jBoundOld = tc.jBound;
>     let iBound = tc.iBound = Math.ceil(viewportRect.right / kTileWidth) - 1;
>     let jBound = tc.jBound = Math.ceil(viewportRect.bottom / kTileHeight) - 1;
> 
>     if (criticalRect.isEmpty() || !criticalRect.equals(this._criticalRect)) {
>-      this.beginCriticalMove(criticalRect);
>       this.endCriticalMove(criticalRect, !(dirtyAll || boundsSizeChanged));
>     } else {
>       // The critical rect hasn't changed, but there are possibly more tiles lounging about offscreen,
>-      // waiting to be rendered. Make sure crawler knows about them.
>-      this.recenterCrawler();
>+      // waiting to be rendered. Make sure crawler and eviction knows about them.
>+      this.recenterCrawler(this._ctr);
>     }

As Roy said this._ctr isn't going to exist here

> 
>   criticalRectPaint: function criticalRectPaint() {
>     let cr = this._criticalRect;
>+    let lastCr = this._lastCriticalRect;
> 
>-    //let start = Date.now();
>+    if (!lastCr.isEmpty()) {
>+      // This is the first paint since the last critical move.
>+      let tc = this._tileCache;
>+      BEGIN_FOREACH_IN_RECT(lastCr, tc, tile)
>+        tc.releaseTile(tile);
>+      END_FOREACH_IN_RECT

Reading the macro i'm not sure to understand why we need to pass it a the third argument "tile" since the macro do a let tile in it?
Is that for an easier read?
Also maybe we can add a "\n" at the end of each line in the macro? If an error occurs in the error console it would be easier to identify the line.

> 
>-    if (!cr.isEmpty()) {
>-      let ctr = cr.center().map(Math.round);
>+      lastCr.setRect(0, 0, 0, 0);
> 

Why did the old code was settings this._ctr = cr.center().map(Math.round); and now we are setting it to 0,0,0,0 (lastCr.setRect(0, 0, 0, 0);) ?

>   endCriticalMove: function endCriticalMove(destCriticalRect, doCriticalPaint) {
>-    let tc = this._tileCache;
>     let cr = this._criticalRect;
>-
>-    //let start = Date.now();
>-
>-    if (!cr.isEmpty()) {
>-      BEGIN_FOREACH_IN_RECT(cr, tc, tile)
>-	    tc.releaseTile(tile);
>-      END_FOREACH_IN_RECT
>-    }
>-
>-    //dump(" release: " + (Date.now() - start) + "\n");
>-    //start = Date.now();
>-
>-    // XXX the conjunction with doCriticalPaint may cause tiles to disappear
>-    // (be evicted) during a (relatively slow) move as no tiles will be "held"
>-    // until a critical paint is requested.  Also, while we have this
>-    // && doCriticalPaint then we don't need this loop altogether, as
>-    // criticalRectPaint will hold everything for us (called below)
>-    //if (destCriticalRect && doCriticalPaint) {
>-    //  BEGIN_FOREACH_IN_RECT(destCriticalRect, tc, tile)
>-    //  tc.holdTile(tile);
>-    //  END_FOREACH_IN_RECT
>-    //}
>-
>-    //dump(" hold: " + (Date.now() - start) + "\n");
>-
>+    let lastCr = this._lastCriticalRect;
>+    if (lastCr.isEmpty() && !cr.equals(destCriticalRect))
>+      lastCr.copyFrom(cr);
>     cr.copyFrom(destCriticalRect);

Maybe because of that?

> 
>   _idleTileCrawler: function _idleTileCrawler(self) {
>-    if (!self) self = this;
>+    if (!self)
>+      self = this;
> 
>     let start = Date.now();
>     let comeAgain = true;
>+    let tile;
> 
>     while ((Date.now() - start) <= kTileCrawlTimeCap) {
>-      let tile = self._crawler.next();
>+      tile = self._crawler.next();

If you move let outside of while (which i'm agree with) keep it just above while, this way we should know that it is used only here and live here for as an optimization


>@@ -713,20 +652,21 @@ TileManager.TileCache.prototype = {
>     this._tileMap[i][j] = tile;          // attach
>     return tile;
>   },
> 
>   _evictTile: function _evictTile(evictionGuard) {
>     let k = this._pos;
>     let pool = this._tilePool;
>     let victim = null;
>-
>+    let tile;
>     for (; k >= 0; --k) {
>-      if (pool[k].free && ( !evictionGuard || evictionGuard(pool[k]) )) {
>-        victim = pool[k];
>+      tile = pool[k];
>+      if (!this.inBounds(tile.i, tile.j) || tile.free && ( !evictionGuard || evictionGuard(tile) )) {
>+        victim = tile;
>         --k;
>         break;
>       }
>     }
> 
>     this._pos = k;
> 
>     return victim;

Idem. If you could just reorganise it to let us know at four sight which var is global to the function and which one just need to live here for the duration of the "for"



>+
>+TileManager.CrawlIterator.prototype = {
>+  _generateCrawlQueue: function _generateCrawlQueue(rect) {
>+    function add(i, j) {
>+      if (tc.inBounds(i, j)) {
>+        outOfBounds = false;
>+        result.push([i, j]);
>+        if (--index == 0)
>+          return true;
>+      }
>+      return false;
>+    }

So, add return true only if the capacity is reached/full and false otherwise? If that, the return value order are strange for such a a name.


>+  recenter: function recenter(rect) {
>+    // Queue should not be very big, so put first priorities last in order to pop quickly.
>+    this._crawlQueue = rect.isEmpty() ? [] : this._generateCrawlQueue(rect).reverse();
>+    // used to remember tiles that we've reused during this crawl
>+    this._visited = {}
>+    // filters the tiles we've already reused once from being considered victims
>+    // for reuse when we ask the tile cache to create a new tile
>+    let visited = this._visited;
>+    // XXX is this function not in the prototype so that a "this" lookup is saved?
>+    this._notVisited = function(tile) { return !visited[tile.i + "," + tile.j]; };
>   },
> 

Please address Roy's comment here so we can live without an other XXX in the code! :)

>   next: function next() {
>-    if (this._queueState)
>-      return this.dequeue();
>-
>+    // Priority for next goes to the crawl queue, dirty tiles afterwards. Since dirty
>+    // tile queue does not really have a necessary order, pop off the top.
>+    let coords = this._crawlQueue.pop() || this.dequeue();
>     let tile = null;
>-
>-    if (this._crawlIndices) {
>-      try {
>-        let [i, j] = this._crawlIndices.next();
>-        tile = this._tileCache.getTile(i, j, true, this._notVisited);
>-      } catch (e) {
>-        if (!(e instanceof StopIteration))
>-          throw e;
>+    if (coords) {
>+      let [i, j] = coords;
>+      // getTile will create a tile only if there are any left in our capacity that have not been
>+      // visited already by the crawler.
>+      tile = this._tileCache.getTile(i, j, true, this._notVisited);
>+      if (tile) {
>+        this._visited[this._strIndices(i, j)] = true;
>+      } else {
>+        tile = this.next();
>       }
>     }
>-
>-    if (tile) {
>-      this._visited[tile.toString()] = true;
>-    } else {
>-      this.becomeQueue();
>-      return this.next();
>-    }
>-
>     return tile;
>   },

I'm wondering if the 
>-    } else {
>-      this.becomeQueue();
>-      return this.next();
>-    }

calls is not better for the stack than the 

>+      if (tile) {
>+        this._visited[this._strIndices(i, j)] = true;
>+      } else {
>+        tile = this.next();
>       }

?
------------------

Changes looks ok, there is a lot of rewrite here and I'm fully at my ease with the tilemanager code, so my comments are mostly nits about code syntax and Co.

My only real question here is the one about

>-    if (!cr.isEmpty()) {
>-      let ctr = cr.center().map(Math.round);
>+      lastCr.setRect(0, 0, 0, 0);

Comment 5

[Benjamin Stover (:stechz)]

>I'm wondering if the 
>>-    } else {
>>-      this.becomeQueue();
>>-      return this.next();
>>-    }
>
>calls is not better for the stack than the 

Why do you think it's better in the old version?

>My only real question here is the one about
>
>>-    if (!cr.isEmpty()) {
>>-      let ctr = cr.center().map(Math.round);
>>+      lastCr.setRect(0, 0, 0, 0);

Instead of caching the center of the critical rect, this caches the last critical rect if the rect has changed.  It has the same effect (doing the hard work in criticalRectPaint just once) but this way we know what the last critical rect was.

This is useful because now we always have a hold on some critical rect, so the crawler or anything else has no way from making the screen surprise checkerboard you.  Also we don't have to do the work of releasing the old critical rect every single time endCriticalMove is called.

Comment 6

[Benjamin Stover (:stechz)]

Attachment: code review

Changed endCriticalRect to criticalRect--Mark doesn't like names that start with "on" for things that aren't actually events.

Changed add to return true when things are added instead of when it's finished.

Changed renderTile to showTile and it now is responsible for appending the tile as well.  Everything now calls showTile which maintains the responsibility of ensuring tile is not dirty => tile is appended.

Comment 7

[Benjamin Stover (:stechz)]

Comment on attachment 421658 [details] [diff] [review]
code review

Carrying froystig's r+

Comment 8

[Vivien Nicolas (:vingtetun) (:21) - (NOT reading bugmails, needinfo? please)]

Comment on attachment 421658 [details] [diff] [review]
code review

R+'ed with the correction of the ittle regression as seen on irc

Comment 9

[Benjamin Stover (:stechz)]

pushed http://hg.mozilla.org/mobile-browser/rev/df4f19ff04d4

Comment 10

[Dão Gottwald [:dao]]

bugspam