Cache function offsets to speed up javascript parsing
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 20 Jan 2011 00:13:03 +0000 (00:13 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 20 Jan 2011 00:13:03 +0000 (00:13 +0000)
https://bugs.webkit.org/show_bug.cgi?id=52622

Reviewed by Oliver Hunt.

Use cache to save function offsets and some other info.
This avoids quite a bit of work when reparsing the source.

Source/JavaScriptCore:

* parser/ASTBuilder.h:
* parser/JSParser.cpp:
(JSC::JSParser::CachedFunctionInfo::CachedFunctionInfo):
(JSC::JSParser::CachedFunctionInfo::approximateByteSize):
(JSC::JSParser::CachedFunctionInfo::closeBraceToken):
(JSC::JSParser::Scope::copyCapturedVariablesToVector):
(JSC::JSParser::Scope::saveFunctionInfo):
(JSC::JSParser::Scope::restoreFunctionInfo):
(JSC::JSParser::findCachedFunctionInfo):
(JSC::JSParser::JSParser):
(JSC::JSParser::parseProgram):
(JSC::JSParser::parseFunctionInfo):
* parser/Lexer.h:
(JSC::Lexer::setOffset):
(JSC::Lexer::setLineNumber):
(JSC::Lexer::sourceProvider):
* parser/SourceProvider.h:
(JSC::SourceProviderCache::SourceProviderCache):
(JSC::SourceProviderCache::~SourceProviderCache):
(JSC::SourceProviderCache::byteSize):
(JSC::SourceProviderCache::add):
(JSC::SourceProviderCache::get):
(JSC::SourceProvider::SourceProvider):
(JSC::SourceProvider::~SourceProvider):
(JSC::SourceProvider::cache):
(JSC::SourceProvider::notifyCacheSizeChanged):
(JSC::SourceProvider::cacheSizeChanged):
* parser/SyntaxChecker.h:

Source/WebCore:

* bindings/js/CachedScriptSourceProvider.h:
(WebCore::CachedScriptSourceProvider::cache):
(WebCore::CachedScriptSourceProvider::cacheSizeChanged):
(WebCore::CachedScriptSourceProvider::CachedScriptSourceProvider):
* bindings/js/ScriptSourceProvider.h:
(WebCore::ScriptSourceProvider::ScriptSourceProvider):
* loader/cache/CachedScript.cpp:
(WebCore::CachedScript::destroyDecodedData):
(WebCore::CachedScript::sourceProviderCache):
(WebCore::CachedScript::sourceProviderCacheSizeChanged):
* loader/cache/CachedScript.h:

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/parser/ASTBuilder.h
Source/JavaScriptCore/parser/JSParser.cpp
Source/JavaScriptCore/parser/Lexer.h
Source/JavaScriptCore/parser/SourceProvider.h
Source/JavaScriptCore/parser/SyntaxChecker.h
Source/WebCore/ChangeLog
Source/WebCore/bindings/js/CachedScriptSourceProvider.h
Source/WebCore/bindings/js/ScriptSourceProvider.h
Source/WebCore/loader/cache/CachedScript.cpp
Source/WebCore/loader/cache/CachedScript.h

index 4010a81cca9759c77e1387317f4f92d73fd92ceb..2a62a9ed7e94fc963392f531dfc5a4ed5d339cee 100644 (file)
@@ -1,3 +1,42 @@
+2011-01-19  Antti Koivisto  <antti@apple.com>
+
+        Reviewed by Oliver Hunt.
+
+        Cache function offsets to speed up javascript parsing
+        https://bugs.webkit.org/show_bug.cgi?id=52622
+        
+        Use cache to save function offsets and some other info.
+        This avoids quite a bit of work when reparsing the source.
+
+        * parser/ASTBuilder.h:
+        * parser/JSParser.cpp:
+        (JSC::JSParser::CachedFunctionInfo::CachedFunctionInfo):
+        (JSC::JSParser::CachedFunctionInfo::approximateByteSize):
+        (JSC::JSParser::CachedFunctionInfo::closeBraceToken):
+        (JSC::JSParser::Scope::copyCapturedVariablesToVector):
+        (JSC::JSParser::Scope::saveFunctionInfo):
+        (JSC::JSParser::Scope::restoreFunctionInfo):
+        (JSC::JSParser::findCachedFunctionInfo):
+        (JSC::JSParser::JSParser):
+        (JSC::JSParser::parseProgram):
+        (JSC::JSParser::parseFunctionInfo):
+        * parser/Lexer.h:
+        (JSC::Lexer::setOffset):
+        (JSC::Lexer::setLineNumber):
+        (JSC::Lexer::sourceProvider):
+        * parser/SourceProvider.h:
+        (JSC::SourceProviderCache::SourceProviderCache):
+        (JSC::SourceProviderCache::~SourceProviderCache):
+        (JSC::SourceProviderCache::byteSize):
+        (JSC::SourceProviderCache::add):
+        (JSC::SourceProviderCache::get):
+        (JSC::SourceProvider::SourceProvider):
+        (JSC::SourceProvider::~SourceProvider):
+        (JSC::SourceProvider::cache):
+        (JSC::SourceProvider::notifyCacheSizeChanged):
+        (JSC::SourceProvider::cacheSizeChanged):
+        * parser/SyntaxChecker.h:
+
 2011-01-19  Mark Rowe  <mrowe@apple.com>
 
         Reviewed by Darin Adler.
index 337c87eff0319c10ffbe91bdd205c7b9fe76b164..0e18d1d81fa6397fe384921ae841ae91efd01337 100644 (file)
@@ -108,6 +108,7 @@ public:
     
     static const bool CreatesAST = true;
     static const bool NeedsFreeVariableInfo = true;
+    static const bool CanUseFunctionCache = true;
 
     ExpressionNode* makeBinaryNode(int token, std::pair<ExpressionNode*, BinaryOpInfo>, std::pair<ExpressionNode*, BinaryOpInfo>);
     ExpressionNode* makeFunctionCallNode(ExpressionNode* func, ArgumentsNode* args, int start, int divot, int end);
index 1ff5090826b1f8037847f08664f41e07dd50ad36..d06f7d93086bd5932273782db68d53e9b6e26d2d 100644 (file)
@@ -33,6 +33,7 @@ using namespace JSC;
 #include "JSGlobalData.h"
 #include "NodeInfo.h"
 #include "ASTBuilder.h"
+#include "SourceProvider.h"
 #include <wtf/HashFunctions.h>
 #include <wtf/WTFThreadData.h>
 #include <utility>
@@ -94,6 +95,39 @@ private:
         StringImpl* m_ident;
         bool m_isLoop;
     };
