Bug 1119774 (Part 5) - Add SurfaceCache::LookupBestMatch. r=dholbert a=lmandel
authorSeth Fowler <seth@mozilla.com>
Sun, 18 Jan 2015 14:02:14 -0800
changeset 249820 fb6a943ca2a581a28858ba7d1128882fe903676d
parent 249819 5a8f7b74bf5573585f2840d338a4aaee2537e2bc
child 249821 d6163bef24faa0518bb1306156cb6e4ef09d0acc
push id4489
push userraliiev@mozilla.com
push dateMon, 23 Feb 2015 15:17:55 +0000
treeherdermozilla-beta@fd7c3dc24146 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdholbert, lmandel
bugs1119774
milestone37.0a2
Bug 1119774 (Part 5) - Add SurfaceCache::LookupBestMatch. r=dholbert a=lmandel
image/src/SurfaceCache.cpp
image/src/SurfaceCache.h
--- a/image/src/SurfaceCache.cpp
+++ b/image/src/SurfaceCache.cpp
@@ -243,25 +243,111 @@ public:
 
   already_AddRefed<CachedSurface> Lookup(const SurfaceKey& aSurfaceKey)
   {
     nsRefPtr<CachedSurface> surface;
     mSurfaces.Get(aSurfaceKey, getter_AddRefs(surface));
     return surface.forget();
   }
 
+  already_AddRefed<CachedSurface>
+  LookupBestMatch(const SurfaceKey&      aSurfaceKey,
+                  const Maybe<uint32_t>& aAlternateFlags)
+  {
+    // Try for a perfect match first.
+    nsRefPtr<CachedSurface> surface;
+    mSurfaces.Get(aSurfaceKey, getter_AddRefs(surface));
+    if (surface) {
+      return surface.forget();
+    }
+
+    // There's no perfect match, so find the best match we can.
+    MatchContext matchContext(aSurfaceKey, aAlternateFlags);
+    ForEach(TryToImproveMatch, &matchContext);
+    return matchContext.mBestMatch.forget();
+  }
+
   void ForEach(SurfaceTable::EnumReadFunction aFunction, void* aData)
   {
     mSurfaces.EnumerateRead(aFunction, aData);
   }
 
   void SetLocked(bool aLocked) { mLocked = aLocked; }
   bool IsLocked() const { return mLocked; }
 
 private:
