Changeset 142966 in webkit


Ignore:
Timestamp:
Feb 14, 2013 10:41:10 PM (11 years ago)
Author:
ggaren@apple.com
Message:

Merged the global function cache into the source code cache
​https://bugs.webkit.org/show_bug.cgi?id=108660

Reviewed by Sam Weinig.

This has a few benefits:

(*) Saves a few kB by removing a second cache data structure.

(*) Reduces the worst case memory usage of the cache by 1.75X. (Heavy
use of 'new Function' and other techniques could cause us to fill
both root caches, and they didn't trade off against each other.)

(*) Paves the way for future improvements based on a non-trivial
cache key (for example, shrinkable pointer to the key string, and
more precise cache size accounting).

Also cleaned up the cache implementation and simplified it a bit.

  • heap/Handle.h:

(HandleBase):

  • heap/Strong.h:

(Strong): Build!

  • runtime/CodeCache.cpp:

(JSC):
(JSC::CodeCache::getCodeBlock):
(JSC::CodeCache::generateFunctionCodeBlock):
(JSC::CodeCache::getFunctionExecutableFromGlobalCode):
(JSC::CodeCache::usedFunctionCode): Updated for three interface changes:

(*) SourceCodeKey is a class, not a pair.

(*) Table values are abstract pointers, since they can be executables
or code blocks. (In a future patch, I'd like to change this so we
always store only code blocks. But that's too much for one patch.)

(*) The cache function is named "set" because it always overwrites
unconditionally.

  • runtime/CodeCache.h:

(CacheMap):
(JSC::CacheMap::find):
(JSC::CacheMap::set):
(JSC::CacheMap::clear): Added support for specifying hash traits, so we
can use a SourceCodeKey.

Removed side table and random number generator to save space and reduce
complexity. Hash tables are already random, so we don't need another source
of randomness.

(SourceCodeKey):
(JSC::SourceCodeKey::SourceCodeKey):
(JSC::SourceCodeKey::isHashTableDeletedValue):
(JSC::SourceCodeKey::hash):
(JSC::SourceCodeKey::isNull):
(JSC::SourceCodeKey::operator==):
(JSC::SourceCodeKeyHash::hash):
(JSC::SourceCodeKeyHash::equal):
(SourceCodeKeyHash):
(SourceCodeKeyHashTraits):
(JSC::SourceCodeKeyHashTraits::isEmptyValue): A SourceCodeKey is just a
fancy triplet: source code string; function name (or null, for non-functions);
and flags. Flags and function name distinguish between functions and programs
with identical code, so they can live in the same cache.

I chose to use the source code string as the primary hashing reference
because it's likely to be unique. We can use profiling to choose another
technique in future, if collisions between functions and programs prove
to be hot. I suspect they won't.

(JSC::CodeCache::clear):
(CodeCache): Removed the second cache.

  • heap/Handle.h:

(HandleBase):

  • heap/Strong.h:

(Strong):

  • runtime/CodeCache.cpp:

(JSC):
(JSC::CodeCache::getCodeBlock):
(JSC::CodeCache::generateFunctionCodeBlock):
(JSC::CodeCache::getFunctionExecutableFromGlobalCode):
(JSC::CodeCache::usedFunctionCode):

  • runtime/CodeCache.h:

(JSC):
(CacheMap):
(JSC::CacheMap::find):
(JSC::CacheMap::set):
(JSC::CacheMap::clear):
(SourceCodeKey):
(JSC::SourceCodeKey::SourceCodeKey):
(JSC::SourceCodeKey::isHashTableDeletedValue):
(JSC::SourceCodeKey::hash):
(JSC::SourceCodeKey::isNull):
(JSC::SourceCodeKey::operator==):
(JSC::SourceCodeKeyHash::hash):
(JSC::SourceCodeKeyHash::equal):
(SourceCodeKeyHash):
(SourceCodeKeyHashTraits):
(JSC::SourceCodeKeyHashTraits::isEmptyValue):
(JSC::CodeCache::clear):
(CodeCache):

Location:
trunk/Source/JavaScriptCore
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r142923 r142966  
     12013-02-14  Geoffrey Garen  <ggaren@apple.com>
     2
     3        Merged the global function cache into the source code cache
     4        https://bugs.webkit.org/show_bug.cgi?id=108660
     5
     6        Reviewed by Sam Weinig.
     7
     8        This has a few benefits:
     9
     10            (*) Saves a few kB by removing a second cache data structure.
     11
     12            (*) Reduces the worst case memory usage of the cache by 1.75X. (Heavy
     13            use of 'new Function' and other techniques could cause us to fill
     14            both root caches, and they didn't trade off against each other.)
     15
     16            (*) Paves the way for future improvements based on a non-trivial
     17            cache key (for example, shrinkable pointer to the key string, and
     18            more precise cache size accounting).
     19
     20        Also cleaned up the cache implementation and simplified it a bit.
     21
     22        * heap/Handle.h:
     23        (HandleBase):
     24        * heap/Strong.h:
     25        (Strong): Build!
     26
     27        * runtime/CodeCache.cpp:
     28        (JSC):
     29        (JSC::CodeCache::getCodeBlock):
     30        (JSC::CodeCache::generateFunctionCodeBlock):
     31        (JSC::CodeCache::getFunctionExecutableFromGlobalCode):
     32        (JSC::CodeCache::usedFunctionCode): Updated for three interface changes:
     33
     34            (*) SourceCodeKey is a class, not a pair.
     35
     36            (*) Table values are abstract pointers, since they can be executables
     37            or code blocks. (In a future patch, I'd like to change this so we
     38            always store only code blocks. But that's too much for one patch.)
     39
     40            (*) The cache function is named "set" because it always overwrites
     41            unconditionally.
     42
     43        * runtime/CodeCache.h:
     44        (CacheMap):
     45        (JSC::CacheMap::find):
     46        (JSC::CacheMap::set):
     47        (JSC::CacheMap::clear): Added support for specifying hash traits, so we
     48        can use a SourceCodeKey.
     49
     50        Removed side table and random number generator to save space and reduce
     51        complexity. Hash tables are already random, so we don't need another source
     52        of randomness.
     53
     54        (SourceCodeKey):
     55        (JSC::SourceCodeKey::SourceCodeKey):
     56        (JSC::SourceCodeKey::isHashTableDeletedValue):
     57        (JSC::SourceCodeKey::hash):
     58        (JSC::SourceCodeKey::isNull):
     59        (JSC::SourceCodeKey::operator==):
     60        (JSC::SourceCodeKeyHash::hash):
     61        (JSC::SourceCodeKeyHash::equal):
     62        (SourceCodeKeyHash):
     63        (SourceCodeKeyHashTraits):
     64        (JSC::SourceCodeKeyHashTraits::isEmptyValue): A SourceCodeKey is just a
     65        fancy triplet: source code string; function name (or null, for non-functions);
     66        and flags. Flags and function name distinguish between functions and programs
     67        with identical code, so they can live in the same cache.
     68
     69        I chose to use the source code string as the primary hashing reference
     70        because it's likely to be unique. We can use profiling to choose another
     71        technique in future, if collisions between functions and programs prove
     72        to be hot. I suspect they won't.
     73
     74        (JSC::CodeCache::clear):
     75        (CodeCache): Removed the second cache.
     76
     77        * heap/Handle.h:
     78        (HandleBase):
     79        * heap/Strong.h:
     80        (Strong):
     81        * runtime/CodeCache.cpp:
     82        (JSC):
     83        (JSC::CodeCache::getCodeBlock):
     84        (JSC::CodeCache::generateFunctionCodeBlock):
     85        (JSC::CodeCache::getFunctionExecutableFromGlobalCode):
     86        (JSC::CodeCache::usedFunctionCode):
     87        * runtime/CodeCache.h:
     88        (JSC):
     89        (CacheMap):
     90        (JSC::CacheMap::find):
     91        (JSC::CacheMap::set):
     92        (JSC::CacheMap::clear):
     93        (SourceCodeKey):
     94        (JSC::SourceCodeKey::SourceCodeKey):
     95        (JSC::SourceCodeKey::isHashTableDeletedValue):
     96        (JSC::SourceCodeKey::hash):
     97        (JSC::SourceCodeKey::isNull):
     98        (JSC::SourceCodeKey::operator==):
     99        (JSC::SourceCodeKeyHash::hash):
     100        (JSC::SourceCodeKeyHash::equal):
     101        (SourceCodeKeyHash):
     102        (SourceCodeKeyHashTraits):
     103        (JSC::SourceCodeKeyHashTraits::isEmptyValue):
     104        (JSC::CodeCache::clear):
     105        (CodeCache):
     106
    11072013-02-14  Tony Chang  <tony@chromium.org>
    2108

  • trunk/Source/JavaScriptCore/heap/Handle.h

    r140194 r142966  
    4646class HandleBase {
    4747    template <typename T> friend class Weak;
     48    template <typename T> friend class Strong;
    4849    friend class HandleSet;
    4950    friend struct JSCallbackObjectData;

  • trunk/Source/JavaScriptCore/heap/Strong.h

    r113508 r142966  
    3939    using Handle<T>::slot;
    4040    using Handle<T>::setSlot;
     41    template <typename U> friend class Strong;
    4142
    4243public:

  • trunk/Source/JavaScriptCore/runtime/CodeCache.cpp

    r140619 r142966  
    4545}
    4646
    47 CodeCache::SourceCodeKey CodeCache::makeSourceCodeKey(const SourceCode& source, CodeCache::CodeType type, JSParserStrictness strictness)
    48 {
    49     return std::make_pair(source.toString(), (type << 1) | strictness);
    50 }
    51 
    5247template <typename T> struct CacheTypes { };
    5348
    5449template <> struct CacheTypes<UnlinkedProgramCodeBlock> {
    5550    typedef JSC::ProgramNode RootNode;
    56     static const CodeCache::CodeType codeType = CodeCache::ProgramType;
     51    static const SourceCodeKey::CodeType codeType = SourceCodeKey::ProgramType;
    5752};
    5853
    5954template <> struct CacheTypes<UnlinkedEvalCodeBlock> {
    6055    typedef JSC::EvalNode RootNode;
    61     static const CodeCache::CodeType codeType = CodeCache::EvalType;
     56    static const SourceCodeKey::CodeType codeType = SourceCodeKey::EvalType;
    6257};
    6358
    … …  
    6560UnlinkedCodeBlockType* CodeCache::getCodeBlock(JSGlobalData& globalData, ExecutableType* executable, const SourceCode& source, JSParserStrictness strictness, DebuggerMode debuggerMode, ProfilerMode profilerMode, ParserError& error)
    6661{
    67     SourceCodeKey key = makeSourceCodeKey(source, CacheTypes<UnlinkedCodeBlockType>::codeType, strictness);
     62    SourceCodeKey key = SourceCodeKey(source, String(), CacheTypes<UnlinkedCodeBlockType>::codeType, strictness);
    6863    bool storeInCache = false;
    6964    if (debuggerMode == DebuggerOff && profilerMode == ProfilerOff) {
    70         const Strong<UnlinkedCodeBlock>* result = m_sourceCode.find(key);
     65        const Strong<JSCell>* result = m_sourceCode.find(key);
    7166        if (result) {
    7267            UnlinkedCodeBlockType* unlinkedCode = jsCast<UnlinkedCodeBlockType*>(result->get());
    … …  
    9388
    9489    if (storeInCache)
    95         m_sourceCode.add(key, Strong<UnlinkedCodeBlock>(globalData, unlinkedCode));
     90        m_sourceCode.set(key, Strong<UnlinkedCodeBlock>(globalData, unlinkedCode));
    9691
    9792    return unlinkedCode;
    … …  
    128123    if (error.m_type != ParserError::ErrorNone)
    129124        return 0;
    130     m_recentlyUsedFunctions.add(result, Strong<UnlinkedFunctionCodeBlock>(globalData, result));
     125    m_recentlyUsedFunctions.set(result, Strong<UnlinkedFunctionCodeBlock>(globalData, result));
    131126    return result;
    132127}
    … …  
    137132}
    138133
    139 CodeCache::FunctionKey CodeCache::makeFunctionKey(const SourceCode& source, const String& name)
    140 {
    141     return FunctionKey(source.toString(), name);
    142 }
    143 
    144134UnlinkedFunctionExecutable* CodeCache::getFunctionExecutableFromGlobalCode(JSGlobalData& globalData, const Identifier& name, const SourceCode& source, ParserError& error)
    145135{
    146     FunctionKey key = makeFunctionKey(source, name.string());
    147     const Strong<UnlinkedFunctionExecutable>* result = m_globalFunctions.find(key);
     136    SourceCodeKey key = SourceCodeKey(source, name.string(), SourceCodeKey::FunctionCallType, JSParseNormal);
     137    const Strong<JSCell>* result = m_sourceCode.find(key);
    148138    if (result)
    149         return result->get();
     139        return jsCast<UnlinkedFunctionExecutable*>(result->get());
    150140
    151141    RefPtr<ProgramNode> program = parse<ProgramNode>(&globalData, source, 0, Identifier(), JSParseNormal, JSParseProgramCode, error);
    … …  
    169159    functionExecutable->m_nameValue.set(globalData, functionExecutable, jsString(&globalData, name.string()));
    170160
    171     m_globalFunctions.add(key, Strong<UnlinkedFunctionExecutable>(globalData, functionExecutable));
     161    m_sourceCode.set(key, Strong<UnlinkedFunctionExecutable>(globalData, functionExecutable));
    172162    return functionExecutable;
    173163}
    … …  
    175165void CodeCache::usedFunctionCode(JSGlobalData& globalData, UnlinkedFunctionCodeBlock* codeBlock)
    176166{
    177     m_recentlyUsedFunctions.add(codeBlock, Strong<UnlinkedFunctionCodeBlock>(globalData, codeBlock));
     167    m_recentlyUsedFunctions.set(codeBlock, Strong<UnlinkedFunctionCodeBlock>(globalData, codeBlock));
    178168}
    179169

  • trunk/Source/JavaScriptCore/runtime/CodeCache.h

    r140619 r142966  
    2929#include "CodeSpecializationKind.h"
    3030#include "ParserModes.h"
     31#include "SourceCode.h"
    3132#include "Strong.h"
    3233#include "WeakRandom.h"
    33 
    3434#include <wtf/FixedArray.h>
    3535#include <wtf/Forward.h>
    … …  
    5454class SourceProvider;
    5555
    56 template <typename KeyType, typename EntryType, int CacheSize> class CacheMap {
    57     typedef typename HashMap<KeyType, unsigned>::iterator iterator;
     56template <int CacheSize, typename KeyType, typename EntryType, typename HashArg = typename DefaultHash<KeyType>::Hash, typename KeyTraitsArg = HashTraits<KeyType> >
     57class CacheMap {
     58    typedef HashMap<KeyType, EntryType, HashArg, KeyTraitsArg> MapType;
     59    typedef typename MapType::iterator iterator;
     60
    5861public:
    59     CacheMap()
    60         : m_randomGenerator((static_cast<uint32_t>(randomNumber() * std::numeric_limits<uint32_t>::max())))
    61     {
    62     }
    6362    const EntryType* find(const KeyType& key)
    6463    {
    … …  
    6665        if (result == m_map.end())
    6766            return 0;
    68         return &m_data[result->value].second;
    69     }
    70     void add(const KeyType& key, const EntryType& value)
    71     {
    72         iterator result = m_map.find(key);
    73         if (result != m_map.end()) {
    74             m_data[result->value].second = value;
    75             return;
    76         }
    77         size_t newIndex = m_randomGenerator.getUint32() % CacheSize;
    78         if (m_data[newIndex].second)
    79             m_map.remove(m_data[newIndex].first);
    80         m_map.add(key, newIndex);
    81         m_data[newIndex].first = key;
    82         m_data[newIndex].second = value;
    83         RELEASE_ASSERT(m_map.size() <= CacheSize);
     67        return &result->value;
    8468    }
    8569
    86     void clear()
     70    void set(const KeyType& key, const EntryType& value)
    8771    {
    88         m_map.clear();
    89         for (size_t i = 0; i < CacheSize; i++) {
    90             m_data[i].first = KeyType();
    91             m_data[i].second = EntryType();
    92         }
     72        if (m_map.size() >= CacheSize)
     73            m_map.remove(m_map.begin());
     74
     75        m_map.set(key, value);
    9376    }
    9477
     78    void clear() { m_map.clear(); }
    9579
    9680private:
    97     HashMap<KeyType, unsigned> m_map;
    98     FixedArray<std::pair<KeyType, EntryType>, CacheSize> m_data;
    99     WeakRandom m_randomGenerator;
     81    MapType m_map;
     82};
     83
     84class SourceCodeKey {
     85public:
     86    enum CodeType { EvalType, ProgramType, FunctionCallType, FunctionConstructType };
     87
     88    SourceCodeKey()
     89        : m_flags(0)
     90    {
     91    }
     92
     93    SourceCodeKey(const SourceCode& sourceCode, const String& name, CodeType codeType, JSParserStrictness jsParserStrictness)
     94        : m_sourceString(sourceCode.toString())
     95        , m_name(name)
     96        , m_flags((codeType << 1) | jsParserStrictness)
     97    {
     98    }
     99
     100    SourceCodeKey(WTF::HashTableDeletedValueType)
     101        : m_sourceString(WTF::HashTableDeletedValue)
     102        , m_name(WTF::HashTableDeletedValue)
     103        , m_flags(0)
     104    {
     105    }
     106
     107    bool isHashTableDeletedValue() const { return m_sourceString.isHashTableDeletedValue(); }
     108
     109    unsigned hash() const { return m_sourceString.impl()->hash(); }
     110
     111    bool isNull() const { return m_sourceString.isNull(); }
     112
     113    bool operator==(const SourceCodeKey& other) const
     114    {
     115        return m_flags == other.m_flags
     116            && m_name == other.m_name
     117            && m_sourceString == other.m_sourceString;
     118    }
     119
     120private:
     121    String m_sourceString;
     122    String m_name;
     123    unsigned m_flags;
     124};
     125
     126struct SourceCodeKeyHash {
     127    static unsigned hash(const SourceCodeKey& key) { return key.hash(); }
     128    static bool equal(const SourceCodeKey& a, const SourceCodeKey& b) { return a == b; }
     129    static const bool safeToCompareToEmptyOrDeleted = false;
     130};
     131
     132struct SourceCodeKeyHashTraits : WTF::SimpleClassHashTraits<SourceCodeKey> {
     133    static const bool hasIsEmptyValueFunction = true;
     134    static bool isEmptyValue(const SourceCodeKey& sourceCodeKey) { return sourceCodeKey.isNull(); }
    100135};
    101136
    … …  
    114149    {
    115150        m_sourceCode.clear();
    116         m_globalFunctions.clear();
    117151        m_recentlyUsedFunctions.clear();
    118152    }
    119 
    120     enum CodeType { EvalType, ProgramType, FunctionCallType, FunctionConstructType };
    121     typedef std::pair<String, unsigned> SourceCodeKey;
    122     typedef std::pair<String, String> FunctionKey;
    123153
    124154private:
    … …  
    128158
    129159    template <class UnlinkedCodeBlockType, class ExecutableType> inline UnlinkedCodeBlockType* getCodeBlock(JSGlobalData&, ExecutableType*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
    130     SourceCodeKey makeSourceCodeKey(const SourceCode&, CodeType, JSParserStrictness);
    131     FunctionKey makeFunctionKey(const SourceCode&, const String&);
    132160
    133161    enum {
    134         MaxRootEntries = 1024, // Top-level code such as <script>, eval(), JSEvaluateScript(), etc.
     162        MaxRootEntries = 1280, // Top-level code such as <script>, eval(), JSEvaluateScript(), etc.
    135163        MaxChildFunctionEntries = MaxRootEntries * 8 // Sampling shows that each root holds about 6 functions. 8 is enough to usually cache all the child functions for each top-level entry.
    136164    };
    137165
    138     CacheMap<SourceCodeKey, Strong<UnlinkedCodeBlock>, MaxRootEntries> m_sourceCode;
    139     CacheMap<FunctionKey, Strong<UnlinkedFunctionExecutable>, MaxRootEntries> m_globalFunctions;
    140     CacheMap<UnlinkedFunctionCodeBlock*, Strong<UnlinkedFunctionCodeBlock>, MaxChildFunctionEntries> m_recentlyUsedFunctions;
     166    CacheMap<MaxRootEntries, SourceCodeKey, Strong<JSCell>, SourceCodeKeyHash, SourceCodeKeyHashTraits> m_sourceCode;
     167    CacheMap<MaxChildFunctionEntries, UnlinkedFunctionCodeBlock*, Strong<UnlinkedFunctionCodeBlock> > m_recentlyUsedFunctions;
    141168};
    142169
    143170}
    144171
    145 #endif
     172#endif // CodeCache_h
Note: See TracChangeset for help on using the changeset viewer.