+    
+    struct CachedFunctionInfo : public SourceProviderCache::Item {
+        CachedFunctionInfo(int closeBraceLine, int closeBracePos)
+            : closeBraceLine(closeBraceLine) 
+            , closeBracePos(closeBracePos)
+        {
+        }
+        unsigned approximateByteSize() const
+        {
+            // The identifiers are uniqued strings so most likely there are few names that actually use any additional memory.
+            static const unsigned assummedAverageIdentifierSize = sizeof(RefPtr<StringImpl>) + 2;
+            unsigned size = sizeof(*this);
+            size += usedVariables.size() * assummedAverageIdentifierSize;
+            size += writtenVariables.size() * assummedAverageIdentifierSize;
+            return size;
+        }
+        JSToken closeBraceToken() const 
+        {
+            JSToken token;
+            token.m_type = CLOSEBRACE;
+            token.m_data.intValue = closeBracePos;
+            token.m_info.startOffset = closeBracePos;
+            token.m_info.endOffset = closeBracePos + 1;
+            token.m_info.line = closeBraceLine; 
+            return token;
+        }
+
+        int closeBraceLine;
+        int closeBracePos;
+        bool usesEval;
+        Vector<RefPtr<StringImpl> > usedVariables;
+        Vector<RefPtr<StringImpl> > writtenVariables;
+    };
 
     void next(Lexer::LexType lexType = Lexer::IdentifyReservedWords)
     {
@@ -417,6 +451,37 @@ private:
         bool strictMode() const { return m_strictMode; }
         bool isValidStrictMode() const { return m_isValidStrictMode; }
         bool shadowsArguments() const { return m_shadowsArguments; }
+        
+        void copyCapturedVariablesToVector(const IdentifierSet& capturedVariables, Vector<RefPtr<StringImpl> >& vector)
+        {
+            IdentifierSet::iterator end = capturedVariables.end();
+            for (IdentifierSet::iterator it = capturedVariables.begin(); it != end; ++it) {
+                if (m_declaredVariables.contains(*it))
+                    continue;
+                vector.append(*it);
+            }
+            vector.shrinkToFit();
+        }
+
+        void saveFunctionInfo(CachedFunctionInfo* info)
+        {
+            ASSERT(m_isFunction);
+            info->usesEval = m_usesEval;
+            copyCapturedVariablesToVector(m_writtenVariables, info->writtenVariables);
+            copyCapturedVariablesToVector(m_usedVariables, info->usedVariables);
+        }
+
+        void restoreFunctionInfo(const CachedFunctionInfo* info)
+        {
+            ASSERT(m_isFunction);
+            m_usesEval = info->usesEval;
+            unsigned size = info->usedVariables.size();
+            for (unsigned i = 0; i < size; ++i)
+                m_usedVariables.add(info->usedVariables[i]);
+            size = info->writtenVariables.size();
+            for (unsigned i = 0; i < size; ++i)
+                m_writtenVariables.add(info->writtenVariables[i]);
+        }
 
     private:
         JSGlobalData* m_globalData;
@@ -543,6 +608,13 @@ private:
     }
 
     ScopeStack m_scopeStack;