+  struct MatchContext
+  {
+    MatchContext(const SurfaceKey& aIdealKey,
+                 const Maybe<uint32_t>& aAlternateFlags)
+      : mIdealKey(aIdealKey)
+      , mAlternateFlags(aAlternateFlags)
+    { }
+
+    const SurfaceKey& mIdealKey;
+    const Maybe<uint32_t> mAlternateFlags;
+    nsRefPtr<CachedSurface> mBestMatch;
+  };
+
+  static PLDHashOperator TryToImproveMatch(const SurfaceKey& aSurfaceKey,
+                                           CachedSurface*    aSurface,
+                                           void*             aContext)
+  {
+    auto context = static_cast<MatchContext*>(aContext);
+    const SurfaceKey& idealKey = context->mIdealKey;
+
+    // Matching the animation time and SVG context is required.
+    if (aSurfaceKey.AnimationTime() != idealKey.AnimationTime() ||
+        aSurfaceKey.SVGContext() != idealKey.SVGContext()) {
+      return PL_DHASH_NEXT;
+    }
+
+    // Matching the flags is required, but we can match the alternate flags as
+    // well if some were provided.
+    if (aSurfaceKey.Flags() != idealKey.Flags() &&
+        Some(aSurfaceKey.Flags()) != context->mAlternateFlags) {
+      return PL_DHASH_NEXT;
+    }
+
+    // Anything is better than nothing! (Within the constraints we just
+    // checked, of course.)
+    if (!context->mBestMatch) {
+      context->mBestMatch = aSurface;
+      return PL_DHASH_NEXT;
+    }
+
+    MOZ_ASSERT(context->mBestMatch, "Should have a current best match");
+    SurfaceKey bestMatchKey = context->mBestMatch->GetSurfaceKey();
+
+    // Compare sizes. We use an area-based heuristic here instead of computing a
+    // truly optimal answer, since it seems very unlikely to make a difference
+    // for realistic sizes.
+    int64_t idealArea = idealKey.Size().width * idealKey.Size().height;
+    int64_t surfaceArea = aSurfaceKey.Size().width * aSurfaceKey.Size().height;
+    int64_t bestMatchArea =
+      bestMatchKey.Size().width * bestMatchKey.Size().height;
+
+    // If the best match is smaller than the ideal size, prefer bigger sizes.
+    if (bestMatchArea < idealArea) {
+      if (surfaceArea > bestMatchArea) {
+        context->mBestMatch = aSurface;
+      }
+      return PL_DHASH_NEXT;
+    }
+
+    // Other, prefer sizes closer to the ideal size, but still not smaller.
+    if (idealArea <= surfaceArea && surfaceArea < bestMatchArea) {
+      context->mBestMatch = aSurface;
+      return PL_DHASH_NEXT;
+    }
+
+    // This surface isn't an improvement over the current best match.
+    return PL_DHASH_NEXT;
+  }
+
   SurfaceTable mSurfaces;
   bool         mLocked;
 };
 
 /**
  * SurfaceCacheImpl is responsible for determining which surfaces will be cached
  * and managing the surface cache data structures. Rather than interact with
  * SurfaceCacheImpl directly, client code interacts with SurfaceCache, which
@@ -448,16 +534,55 @@ public:
 
     if (!surface->IsLocked()) {
       mExpirationTracker.MarkUsed(surface);
     }
 
     return ref;
   }
 
+  DrawableFrameRef LookupBestMatch(const ImageKey         aImageKey,
+                                   const SurfaceKey&      aSurfaceKey,
+                                   const Maybe<uint32_t>& aAlternateFlags)
+  {
+    nsRefPtr<ImageSurfaceCache> cache = GetImageCache(aImageKey);
+    if (!cache)
+      return DrawableFrameRef();  // No cached surfaces for this image.
+
+    // Repeatedly look up the best match, trying again if the resulting surface
+    // has been freed by the operating system, until we can either lock a
+    // surface for drawing or there are no matching surfaces left.
+    // XXX(seth): This is O(N^2), but N is expected to be very small. If we
+    // encounter a performance problem here we can revisit this.
+
+    nsRefPtr<CachedSurface> surface;
+    DrawableFrameRef ref;
+    while (true) {
+      surface = cache->LookupBestMatch(aSurfaceKey, aAlternateFlags);
+      if (!surface) {
+        return DrawableFrameRef();  // Lookup in the per-image cache missed.
+      }
+
+      ref = surface->DrawableRef();
+      if (ref) {
+        break;
+      }
+
+      // The surface was released by the operating system. Remove the cache
+      // entry as well.
+      Remove(surface);
+    }
+
+    if (!surface->IsLocked()) {
+      mExpirationTracker.MarkUsed(surface);
+    }
+
+    return ref;
+  }
+
   void RemoveSurface(const ImageKey    aImageKey,
                      const SurfaceKey& aSurfaceKey)
   {
     nsRefPtr<ImageSurfaceCache> cache = GetImageCache(aImageKey);
     if (!cache)
       return;  // No cached surfaces for this image.
 
     nsRefPtr<CachedSurface> surface = cache->Lookup(aSurfaceKey);
@@ -801,16 +926,30 @@ SurfaceCache::Lookup(const ImageKey     
   if (!ref && aAlternateFlags) {
     ref = sInstance->Lookup(aImageKey,
                             aSurfaceKey.WithNewFlags(*aAlternateFlags));
   }
 
   return ref;
 }
 
+/* static */ DrawableFrameRef
+SurfaceCache::LookupBestMatch(const ImageKey         aImageKey,
+                              const SurfaceKey&      aSurfaceKey,
+                              const Maybe<uint32_t>& aAlternateFlags
+                                /* = Nothing() */)
+{
+  if (!sInstance) {
+    return DrawableFrameRef();
+  }
+
+  MutexAutoLock lock(sInstance->GetMutex());
+  return sInstance->LookupBestMatch(aImageKey, aSurfaceKey, aAlternateFlags);
+}
+
 /* static */ InsertOutcome
 SurfaceCache::Insert(imgFrame*         aSurface,
                      const ImageKey    aImageKey,
                      const SurfaceKey& aSurfaceKey,
                      Lifetime          aLifetime)
 {
   if (!sInstance) {
     return InsertOutcome::FAILURE;
--- a/image/src/SurfaceCache.h
+++ b/image/src/SurfaceCache.h
@@ -58,16 +58,19 @@ public:
   {
     uint32_t hash = HashGeneric(mSize.width, mSize.height);
     hash = AddToHash(hash, mSVGContext.map(HashSIC).valueOr(0));
     hash = AddToHash(hash, mAnimationTime, mFlags);
     return hash;
   }
 
   IntSize Size() const { return mSize; }
+  Maybe<SVGImageContext> SVGContext() const { return mSVGContext; }
+  float AnimationTime() const { return mAnimationTime; }
+  uint32_t Flags() const { return mFlags; }
 
   SurfaceKey WithNewFlags(uint32_t aFlags) const
   {
     return SurfaceKey(mSize, mSVGContext, mAnimationTime, aFlags);
   }
 
 private:
   SurfaceKey(const IntSize& aSize,
@@ -186,16 +189,38 @@ struct SurfaceCache
    *         or an empty DrawableFrameRef if not found.
    */
   static DrawableFrameRef Lookup(const ImageKey    aImageKey,
                                  const SurfaceKey& aSurfaceKey,
                                  const Maybe<uint32_t>& aAlternateFlags
                                    = Nothing());
 
   /**
+   * Looks up the best matching surface in the cache and returns a drawable
+   * reference to the imgFrame containing it.
+   *
+   * Returned surfaces may vary from the requested surface only in terms of
+   * size, unless @aAlternateFlags is specified.
+   *
+   * @param aImageKey    Key data identifying which image the surface belongs to.
+   * @param aSurfaceKey  Key data which identifies the ideal surface to return.
+   * @param aAlternateFlags If not Nothing(), a different set of flags than the
+   *                        ones specified in @aSurfaceKey which are also
+   *                        acceptable to the caller. This is much more
+   *                        efficient than calling LookupBestMatch() twice.
+   *
+   * @return a DrawableFrameRef to the imgFrame wrapping a surface similar to
+   *         the requested surface, or an empty DrawableFrameRef if not found.
+   */
+  static DrawableFrameRef LookupBestMatch(const ImageKey    aImageKey,
+                                          const SurfaceKey& aSurfaceKey,
+                                          const Maybe<uint32_t>& aAlternateFlags
+                                            = Nothing());
+
+  /**
    * Insert a surface into the cache. If a surface with the same ImageKey and
    * SurfaceKey is already in the cache, Insert returns FAILURE_ALREADY_PRESENT.
    *
    * Each surface in the cache has a lifetime, either Transient or Persistent.
    * Transient surfaces can expire from the cache at any time. Persistent
    * surfaces can ordinarily also expire from the cache at any time, but if the
    * image they're associated with is locked, then these surfaces will never
    * expire. This means that surfaces which cannot be rematerialized should be