Optimized kerning and ligatures using caching
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 8 Nov 2012 19:06:02 +0000 (19:06 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 8 Nov 2012 19:06:02 +0000 (19:06 +0000)
https://bugs.webkit.org/show_bug.cgi?id=101269

Reviewed by Dan Bernstein.

Consider three kinds of text layout, and the value of caching for each:

    (1) 1 layout of 100% unique words: small negative value.

    (2) 1 layout of English prose: medium positive value.

    (3) Many layouts of anything: extra-extra-large positive value.

Since we can't distinguish betwen these workflows a priori, we use statistical
sampling. To minimize cost in (1) and maximize benefit in (2) and (3), we treat
each cache access as a statistical sample, and use the cache in proportion to
the observed probability of duplicate text measurement.

Benchmark results:
    plt3: 1% faster
    chapter-reflow-once-random: No change [*]
    chapter-reflow-once: 23% faster
    chapter-reflow-twice: 52% faster
    chapter-reflow-thrice: 68% faster
    chapter-reflow: 263% faster
    line-layout: 270% faster

    [*] This is a stress test designed to make everything go wrong for
    caching. It does not represent real world content.

* GNUmakefile.list.am:
* Target.pri:
* WebCore.vcproj/WebCore.vcproj:
* WebCore.xcodeproj/project.pbxproj:
* platform/graphics/WidthCache.h: Added.

(WidthCache): Added a class that caches common word widths. This cache
could cache more things or more cases in future -- but for now it seems
to cover the common cases.

(SmallStringKey): Early profiling showed that allocating an AtomicString
or String measurably added to the cost of the cache, so I added a custom
string key that can be stored directly inside the table by value --
empirically answering an age-old question with which Apple WebKit engineers
seem to be obsessed.

(WebCore::WidthCache::SmallStringKey::capacity):
(WebCore::WidthCache::SmallStringKey::SmallStringKey):
(WebCore::WidthCache::SmallStringKey::characters):
(WebCore::WidthCache::SmallStringKey::length):
(WebCore::WidthCache::SmallStringKey::hash):
(WebCore::WidthCache::SmallStringKey::isHashTableDeletedValue):
(WebCore::WidthCache::SmallStringKey::isHashTableEmptyValue):
(WebCore::WidthCache::SmallStringKeyHash::hash):
(WebCore::WidthCache::SmallStringKeyHash::equal):
(SmallStringKeyHash):
(SmallStringKeyHashTraits):
(WebCore::WidthCache::SmallStringKeyHashTraits::isEmptyValue): Ditto.

(WebCore::WidthCache::WidthCache):
(WebCore::WidthCache::add): Separate out the "don't use the cache" case
so the compiler can inline it separate, hopefully further reducing cases
of (1).

(WebCore::WidthCache::addSlowCase): There's a little subtlety to the
sampling policy here. Lots of different approaches are possible, and I
just picked a simple one that seemed to work based on benchmarking. I'll
point out some interesting sublteties I'm aware of here:

    (*) Since we start at the min sampling rate, a font used for 20 words
    or fewer never allocates a cache. Anecdotally, some fonts seem to
    be used this way.

    (*) When the sampling rate is x / y, sampling all x words in a row
    seems smart because some words may occur more commonly in relation to
    each other (such as 'each' and 'other'), and repeat workloads will
    lay out the same words in order. Intuitively, these are both reasons
    this policy may ramp up more effectively under load.

    (*) I opted for linear back-off instead of, say, exponential back-off
    because we're not trying to back off to infinity -- just to our min
    sampling rate. Since we don't expect the cache to hit for every word,
    my guess is that exponential back-off would be too aggressive.

    (*) Our "eviction" policy has an IQ of 1. I expect this is sufficient
    because it would be surprising to see a million unique words all used
    in the same document. (I would not like to play a Letterpress game
    against such a document.)

(WebCore::WidthCache::clear): Needed because a font can change, in which
case we need to ditch its cache.

(WebCore::operator==): Needed for hashing.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@133921 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/GNUmakefile.list.am
Source/WebCore/Target.pri
Source/WebCore/WebCore.vcproj/WebCore.vcproj
Source/WebCore/WebCore.xcodeproj/project.pbxproj
Source/WebCore/platform/graphics/Font.cpp
Source/WebCore/platform/graphics/FontFallbackList.cpp
Source/WebCore/platform/graphics/FontFallbackList.h
Source/WebCore/platform/graphics/WidthCache.h [new file with mode: 0644]

index b513010..93cfb1a 100644 (file)
@@ -1,3 +1,99 @@
+2012-11-05  Geoffrey Garen  <ggaren@apple.com>
+
+        Optimized kerning and ligatures using caching
+        https://bugs.webkit.org/show_bug.cgi?id=101269
+
+        Reviewed by Dan Bernstein.
+
+        Consider three kinds of text layout, and the value of caching for each:
+
+            (1) 1 layout of 100% unique words: small negative value.
+
+            (2) 1 layout of English prose: medium positive value.
+
+            (3) Many layouts of anything: extra-extra-large positive value.
+
+        Since we can't distinguish betwen these workflows a priori, we use statistical
+        sampling. To minimize cost in (1) and maximize benefit in (2) and (3), we treat
+        each cache access as a statistical sample, and use the cache in proportion to
+        the observed probability of duplicate text measurement.
+
+        Benchmark results:
+            plt3: 1% faster
+            chapter-reflow-once-random: No change [*]
+            chapter-reflow-once: 23% faster
+            chapter-reflow-twice: 52% faster
+            chapter-reflow-thrice: 68% faster
+            chapter-reflow: 263% faster
+            line-layout: 270% faster
+
+            [*] This is a stress test designed to make everything go wrong for
+            caching. It does not represent real world content.
+
+        * GNUmakefile.list.am:
+        * Target.pri:
+        * WebCore.vcproj/WebCore.vcproj:
+        * WebCore.xcodeproj/project.pbxproj:
+        * platform/graphics/WidthCache.h: Added.
+
+        (WidthCache): Added a class that caches common word widths. This cache
+        could cache more things or more cases in future -- but for now it seems
+        to cover the common cases.
+
+        (SmallStringKey): Early profiling showed that allocating an AtomicString
+        or String measurably added to the cost of the cache, so I added a custom
+        string key that can be stored directly inside the table by value --
+        empirically answering an age-old question with which Apple WebKit engineers
+        seem to be obsessed.
+
+        (WebCore::WidthCache::SmallStringKey::capacity):
+        (WebCore::WidthCache::SmallStringKey::SmallStringKey):
+        (WebCore::WidthCache::SmallStringKey::characters):
+        (WebCore::WidthCache::SmallStringKey::length):
+        (WebCore::WidthCache::SmallStringKey::hash):
+        (WebCore::WidthCache::SmallStringKey::isHashTableDeletedValue):
+        (WebCore::WidthCache::SmallStringKey::isHashTableEmptyValue):
+        (WebCore::WidthCache::SmallStringKeyHash::hash):
+        (WebCore::WidthCache::SmallStringKeyHash::equal):
+        (SmallStringKeyHash):
+        (SmallStringKeyHashTraits):
+        (WebCore::WidthCache::SmallStringKeyHashTraits::isEmptyValue): Ditto.
+
+        (WebCore::WidthCache::WidthCache):
+        (WebCore::WidthCache::add): Separate out the "don't use the cache" case
+        so the compiler can inline it separate, hopefully further reducing cases
+        of (1).
+
+        (WebCore::WidthCache::addSlowCase): There's a little subtlety to the
+        sampling policy here. Lots of different approaches are possible, and I
+        just picked a simple one that seemed to work based on benchmarking. I'll
+        point out some interesting sublteties I'm aware of here:
+
+            (*) Since we start at the min sampling rate, a font used for 20 words
+            or fewer never allocates a cache. Anecdotally, some fonts seem to
+            be used this way.
+
+            (*) When the sampling rate is x / y, sampling all x words in a row
+            seems smart because some words may occur more commonly in relation to
+            each other (such as 'each' and 'other'), and repeat workloads will
+            lay out the same words in order. Intuitively, these are both reasons
+            this policy may ramp up more effectively under load.
+
+            (*) I opted for linear back-off instead of, say, exponential back-off
+            because we're not trying to back off to infinity -- just to our min
+            sampling rate. Since we don't expect the cache to hit for every word,
+            my guess is that exponential back-off would be too aggressive.
+
+            (*) Our "eviction" policy has an IQ of 1. I expect this is sufficient
+            because it would be surprising to see a million unique words all used
+            in the same document. (I would not like to play a Letterpress game
+            against such a document.)
+
+        (WebCore::WidthCache::clear): Needed because a font can change, in which
+        case we need to ditch its cache.
+
+        (WebCore::operator==): Needed for hashing.
+
 2012-11-08  Andrey Kosyakov  <caseq@chromium.org>
 
         Web Inspector: show statistics over selected frame range in Timeline's Frame mode
index 8e4899a..fa6bb12 100644 (file)
@@ -4559,6 +4559,7 @@ webcore_sources += \
        Source/WebCore/platform/graphics/transforms/TranslateTransformOperation.h \
        Source/WebCore/platform/graphics/TypesettingFeatures.h \
        Source/WebCore/platform/graphics/UnitBezier.h \
+       Source/WebCore/platform/graphics/WidthCache.h \
        Source/WebCore/platform/graphics/WidthIterator.cpp \
        Source/WebCore/platform/graphics/WidthIterator.h \
        Source/WebCore/platform/graphics/WindRule.h \
index 9a29cef..3bd4619 100644 (file)
@@ -2186,6 +2186,7 @@ HEADERS += \
     platform/graphics/transforms/TransformState.h \
     platform/graphics/transforms/TranslateTransformOperation.h \
     platform/graphics/WidthIterator.h \
+    platform/graphics/WidthCache.h \
     platform/image-decoders/bmp/BMPImageDecoder.h \
     platform/image-decoders/bmp/BMPImageReader.h \
     platform/image-decoders/ico/ICOImageDecoder.h \
index 4c966fe..fd56b51 100755 (executable)
                                        >
                                </File>
                                <File
+                                       RelativePath="..\platform\graphics\WidthCache.h"
+                                       >
+                               </File>
+                               <File
                                        RelativePath="..\platform\graphics\WidthIterator.cpp"
                                        >
                                </File>
index c69c26c..7c724e4 100644 (file)
                14115B5209F84B7100CA4FC1 /* Node.h in Headers */ = {isa = PBXBuildFile; fileRef = 14115B5109F84B7100CA4FC1 /* Node.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14115B7209F84CD600CA4FC1 /* JSNodeFilter.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14115B7009F84CD600CA4FC1 /* JSNodeFilter.cpp */; };
                14115B7309F84CD600CA4FC1 /* JSNodeFilter.h in Headers */ = {isa = PBXBuildFile; fileRef = 14115B7109F84CD600CA4FC1 /* JSNodeFilter.h */; };
+               1411DCB1164C39A800D49BC1 /* WidthCache.h in Headers */ = {isa = PBXBuildFile; fileRef = 1411DCB0164C39A800D49BC1 /* WidthCache.h */; };
                1419D2C50CEA6F6100FF507A /* TreeShared.h in Headers */ = {isa = PBXBuildFile; fileRef = 1419D2C40CEA6F6100FF507A /* TreeShared.h */; settings = {ATTRIBUTES = (Private, ); }; };
                141DC0481648348F00371E5A /* LayoutUnit.h in Headers */ = {isa = PBXBuildFile; fileRef = 141DC0471648348F00371E5A /* LayoutUnit.h */; settings = {ATTRIBUTES = (Private, ); }; };
                141DC04F164834B900371E5A /* LayoutBoxExtent.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 141DC049164834B900371E5A /* LayoutBoxExtent.cpp */; };
                14115B5109F84B7100CA4FC1 /* Node.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = Node.h; sourceTree = "<group>"; };
                14115B7009F84CD600CA4FC1 /* JSNodeFilter.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = JSNodeFilter.cpp; sourceTree = "<group>"; };
                14115B7109F84CD600CA4FC1 /* JSNodeFilter.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = JSNodeFilter.h; sourceTree = "<group>"; };
+               1411DCB0164C39A800D49BC1 /* WidthCache.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WidthCache.h; sourceTree = "<group>"; };
                1419D2C40CEA6F6100FF507A /* TreeShared.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TreeShared.h; sourceTree = "<group>"; };
                141B94E509EC4223000E9413 /* MouseEvent.idl */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = text; path = MouseEvent.idl; sourceTree = "<group>"; };
                141B94EE09EC425A000E9413 /* UIEvent.idl */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = text; path = UIEvent.idl; sourceTree = "<group>"; };
                                1AF89A411518FDEA00E547B5 /* TiledBacking.h */,
                                37C28A6710F659CC008C7813 /* TypesettingFeatures.h */,
                                E4AFCFA40DAF29A300F5F55C /* UnitBezier.h */,