+
+    const CachedFunctionInfo* findCachedFunctionInfo(int openBracePos) 
+    {
+        return m_functionCache ? static_cast<const CachedFunctionInfo*>(m_functionCache->get(openBracePos)) : 0;
+    }
+
+    SourceProviderCache* m_functionCache;
 };
 
 const char* jsParse(JSGlobalData* globalData, FunctionParameters* parameters, JSParserStrictness strictness, JSParserMode parserMode, const SourceCode* source)
@@ -566,6 +638,7 @@ JSParser::JSParser(Lexer* lexer, JSGlobalData* globalData, FunctionParameters* p
     , m_statementDepth(0)
     , m_nonTrivialExpressionCount(0)
     , m_lastIdentifier(0)
+    , m_functionCache(m_lexer->sourceProvider()->cache())
 {
     ScopeRef scope = pushScope();
     if (isFunction)
@@ -582,6 +655,7 @@ JSParser::JSParser(Lexer* lexer, JSGlobalData* globalData, FunctionParameters* p
 
 const char* JSParser::parseProgram()
 {
+    unsigned oldFunctionCacheSize = m_functionCache ? m_functionCache->byteSize() : 0;
     ASTBuilder context(m_globalData, m_lexer);
     if (m_lexer->isReparsing())
         m_statementDepth--;
@@ -596,6 +670,10 @@ const char* JSParser::parseProgram()
         features |= StrictModeFeature;
     if (scope->shadowsArguments())
         features |= ShadowsArgumentsFeature;
+    
+    unsigned functionCacheSize = m_functionCache ? m_functionCache->byteSize() : 0;
+    if (functionCacheSize != oldFunctionCacheSize)
+        m_lexer->sourceProvider()->notifyCacheSizeChanged(functionCacheSize - oldFunctionCacheSize);
 
     m_globalData->parser->didFinishParsing(sourceElements, context.varDeclarations(), context.funcDeclarations(), features,
                                            m_lastLine, context.numConstants(), capturedVariables);
@@ -1239,6 +1317,23 @@ template <JSParser::FunctionRequirements requirements, bool nameIsInContainingSc
 
     openBracePos = m_token.m_data.intValue;
     bodyStartLine = tokenLine();
+
+    if (const CachedFunctionInfo* cachedInfo = TreeBuilder::CanUseFunctionCache ? findCachedFunctionInfo(openBracePos) : 0) {
+        // If we know about this function already, we can use the cached info and skip the parser to the end of the function.
+        body = context.createFunctionBody(strictMode());
+
+        functionScope->restoreFunctionInfo(cachedInfo);
+        failIfFalse(popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo));
+
+        closeBracePos = cachedInfo->closeBracePos;
+        m_token = cachedInfo->closeBraceToken();
+        m_lexer->setOffset(m_token.m_info.endOffset);
+        m_lexer->setLineNumber(m_token.m_info.line);
+
+        next();
+        return true;
+    }
+
     next();
 
     body = parseFunctionBody(context);
@@ -1247,9 +1342,24 @@ template <JSParser::FunctionRequirements requirements, bool nameIsInContainingSc
         failIfTrue(m_globalData->propertyNames->arguments == *name);
         failIfTrue(m_globalData->propertyNames->eval == *name);
     }
+    closeBracePos = m_token.m_data.intValue;
+    
+    // Cache the tokenizer state and the function scope the first time the function is parsed.
+    // Any future reparsing can then skip the function.
+    static const int minimumFunctionLengthToCache = 64;
+    OwnPtr<CachedFunctionInfo> newInfo;
+    int functionLength = closeBracePos - openBracePos;
+    if (TreeBuilder::CanUseFunctionCache && m_functionCache && functionLength > minimumFunctionLengthToCache) {
+        newInfo = adoptPtr(new CachedFunctionInfo(m_token.m_info.line, closeBracePos));
+        functionScope->saveFunctionInfo(newInfo.get());
+    }
+    
     failIfFalse(popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo));
     matchOrFail(CLOSEBRACE);
-    closeBracePos = m_token.m_data.intValue;
+
+    if (newInfo)
+        m_functionCache->add(openBracePos, newInfo.release(), newInfo->approximateByteSize());
+
     next();
     return true;
 }
