Bug 747528 - Add a PredictionBiasStrategy that uses estimated draw time to paint ahead. r=Cwiiis
authorKartikaya Gupta <kgupta@mozilla.com>
Wed, 25 Apr 2012 09:53:38 -0400
changeset 96478 be42a3881ada948400ec3b284dd1580af1697a4a
parent 96477 1aadea66098cce6177adb73ad4a5f47ce2a8d496
child 96479 cc37cd8dac5965c6465a6a9d775a75a988679028
push idunknown
push userunknown
push dateunknown
reviewersCwiiis
bugs747528
milestone15.0a1
Bug 747528 - Add a PredictionBiasStrategy that uses estimated draw time to paint ahead. r=Cwiiis
mobile/android/app/mobile.js
mobile/android/base/Makefile.in
mobile/android/base/gfx/DisplayPortCalculator.java
mobile/android/base/gfx/DisplayPortMetrics.java
mobile/android/base/gfx/DrawTimingQueue.java
mobile/android/base/gfx/GeckoLayerClient.java
--- a/mobile/android/app/mobile.js
+++ b/mobile/android/app/mobile.js
@@ -360,32 +360,34 @@ pref("places.frecency.tempRedirectVisitB
 pref("places.frecency.defaultVisitBonus", 0);
 pref("places.frecency.unvisitedBookmarkBonus", 140);
 pref("places.frecency.unvisitedTypedBonus", 200);
 
 // disable color management
 pref("gfx.color_management.mode", 0);
 
 #ifdef ANDROID
-// 0=fixed margin, 1=velocity bias, 2=dynamic resolution, 3=no margins
+// 0=fixed margin, 1=velocity bias, 2=dynamic resolution, 3=no margins, 4=prediction bias
 pref("gfx.displayport.strategy", 1);
 // all of the following displayport strategy prefs will be divided by 1000
 // to obtain some multiplier which is then used in the strategy.
 // fixed margin strategy options
 pref("gfx.displayport.strategy_fm.multiplier", -1); // displayport dimension multiplier
 pref("gfx.displayport.strategy_fm.danger_x", -1); // danger zone on x-axis when multiplied by viewport width
 pref("gfx.displayport.strategy_fm.danger_y", -1); // danger zone on y-axis when multiplied by viewport height
 // velocity bias strategy options
 pref("gfx.displayport.strategy_vb.multiplier", -1); // displayport dimension multiplier
-pref("gfx.displayport.strategy_vb.threshold", -1); // velocity threshold in pixels/frame when multiplied by screen DPI
+pref("gfx.displayport.strategy_vb.threshold", -1); // velocity threshold in inches/frame
 pref("gfx.displayport.strategy_vb.reverse_buffer", -1); // fraction of buffer to keep in reverse direction from scroll
 pref("gfx.displayport.strategy_vb.danger_x_base", -1); // danger zone on x-axis when multiplied by viewport width
 pref("gfx.displayport.strategy_vb.danger_y_base", -1); // danger zone on y-axis when multiplied by viewport height
 pref("gfx.displayport.strategy_vb.danger_x_incr", -1); // additional danger zone on x-axis when multiplied by viewport width and velocity
 pref("gfx.displayport.strategy_vb.danger_y_incr", -1); // additional danger zone on y-axis when multiplied by viewport height and velocity
+// prediction bias strategy options
+pref("gfx.displayport.strategy_pb.threshold", -1); // velocity threshold in inches/frame
 #endif
 
 // don't allow JS to move and resize existing windows
 pref("dom.disable_window_move_resize", true);
 
 // prevent click image resizing for nsImageDocument
 pref("browser.enable_click_image_resizing", false);
 
--- a/mobile/android/base/Makefile.in
+++ b/mobile/android/base/Makefile.in
@@ -119,16 +119,17 @@ FENNEC_JAVA_FILES = \
   gfx/BitmapUtils.java \
   gfx/BufferedCairoImage.java \
   gfx/CairoGLInfo.java \
   gfx/CairoImage.java \
   gfx/CairoUtils.java \
   gfx/CheckerboardImage.java \
   gfx/DisplayPortCalculator.java \
   gfx/DisplayPortMetrics.java \
+  gfx/DrawTimingQueue.java \
   gfx/FloatSize.java \
   gfx/GeckoLayerClient.java \
   gfx/GLController.java \
   gfx/ImmutableViewportMetrics.java \
   gfx/InputConnectionHandler.java \
   gfx/IntSize.java \
   gfx/Layer.java \
   gfx/LayerController.java \
--- a/mobile/android/base/gfx/DisplayPortCalculator.java
+++ b/mobile/android/base/gfx/DisplayPortCalculator.java
@@ -27,42 +27,52 @@ final class DisplayPortCalculator {
     private static final String PREF_DISPLAYPORT_FM_DANGER_Y = "gfx.displayport.strategy_fm.danger_y";
     private static final String PREF_DISPLAYPORT_VB_MULTIPLIER = "gfx.displayport.strategy_vb.multiplier";
     private static final String PREF_DISPLAYPORT_VB_VELOCITY_THRESHOLD = "gfx.displayport.strategy_vb.threshold";
     private static final String PREF_DISPLAYPORT_VB_REVERSE_BUFFER = "gfx.displayport.strategy_vb.reverse_buffer";
     private static final String PREF_DISPLAYPORT_VB_DANGER_X_BASE = "gfx.displayport.strategy_vb.danger_x_base";
     private static final String PREF_DISPLAYPORT_VB_DANGER_Y_BASE = "gfx.displayport.strategy_vb.danger_y_base";
     private static final String PREF_DISPLAYPORT_VB_DANGER_X_INCR = "gfx.displayport.strategy_vb.danger_x_incr";
     private static final String PREF_DISPLAYPORT_VB_DANGER_Y_INCR = "gfx.displayport.strategy_vb.danger_y_incr";
+    private static final String PREF_DISPLAYPORT_PB_VELOCITY_THRESHOLD = "gfx.displayport.strategy_pb.threshold";
 
     private static DisplayPortStrategy sStrategy = new VelocityBiasStrategy(null);
 
     static DisplayPortMetrics calculate(ImmutableViewportMetrics metrics, PointF velocity) {
         return sStrategy.calculate(metrics, (velocity == null ? ZERO_VELOCITY : velocity));
     }
 
     static boolean aboutToCheckerboard(ImmutableViewportMetrics metrics, PointF velocity, DisplayPortMetrics displayPort) {
         if (displayPort == null) {
             return true;
         }
         return sStrategy.aboutToCheckerboard(metrics, (velocity == null ? ZERO_VELOCITY : velocity), displayPort);
     }
 
+    static boolean drawTimeUpdate(long millis, int pixels) {
+        return sStrategy.drawTimeUpdate(millis, pixels);
+    }
+
+    static void resetPageState() {
+        sStrategy.resetPageState();
+    }
+
     static void addPrefNames(JSONArray prefs) {
         prefs.put(PREF_DISPLAYPORT_STRATEGY);
         prefs.put(PREF_DISPLAYPORT_FM_MULTIPLIER);
         prefs.put(PREF_DISPLAYPORT_FM_DANGER_X);
         prefs.put(PREF_DISPLAYPORT_FM_DANGER_Y);
         prefs.put(PREF_DISPLAYPORT_VB_MULTIPLIER);
         prefs.put(PREF_DISPLAYPORT_VB_VELOCITY_THRESHOLD);
         prefs.put(PREF_DISPLAYPORT_VB_REVERSE_BUFFER);
         prefs.put(PREF_DISPLAYPORT_VB_DANGER_X_BASE);
         prefs.put(PREF_DISPLAYPORT_VB_DANGER_Y_BASE);
         prefs.put(PREF_DISPLAYPORT_VB_DANGER_X_INCR);
         prefs.put(PREF_DISPLAYPORT_VB_DANGER_Y_INCR);
+        prefs.put(PREF_DISPLAYPORT_PB_VELOCITY_THRESHOLD);
     }
 
     /**
      * Set the active strategy to use.
      * See the gfx.displayport.strategy pref in mobile/android/app/mobile.js to see the
      * mapping between ints and strategies.
      */
     static boolean setStrategy(Map<String, Integer> prefs) {
@@ -79,34 +89,41 @@ final class DisplayPortCalculator {
                 sStrategy = new VelocityBiasStrategy(prefs);
                 break;
             case 2:
                 sStrategy = new DynamicResolutionStrategy(prefs);
                 break;
             case 3:
                 sStrategy = new NoMarginStrategy(prefs);
                 break;
+            case 4:
+                sStrategy = new PredictionBiasStrategy(prefs);
+                break;
             default:
                 Log.e(LOGTAG, "Invalid strategy index specified");
                 return false;
         }
         Log.i(LOGTAG, "Set strategy " + sStrategy.toString());
         return true;
     }
 
     private static float getFloatPref(Map<String, Integer> prefs, String prefName, int defaultValue) {
         Integer value = (prefs == null ? null : prefs.get(prefName));
         return (float)(value == null || value < 0 ? defaultValue : value) / 1000f;
     }
 
-    private interface DisplayPortStrategy {
+    private static abstract class DisplayPortStrategy {
         /** Calculates a displayport given a viewport and panning velocity. */
-        public DisplayPortMetrics calculate(ImmutableViewportMetrics metrics, PointF velocity);
+        public abstract DisplayPortMetrics calculate(ImmutableViewportMetrics metrics, PointF velocity);
         /** Returns true if a checkerboard is about to be visible and we should not throttle drawing. */
-        public boolean aboutToCheckerboard(ImmutableViewportMetrics metrics, PointF velocity, DisplayPortMetrics displayPort);
+        public abstract boolean aboutToCheckerboard(ImmutableViewportMetrics metrics, PointF velocity, DisplayPortMetrics displayPort);
+        /** Notify the strategy of a new recorded draw time. Return false to turn off draw time recording. */
+        public boolean drawTimeUpdate(long millis, int pixels) { return false; }
+        /** Reset any page-specific state stored, as the page being displayed has changed. */
+        public void resetPageState() {}
     }
 
     /**
      * Return the dimensions for a rect that has area (width*height) that does not exceed the page size in the
      * given metrics object. The area in the returned FloatSize may be less than width*height if the page is
      * small, but it will never be larger than width*height.
      * Note that this process may change the relative aspect ratio of the given dimensions.
      */
@@ -190,19 +207,30 @@ final class DisplayPortCalculator {
         } else if (bottomOverflow > 0) {
             margins.bottom -= bottomOverflow;
             margins.top += bottomOverflow;
         }
         return margins;
     }
 
     /**
+     * Clamp the given rect to the page bounds and return it.
+     */
+    private static RectF clampToPageBounds(RectF rect, ImmutableViewportMetrics metrics) {
+        rect.left = Math.max(rect.left, 0);
+        rect.top = Math.max(rect.top, 0);
+        rect.right = Math.min(rect.right, metrics.pageSizeWidth);
+        rect.bottom = Math.min(rect.bottom, metrics.pageSizeHeight);
+        return rect;
+    }
+
+    /**
      * This class implements the variation where we basically don't bother with a a display port.
      */
-    private static class NoMarginStrategy implements DisplayPortStrategy {
+    private static class NoMarginStrategy extends DisplayPortStrategy {
         NoMarginStrategy(Map<String, Integer> prefs) {
             // no prefs in this strategy
         }
 
         public DisplayPortMetrics calculate(ImmutableViewportMetrics metrics, PointF velocity) {
             return new DisplayPortMetrics(metrics.viewportRectLeft,
                     metrics.viewportRectTop,
                     metrics.viewportRectRight,
@@ -223,17 +251,17 @@ final class DisplayPortCalculator {
     /**
      * This class implements the variation where we use a fixed-size margin on the display port.
      * The margin is always 300 pixels in all directions, except when we are (a) approaching a page
      * boundary, and/or (b) if we are limited by the page size. In these cases we try to maintain
      * the area of the display port by (a) shifting the buffer to the other side on the same axis,
      * and/or (b) increasing the buffer on the other axis to compensate for the reduced buffer on
      * one axis.
      */
-    private static class FixedMarginStrategy implements DisplayPortStrategy {
+    private static class FixedMarginStrategy extends DisplayPortStrategy {
         // The length of each axis of the display port will be the corresponding view length
         // multiplied by this factor.
         private final float SIZE_MULTIPLIER;
 
         // If the visible rect is within the danger zone (measured as a fraction of the view size
         // from the edge of the displayport) we start redrawing to minimize checkerboarding.
         private final float DANGER_ZONE_X_MULTIPLIER;
         private final float DANGER_ZONE_Y_MULTIPLIER;
@@ -289,17 +317,17 @@ final class DisplayPortCalculator {
      * This class implements the variation with a small fixed-size margin with velocity bias.
      * In this variation, the default margins are pretty small relative to the view size, but
      * they are affected by the panning velocity. Specifically, if we are panning on one axis,
      * we remove the margins on the other axis because we are likely axis-locked. Also once
      * we are panning in one direction above a certain threshold velocity, we shift the buffer
      * so that it is almost entirely in the direction of the pan, with a little bit in the
      * reverse direction.
      */
-    private static class VelocityBiasStrategy implements DisplayPortStrategy {
+    private static class VelocityBiasStrategy extends DisplayPortStrategy {
         // The length of each axis of the display port will be the corresponding view length
         // multiplied by this factor.
         private final float SIZE_MULTIPLIER;
         // The velocity above which we apply the velocity bias
         private final float VELOCITY_THRESHOLD;
         // How much of the buffer to keep in the reverse direction of the velocity
         private final float REVERSE_BUFFER;
         // If the visible rect is within the danger zone we start redrawing to minimize
@@ -415,17 +443,17 @@ final class DisplayPortCalculator {
     /**
      * This class implements the variation where we draw more of the page at low resolution while panning.
      * In this variation, as we pan faster, we increase the page area we are drawing, but reduce the draw
      * resolution to compensate. This results in the same device-pixel area drawn; the compositor then
      * scales this up to the viewport zoom level. This results in a large area of the page drawn but it
      * looks blurry. The assumption is that drawing extra that we never display is better than checkerboarding,
      * where we draw less but never even show it on the screen.
      */
-    private static class DynamicResolutionStrategy implements DisplayPortStrategy {
+    private static class DynamicResolutionStrategy extends DisplayPortStrategy {
         // The length of each axis of the display port will be the corresponding view length
         // multiplied by this factor.
         private static final float SIZE_MULTIPLIER = 1.5f;
 
         // The velocity above which we start zooming out the display port to keep up
         // with the panning.
         private static final float VELOCITY_EXPANSION_THRESHOLD = GeckoAppShell.getDpi() / 16f;
 
@@ -604,9 +632,122 @@ final class DisplayPortCalculator {
             return !displayPort.contains(predictedViewport);
         }
 
         @Override
         public String toString() {
             return "DynamicResolutionStrategy";
         }
     }
+
+    /**
+     * This class implements the variation where we use the draw time to predict where we will be when
+     * a draw completes, and draw that instead of where we are now. In this variation, when our panning
+     * speed drops below a certain threshold, we draw 9 viewports' worth of content so that the user can
+     * pan in any direction without encountering checkerboarding.
+     * Once the user is panning, we modify the displayport to encompass an area range of where we think
+     * the user will be when the draw completes. This heuristic relies on both the estimated draw time
+     * the panning velocity; unexpected changes in either of these values will cause the heuristic to
+     * fail and show checkerboard.
+     */
+    private static class PredictionBiasStrategy extends DisplayPortStrategy {
+        private static float VELOCITY_THRESHOLD;
+
+        private int mPixelArea;         // area of the viewport, used in draw time calculations
+        private int mMinFramesToDraw;   // minimum number of frames we take to draw
+        private int mMaxFramesToDraw;   // maximum number of frames we take to draw
+
+        PredictionBiasStrategy(Map<String, Integer> prefs) {
+            VELOCITY_THRESHOLD = GeckoAppShell.getDpi() * getFloatPref(prefs, PREF_DISPLAYPORT_PB_VELOCITY_THRESHOLD, 16);
+            resetPageState();
+        }
+
+        public DisplayPortMetrics calculate(ImmutableViewportMetrics metrics, PointF velocity) {
+            float width = metrics.getWidth();
+            float height = metrics.getHeight();
+            mPixelArea = (int)(width * height);
+
+            if (velocity.length() < VELOCITY_THRESHOLD) {
+                // if we're going slow, expand the displayport to 9x viewport size
+                RectF margins = new RectF(width, height, width, height);
+                return getTileAlignedDisplayPortMetrics(margins, metrics.zoomFactor, metrics);
+            }
+
+            // figure out how far we expect to be
+            float minDx = velocity.x * mMinFramesToDraw;
+            float minDy = velocity.y * mMinFramesToDraw;
+            float maxDx = velocity.x * mMaxFramesToDraw;
+            float maxDy = velocity.y * mMaxFramesToDraw;
+
+            // figure out how many pixels we will be drawing when we draw the above-calculated range.
+            // this will be larger than the viewport area.
+            float pixelsToDraw = (width + Math.abs(maxDx - minDx)) * (height + Math.abs(maxDy - minDy));
+            // adjust how far we will get because of the time spent drawing all these extra pixels. this
+            // will again increase the number of pixels drawn so really we could keep iterating this over
+            // and over, but once seems enough for now.
+            maxDx = maxDx * pixelsToDraw / mPixelArea;
+            maxDy = maxDy * pixelsToDraw / mPixelArea;
+
+            // and finally generate the displayport. the min/max stuff takes care of
+            // negative velocities as well as positive.
+            RectF margins = new RectF(
+                -Math.min(minDx, maxDx),
+                -Math.min(minDy, maxDy),
+                Math.max(minDx, maxDx),
+                Math.max(minDy, maxDy));
+            return getTileAlignedDisplayPortMetrics(margins, metrics.zoomFactor, metrics);
+        }
+
+        public boolean aboutToCheckerboard(ImmutableViewportMetrics metrics, PointF velocity, DisplayPortMetrics displayPort) {
+            // the code below is the same as in calculate() but is awkward to refactor since it has multiple outputs.
+            // refer to the comments in calculate() to understand what this is doing.
+            float minDx = velocity.x * mMinFramesToDraw;
+            float minDy = velocity.y * mMinFramesToDraw;
+            float maxDx = velocity.x * mMaxFramesToDraw;
+            float maxDy = velocity.y * mMaxFramesToDraw;
+            float pixelsToDraw = (metrics.getWidth() + Math.abs(maxDx - minDx)) * (metrics.getHeight() + Math.abs(maxDy - minDy));
+            maxDx = maxDx * pixelsToDraw / mPixelArea;
+            maxDy = maxDy * pixelsToDraw / mPixelArea;
+
+            // now that we have an idea of how far we will be when the draw completes, take the farthest
+            // end of that range and see if it falls outside the displayport bounds. if it does, allow
+            // the draw to go through
+            RectF predictedViewport = metrics.getViewport();
+            predictedViewport.left += maxDx;
+            predictedViewport.top += maxDy;
+            predictedViewport.right += maxDx;
+            predictedViewport.bottom += maxDy;
+
+            predictedViewport = clampToPageBounds(predictedViewport, metrics);
+            return !displayPort.contains(predictedViewport);
+        }
+
+        @Override
+        public boolean drawTimeUpdate(long millis, int pixels) {
+            // calculate the number of frames it took to draw a viewport-sized area
+            float normalizedTime = (float)mPixelArea * (float)millis / (float)pixels;
+            int normalizedFrames = (int)FloatMath.ceil(normalizedTime * 60f / 1000f);
+            // broaden our range on how long it takes to draw if the draw falls outside
+            // the range. this allows it to grow gradually. this heuristic may need to
+            // be tweaked into more of a floating window average or something.
+            if (normalizedFrames <= mMinFramesToDraw) {
+                mMinFramesToDraw--;
+            } else if (normalizedFrames > mMaxFramesToDraw) {
+                mMaxFramesToDraw++;
+            } else {
+                return true;
+            }
+            Log.d(LOGTAG, "Widened draw range to [" + mMinFramesToDraw + ", " + mMaxFramesToDraw + "]");
+            return true;
+        }
+
+        @Override
+        public void resetPageState() {
+            mMinFramesToDraw = 0;
+            mMaxFramesToDraw = 2;
+        }
+
+        @Override
+        public String toString() {
+            return "PredictionBiasStrategy threshold=" + VELOCITY_THRESHOLD;
+        }
+    }
 }
--- a/mobile/android/base/gfx/DisplayPortMetrics.java
+++ b/mobile/android/base/gfx/DisplayPortMetrics.java
@@ -1,16 +1,17 @@
 /* -*- Mode: Java; c-basic-offset: 4; tab-width: 20; indent-tabs-mode: nil; -*-
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
  * You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 package org.mozilla.gecko.gfx;
 
 import android.graphics.RectF;
+import org.mozilla.gecko.FloatUtils;
 
 /*
  * This class keeps track of the area we request Gecko to paint, as well
  * as the resolution of the paint. The area may be different from the visible
  * area of the page, and the resolution may be different from the resolution
  * used in the compositor to render the page. This is so that we can ask Gecko
  * to paint a much larger area without using extra memory, and then render some
  * subsection of that with compositor scaling.
@@ -27,16 +28,21 @@ public final class DisplayPortMetrics {
         mPosition = new RectF(left, top, right, bottom);
         mResolution = resolution;
     }
 
     public boolean contains(RectF rect) {
         return mPosition.contains(rect);
     }
 
+    public boolean fuzzyEquals(DisplayPortMetrics metrics) {
+        return RectUtils.fuzzyEquals(mPosition, metrics.mPosition)
+            && FloatUtils.fuzzyEquals(mResolution, metrics.mResolution);
+    }
+
     public String toJSON() {
         StringBuffer sb = new StringBuffer(256);
         sb.append("{ \"left\": ").append(mPosition.left)
           .append(", \"top\": ").append(mPosition.top)
           .append(", \"right\": ").append(mPosition.right)
           .append(", \"bottom\": ").append(mPosition.bottom)
           .append(", \"resolution\": ").append(mResolution)
           .append('}');
new file mode 100644
--- /dev/null
+++ b/mobile/android/base/gfx/DrawTimingQueue.java
@@ -0,0 +1,95 @@
+/* -*- Mode: Java; c-basic-offset: 4; tab-width: 20; indent-tabs-mode: nil; -*-
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+package org.mozilla.gecko.gfx;
+
+import android.os.SystemClock;
+
+/**
+ * A custom-built data structure to assist with measuring draw times.
+ *
+ * This class maintains a fixed-size circular buffer of DisplayPortMetrics
+ * objects and associated timestamps. It provides only three operations, which
+ * is all we require for our purposes of measuring draw times. Note
+ * in particular that the class is designed so that even though it is
+ * accessed from multiple threads, it does not require synchronization;
+ * any concurrency errors that result from this are handled gracefully.
+ *
+ * Assuming an unrolled buffer so that mTail is greater than mHead, the data
+ * stored in the buffer at entries [mHead, mTail) will never be modified, and
+ * so are "safe" to read. If this reading is done on the same thread that
+ * owns mHead, then reading the range [mHead, mTail) is guaranteed to be safe
+ * since the range itself will not shrink.
+ */
+final class DrawTimingQueue {
+    private static final String LOGTAG = "GeckoDrawTimingQueue";
+    private static final int BUFFER_SIZE = 16;
+
+    private final DisplayPortMetrics[] mMetrics;
+    private final long[] mTimestamps;
+
+    private int mHead;
+    private int mTail;
+
+    DrawTimingQueue() {
+        mMetrics = new DisplayPortMetrics[BUFFER_SIZE];
+        mTimestamps = new long[BUFFER_SIZE];
+        mHead = BUFFER_SIZE - 1;
+        mTail = 0;
+    }
+
+    /**
+     * Add a new entry to the tail of the queue. If the buffer is full,
+     * do nothing. This must only be called from the Java UI thread.
+     */
+    boolean add(DisplayPortMetrics metrics) {
+        if (mHead == mTail) {
+            return false;
+        }
+        mMetrics[mTail] = metrics;
+        mTimestamps[mTail] = SystemClock.uptimeMillis();
+        mTail = (mTail + 1) % BUFFER_SIZE;
+        return true;
+    }
+
+    /**
+     * Find the timestamp associated with the given metrics, AND remove
+     * all metrics objects from the start of the queue up to and including
+     * the one provided. Note that because of draw coalescing, the metrics
+     * object passed in here may not be the one at the head of the queue,
+     * and so we must iterate our way through the list to find it.
+     * This must only be called from the compositor thread.
+     */
+    long findTimeFor(DisplayPortMetrics metrics) {
+        // keep a copy of the tail pointer so that we ignore new items
+        // added to the queue while we are searching. this is fine because
+        // the one we are looking for will either have been added already
+        // or will not be in the queue at all.
+        int tail = mTail;
+        // walk through the "safe" range from mHead to tail; these entries
+        // will not be modified unless we change mHead.
+        int i = (mHead + 1) % BUFFER_SIZE;
+        while (i != tail) {
+            if (mMetrics[i].fuzzyEquals(metrics)) {
+                // found it, copy out the timestamp to a local var BEFORE
+                // changing mHead or add could clobber the timestamp.
+                long timestamp = mTimestamps[i];
+                mHead = i;
+                return timestamp;
+            }
+            i = (i + 1) % BUFFER_SIZE;
+        }
+        return -1;
+    }
+
+    /**
+     * Reset the buffer to empty.
+     * This must only be called from the compositor thread.
+     */
+    void reset() {
+        // we can only modify mHead on this thread.
+        mHead = (mTail + BUFFER_SIZE - 1) % BUFFER_SIZE;
+    }
+}
--- a/mobile/android/base/gfx/GeckoLayerClient.java
+++ b/mobile/android/base/gfx/GeckoLayerClient.java
@@ -69,16 +69,19 @@ public class GeckoLayerClient implements
     private LayerRenderer mLayerRenderer;
     private boolean mLayerRendererInitialized;
 
     private IntSize mScreenSize;
     private IntSize mWindowSize;
     private DisplayPortMetrics mDisplayPort;
     private DisplayPortMetrics mReturnDisplayPort;
 
+    private boolean mRecordDrawTimes;
+    private DrawTimingQueue mDrawTimingQueue;
+
     private VirtualLayer mRootLayer;
 
     /* The Gecko viewport as per the UI thread. Must be touched only on the UI thread. */
     private ViewportMetrics mGeckoViewport;
 
     /*
      * The viewport metrics being used to draw the current frame. This is only
      * accessed by the compositor thread, and so needs no synchronisation.
@@ -94,16 +97,18 @@ public class GeckoLayerClient implements
     private ViewTransform mCurrentViewTransform;
 
     public GeckoLayerClient(Context context) {
         // we can fill these in with dummy values because they are always written
         // to before being read
         mScreenSize = new IntSize(0, 0);
         mWindowSize = new IntSize(0, 0);
         mDisplayPort = new DisplayPortMetrics();
+        mRecordDrawTimes = true;
+        mDrawTimingQueue = new DrawTimingQueue();
         mCurrentViewTransform = new ViewTransform(0, 0, 1);
     }
 
     /** Attaches the root layer to the layer controller so that Gecko appears. */
     void setLayerController(LayerController layerController) {
         LayerView view = layerController.getView();
 
         mLayerController = layerController;
@@ -188,16 +193,20 @@ public class GeckoLayerClient implements
         if (displayPort == null) {
             displayPort = DisplayPortCalculator.calculate(metrics,
                     mLayerController.getPanZoomController().getVelocityVector());
         }
 
         mDisplayPort = displayPort;
         mGeckoViewport = clampedMetrics;
 
+        if (mRecordDrawTimes) {
+            mDrawTimingQueue.add(displayPort);
+        }
+
         GeckoAppShell.sendEventToGecko(GeckoEvent.createViewportEvent(clampedMetrics, displayPort));
     }
 
     /**
      * The different types of Viewport messages handled. All viewport events
      * expect a display-port to be returned, but can handle one not being
      * returned.
      */
@@ -337,16 +346,18 @@ public class GeckoLayerClient implements
             // that are in progress and send an updated display port request to browser.js as soon
             // as possible. We accomplish this by passing true to abortPanZoomAnimation, which
             // sends the request after aborting the animation. The display port request is actually
             // a full viewport update, which is fine because if browser.js has somehow moved to
             // be out of sync with this first-paint viewport, then we force them back in sync.
             mLayerController.abortPanZoomAnimation();
             mLayerController.getView().setPaintState(LayerView.PAINT_BEFORE_FIRST);
         }
+        DisplayPortCalculator.resetPageState();
+        mDrawTimingQueue.reset();
         mLayerController.getView().getRenderer().resetCheckerboard();
         GeckoAppShell.screenshotWholePage(Tabs.getInstance().getSelectedTab());
     }
 
     /** This function is invoked by Gecko via JNI; be careful when modifying signature.
       * The compositor invokes this function whenever it determines that the page size
       * has changed (based on the information it gets from layout). If setFirstPaintViewport
       * is invoked on a frame, then this function will not be. For any given frame, this
@@ -388,16 +399,29 @@ public class GeckoLayerClient implements
         mFrameMetrics = mLayerController.getViewportMetrics();
 
         mCurrentViewTransform.x = mFrameMetrics.viewportRectLeft;
         mCurrentViewTransform.y = mFrameMetrics.viewportRectTop;
         mCurrentViewTransform.scale = mFrameMetrics.zoomFactor;
 
         mRootLayer.setPositionAndResolution(x, y, x + width, y + height, resolution);
 
+        if (layersUpdated && mRecordDrawTimes) {
+            // If we got a layers update, that means a draw finished. Check to see if the area drawn matches
+            // one of our requested displayports; if it does calculate the draw time and notify the
+            // DisplayPortCalculator
+            DisplayPortMetrics drawn = new DisplayPortMetrics(x, y, x + width, y + height, resolution);
+            long time = mDrawTimingQueue.findTimeFor(drawn);
+            if (time >= 0) {
+                long now = SystemClock.uptimeMillis();
+                time = now - time;
+                mRecordDrawTimes = DisplayPortCalculator.drawTimeUpdate(time, width * height);
+            }
+        }
+
         if (layersUpdated && mDrawListener != null) {
             /* Used by robocop for testing purposes */
             mDrawListener.drawFinished();
         }
 
         return mCurrentViewTransform;
     }