+                               1411DCB0164C39A800D49BC1 /* WidthCache.h */,
                                939B02EC0EA2DBC400C54570 /* WidthIterator.cpp */,
                                939B02ED0EA2DBC400C54570 /* WidthIterator.h */,
                                501BAAA813950E2C00F7ACEB /* WindRule.h */,
                                3FFFF9A9159D9A550020BBD5 /* WebKitCSSViewportRule.h in Headers */,
                                93C38BFF164473C700091EB2 /* ScrollingStateFixedNode.h in Headers */,
                                93C38C03164473DD00091EB2 /* ScrollingTreeFixedNode.h in Headers */,
+                               1411DCB1164C39A800D49BC1 /* WidthCache.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
index b3bf322..0f32e49 100644 (file)
@@ -198,13 +198,29 @@ float Font::width(const TextRun& run, HashSet<const SimpleFontData*>* fallbackFo
 {
     CodePath codePathToUse = codePath(run);
     if (codePathToUse != Complex) {
-        // If the complex text implementation cannot return fallback fonts, avoid
-        // returning them for simple text as well.
-        static bool returnFallbackFonts = canReturnFallbackFontsForComplexText();
-        return floatWidthForSimpleText(run, returnFallbackFonts ? fallbackFonts : 0, codePathToUse == SimpleWithGlyphOverflow || (glyphOverflow && glyphOverflow->computeBounds) ? glyphOverflow : 0);
+        // The complex path is more restrictive about returning fallback fonts than the simple path, so we need an explicit test to make their behaviors match.
+        if (!canReturnFallbackFontsForComplexText())
+            fallbackFonts = 0;
+        // The simple path can optimize the case where glyph overflow is not observable.
+        if (codePathToUse != SimpleWithGlyphOverflow && (glyphOverflow && !glyphOverflow->computeBounds))
+            glyphOverflow = 0;
     }
 
-    return floatWidthForComplexText(run, fallbackFonts, glyphOverflow);
+    bool hasKerningOrLigatures = typesettingFeatures() & (Kerning | Ligatures);
+    bool hasWordSpacingOrLetterSpacing = wordSpacing() | letterSpacing();
+    float* cacheEntry = m_fontFallbackList->widthCache().add(run, std::numeric_limits<float>::quiet_NaN(), hasKerningOrLigatures, hasWordSpacingOrLetterSpacing, glyphOverflow);
+    if (cacheEntry && !isnan(*cacheEntry))
+        return *cacheEntry;
+
+    float result;
+    if (codePathToUse == Complex)
+        result = floatWidthForComplexText(run, fallbackFonts, glyphOverflow);
+    else
+        result = floatWidthForSimpleText(run, fallbackFonts, glyphOverflow);
+
+    if (cacheEntry && (!fallbackFonts || fallbackFonts->isEmpty()))
+        *cacheEntry = result;
+    return result;
 }
 
 float Font::width(const TextRun& run, int& charsConsumed, String& glyphName) const
index 74ab726..3741714 100644 (file)
@@ -60,6 +60,7 @@ void FontFallbackList::invalidate(PassRefPtr<FontSelector> fontSelector)
     m_fontSelector = fontSelector;
     m_fontSelectorVersion = m_fontSelector ? m_fontSelector->version() : 0;
     m_generation = fontCache()->generation();
+    m_widthCache.clear();
 }
 
 void FontFallbackList::releaseFontData()
index a14fb82..004a53a 100644 (file)
@@ -23,6 +23,7 @@
 
 #include "FontSelector.h"
 #include "SimpleFontData.h"
+#include "WidthCache.h"
 #include <wtf/Forward.h>
 #include <wtf/MainThread.h>
 
@@ -79,6 +80,8 @@ public:
     unsigned fontSelectorVersion() const { return m_fontSelectorVersion; }
     unsigned generation() const { return m_generation; }
 
+    WidthCache& widthCache() const { return m_widthCache; }
+
 private:
     FontFallbackList();
 
@@ -102,6 +105,7 @@ private:
     mutable GlyphPageTreeNode* m_pageZero;
     mutable const SimpleFontData* m_cachedPrimarySimpleFontData;
     RefPtr<FontSelector> m_fontSelector;
+    mutable WidthCache m_widthCache;
     unsigned m_fontSelectorVersion;
     mutable int m_familyIndex;
     unsigned short m_generation;
diff --git a/Source/WebCore/platform/graphics/WidthCache.h b/Source/WebCore/platform/graphics/WidthCache.h
new file mode 100644 (file)
index 0000000..2be546d
--- /dev/null
@@ -0,0 +1,196 @@
+/*
+ * Copyright (C) 2012 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef WidthCache_h
+#define WidthCache_h
+
+#include "TextRun.h"
+#include <wtf/Forward.h>
+#include <wtf/HashFunctions.h>
+#include <wtf/HashSet.h>
+#include <wtf/RefPtr.h>
+#include <wtf/StringHasher.h>
+
+namespace WebCore {
+
+struct GlyphOverflow;
+
+class WidthCache {
+private:
+    // Used to optimize small strings as hash table keys. Avoids malloc'ing an out-of-line StringImpl.
+    class SmallStringKey {
+    public:
+        static unsigned capacity() { return s_capacity; }
+
+        SmallStringKey()
+            : m_length(s_emptyValueLength)
+        {
+        }
+
+        SmallStringKey(WTF::HashTableDeletedValueType)
+            : m_length(s_deletedValueLength)
+        {
+        }
+
+        template<typename CharacterType> SmallStringKey(CharacterType* characters, unsigned short length)
+            : m_length(length)
+        {
+            ASSERT(length <= s_capacity);
+            StringHasher hasher;
+
+            bool remainder = length & 1;
+            length >>= 1;
+
+            unsigned i = 0;
+            while (length--) {
+                m_characters[i] = characters[i];
+                m_characters[i + 1] = characters[i + 1];
+                hasher.addCharacters(characters[i], characters[i + 1]);
+                i += 2;
+            }
+
+            if (remainder) {
+                m_characters[i] = characters[i];
+                hasher.addCharacter(characters[i]);
+            }
+
+            m_hash = hasher.hash();
+        }
+
+        const UChar* characters() const { return m_characters; }
+        unsigned short length() const { return m_length; }
+        unsigned hash() const { return m_hash; }
+
+        bool isHashTableDeletedValue() const { return m_length == s_deletedValueLength; }
+        bool isHashTableEmptyValue() const { return m_length == s_emptyValueLength; }
+
+    private:
+        static const unsigned s_capacity = 15;
+        static const unsigned s_emptyValueLength = s_capacity + 1;
+        static const unsigned s_deletedValueLength = s_capacity + 2;
+
+        unsigned m_hash;
+        unsigned short m_length;
+        UChar m_characters[s_capacity];
+    };
+
+    struct SmallStringKeyHash {
+        static unsigned hash(const SmallStringKey& key) { return key.hash(); }
+        static bool equal(const SmallStringKey& a, const SmallStringKey& b) { return a == b; }
+        static const bool safeToCompareToEmptyOrDeleted = true; // Empty and deleted values have lengths that are not equal to any valid length.
+    };
+
+    struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> {
+        static const bool hasIsEmptyValueFunction = true;
+        static bool isEmptyValue(const SmallStringKey& key) { return key.isHashTableEmptyValue(); }
+        static const bool needsDestruction = false;
+        static const int minimumTableSize = 16;
+    };
+
+    friend bool operator==(const SmallStringKey&, const SmallStringKey&);
+
+public:
+    WidthCache()
+        : m_interval(s_maxInterval)
+        , m_countdown(m_interval)
+    {
+    }
+
+    float* add(const TextRun& run, float entry, bool hasKerningOrLigatures, bool hasWordSpacingOrLetterSpacing, GlyphOverflow* glyphOverflow)
+    {
+        // The width cache is not really profitable unless we're doing expensive glyph transformations.
+        if (!hasKerningOrLigatures)
+            return 0;
+        // Word spacing and letter spacing can change the width of a word.
+        if (hasWordSpacingOrLetterSpacing)
+            return 0;
+        // Since this is just a width cache, we don't have enough information to satisfy glyph queries.
+        if (glyphOverflow)
+            return 0;
+        // If we allow tabs and a tab occurs inside a word, the width of the word varies based on its position on the line.
+        if (run.allowTabs())
+            return 0;
+        if (static_cast<unsigned>(run.length()) > SmallStringKey::capacity())
+            return 0;
+
+        if (m_countdown > 0) {
+            --m_countdown;
+            return 0;
+        }
+
+        return addSlowCase(run, entry);
+    }
+
+    float* addSlowCase(const TextRun& run, float entry)
+    {
+        SmallStringKey smallStringKey;
+        if (run.is8Bit())
+            smallStringKey = SmallStringKey(run.characters8(), run.length());
+        else
+            smallStringKey = SmallStringKey(run.characters16(), run.length());
+
+        Map::AddResult addResult = m_map.add(smallStringKey, entry);
+
+        // Cache hit: ramp up by sampling the next few words.
+        if (!addResult.isNewEntry) {
+            m_interval = s_minInterval;
+            return &addResult.iterator->value;
+        }
+
+        // Cache miss: ramp down by increasing our sampling interval.
+        if (m_interval < s_maxInterval)
+            ++m_interval;
+        m_countdown = m_interval;
+
+        if (m_map.size() < s_maxSize)
+            return &addResult.iterator->value;
+
+        m_map.clear(); // No need to be fancy: we're just trying to avoid pathological growth.
+        return 0;
+    }
+
+    void clear() { m_map.clear(); }
+
+private:
+    typedef HashMap<SmallStringKey, float, SmallStringKeyHash, SmallStringKeyHashTraits> Map;
+    static const int s_minInterval = -3; // A cache hit pays for about 3 cache misses.
+    static const int s_maxInterval = 20; // Sampling at this interval has almost no overhead.
+    static const int s_maxSize = 500000; // Just enough to guard against pathological growth.
+
+    int m_interval;
+    int m_countdown;
+    Map m_map;
+};
+
+inline bool operator==(const WidthCache::SmallStringKey& a, const WidthCache::SmallStringKey& b)
+{
+    if (a.length() != b.length())
+        return false;
+    return WTF::equal(a.characters(), b.characters(), a.length());
+}
+
+} // namespace WebCore
+
+#endif // WidthCache_h