index 79987af659e5eef48b0351e918e18d3045c1d927..dfdb22ccc64df64deb15608ea4ba88dc0b874a0f 100644 (file)
@@ -73,7 +73,15 @@ namespace JSC {
             m_current = *m_code;
             m_buffer8.resize(0);
             m_buffer16.resize(0);
+            if (UNLIKELY(m_code == m_codeEnd))
+                m_current = -1;
         }
+        void setLineNumber(int line)
+        {
+            m_lineNumber = line;
+        }
+
+        SourceProvider* sourceProvider() const { return m_source->provider(); }
 
     private:
         friend class JSGlobalData;
index 36481263d40dc87ca0dd9ad82a390044f0e4f5d5..bcc445ba9bdb265e95201fcc3dcd36fdde17fcc1 100644 (file)
 #define SourceProvider_h
 
 #include "UString.h"
+#include <wtf/HashMap.h>
+#include <wtf/PassOwnPtr.h>
 #include <wtf/RefCounted.h>
+#include <wtf/UnusedParam.h>
 #include <wtf/text/TextPosition.h>
 
+
 namespace JSC {
 
+    class SourceProviderCache {
+    public:
+        struct Item {};
+
+        SourceProviderCache() : m_contentByteSize(0) {}
+        ~SourceProviderCache() { deleteAllValues(m_map); }
+        
+        unsigned byteSize() const { return m_contentByteSize + sizeof(*this) + m_map.capacity() * sizeof(Item*); } 
+        void add(int sourcePosition, PassOwnPtr<Item> item, unsigned size) { m_map.add(sourcePosition, item.leakPtr()); m_contentByteSize += size; }
+        const Item* get(int sourcePosition) const { return m_map.get(sourcePosition); }
+
+    private:
+        HashMap<int, Item*> m_map;
+        unsigned m_contentByteSize;
+    };
+
     class SourceProvider : public RefCounted<SourceProvider> {
     public:
-        SourceProvider(const UString& url)
+        SourceProvider(const UString& url, SourceProviderCache* cache = 0)
             : m_url(url)
             , m_validated(false)
+            , m_cache(cache ? cache : new SourceProviderCache)
+            , m_cacheOwned(!cache)
+        {
+        }
+        virtual ~SourceProvider()
         {
+            if (m_cacheOwned)
+                delete m_cache;
         }
-        virtual ~SourceProvider() { }
 
         virtual UString getRange(int start, int end) const = 0;
         virtual const UChar* data() const = 0;
@@ -55,9 +81,16 @@ namespace JSC {
         bool isValid() const { return m_validated; }
         void setValid() { m_validated = true; }
 
+        SourceProviderCache* cache() const { return m_cache; }
+        void notifyCacheSizeChanged(int delta) { if (!m_cacheOwned) cacheSizeChanged(delta); }
+        
     private:
+        virtual void cacheSizeChanged(int delta) { UNUSED_PARAM(delta); }
+
         UString m_url;
         bool m_validated;
+        SourceProviderCache* m_cache;
+        bool m_cacheOwned;
     };
 
     class UStringSourceProvider : public SourceProvider {
index 1b5497af47a22084994bb67d533c6f33143f16f4..8823566330d6bfa0413b8fa47455d84289c4a975 100644 (file)
@@ -112,6 +112,7 @@ public:
     
     static const bool CreatesAST = false;
     static const bool NeedsFreeVariableInfo = false;
+    static const bool CanUseFunctionCache = true;
 
     int createSourceElements() { return 1; }
     ExpressionType makeFunctionCallNode(int, int, int, int, int) { return CallExpr; }
index 853344e199ddfe24584d0843812f117d480d965e..4e57c72e3a72b4907b42b0da22d9a85ccf5b72dd 100644 (file)
@@ -1,3 +1,25 @@
+2011-01-19  Antti Koivisto  <antti@apple.com>
+
+        Reviewed by Oliver Hunt.
+
+        Cache function offsets to speed up javascript parsing
+        https://bugs.webkit.org/show_bug.cgi?id=52622
+        
+        Use cache to save function offsets and some other info.
+        This avoids quite a bit of work when reparsing the source.
+
+        * bindings/js/CachedScriptSourceProvider.h:
+        (WebCore::CachedScriptSourceProvider::cache):
+        (WebCore::CachedScriptSourceProvider::cacheSizeChanged):
+        (WebCore::CachedScriptSourceProvider::CachedScriptSourceProvider):
+        * bindings/js/ScriptSourceProvider.h:
+        (WebCore::ScriptSourceProvider::ScriptSourceProvider):
+        * loader/cache/CachedScript.cpp:
+        (WebCore::CachedScript::destroyDecodedData):
+        (WebCore::CachedScript::sourceProviderCache):
+        (WebCore::CachedScript::sourceProviderCacheSizeChanged):
+        * loader/cache/CachedScript.h:
+
 2011-01-11  Martin Robinson  <mrobinson@igalia.com>
 
         Reviewed by Gustavo Noronha Silva.
index 809a48806a55cf15e369f04732754b477d5d7bb3..ea68d10ef28fece4eda61ea996029b785a7a6222 100644 (file)
@@ -49,9 +49,14 @@ namespace WebCore {
         int length() const { return m_cachedScript->script().length(); }
         const String& source() const { return m_cachedScript->script(); }
 
+        virtual void cacheSizeChanged(int delta) 
+        { 
+            m_cachedScript->sourceProviderCacheSizeChanged(delta);
+        }
+
     private:
         CachedScriptSourceProvider(CachedScript* cachedScript)
-            : ScriptSourceProvider(stringToUString(cachedScript->url()))
+            : ScriptSourceProvider(stringToUString(cachedScript->url()), cachedScript->sourceProviderCache())
             , m_cachedScript(cachedScript)
         {
             m_cachedScript->addClient(this);
index de4e307776b603f8da20a4c19d5bb66d954356ad..3a5d579bfeadd95de50af41d7dbc499147663cf1 100644 (file)
@@ -34,8 +34,8 @@ namespace WebCore {
 
     class ScriptSourceProvider : public JSC::SourceProvider {
     public:
-        ScriptSourceProvider(const JSC::UString& url)
-            : SourceProvider(url)
+        ScriptSourceProvider(const JSC::UString& url, JSC::SourceProviderCache* cache = 0)
+            : SourceProvider(url, cache)
         {
         }
 
index 54b4503fe3eb16e43a8443b3a2276b72cff9b4b8..8950ddb2f4cb414a70db4a89c95d5a6941d4f55e 100644 (file)
 #include "TextResourceDecoder.h"
 #include <wtf/Vector.h>
 
+#if USE(JSC)  
+#include <parser/SourceProvider.h>
+#endif
+
 namespace WebCore {
 
 CachedScript::CachedScript(const String& url, const String& charset)
@@ -111,7 +115,12 @@ void CachedScript::error(CachedResource::Status status)
 void CachedScript::destroyDecodedData()
 {
     m_script = String();
-    setDecodedSize(0);
+    unsigned extraSize = 0;
+#if USE(JSC)
+    // FIXME: SourceInfoCache should be wiped out too but not this easily.
+    extraSize = m_sourceProviderCache ? m_sourceProviderCache->byteSize() : 0;
+#endif
+    setDecodedSize(extraSize);
     if (!MemoryCache::shouldMakeResourcePurgeableOnEviction() && isSafeToMakePurgeable())
         makePurgeable(true);
 }
@@ -121,4 +130,18 @@ void CachedScript::decodedDataDeletionTimerFired(Timer<CachedScript>*)
     destroyDecodedData();
 }
 
+#if USE(JSC)
+JSC::SourceProviderCache* CachedScript::sourceProviderCache() const
+{   
+    if (!m_sourceProviderCache) 
+        m_sourceProviderCache = adoptPtr(new JSC::SourceProviderCache); 
+    return m_sourceProviderCache.get(); 
+}
+
+void CachedScript::sourceProviderCacheSizeChanged(int delta)
+{
+    setDecodedSize(decodedSize() + delta);
+}
+#endif
+
 } // namespace WebCore
index 30fcb1e5f268ada1a9b7123a6644b685e7f4a4dc..14294f27533cb176f1293f0f50f9cbb678720677 100644 (file)
 #include "CachedResource.h"
 #include "Timer.h"
 
+#if USE(JSC)
+namespace JSC {
+    class SourceProviderCache;
+}
+#endif
+
 namespace WebCore {
 
     class CachedResourceLoader;
@@ -51,7 +57,11 @@ namespace WebCore {
         void checkNotify();
 
         virtual void destroyDecodedData();
-
+#if USE(JSC)        
+        // Allows JSC to cache additional information about the source.
+        JSC::SourceProviderCache* sourceProviderCache() const;
+        void sourceProviderCacheSizeChanged(int delta);
+#endif
     private:
         void decodedDataDeletionTimerFired(Timer<CachedScript>*);
         virtual PurgePriority purgePriority() const { return PurgeLast; }
@@ -59,6 +69,9 @@ namespace WebCore {
         String m_script;
         RefPtr<TextResourceDecoder> m_decoder;
         Timer<CachedScript> m_decodedDataDeletionTimer;
+#if USE(JSC)        
+        mutable OwnPtr<JSC::SourceProviderCache> m_sourceProviderCache;
+#endif
     };
 }