Bug 52622 - Cache function offsets to speed up javascript parsing
Summary: Cache function offsets to speed up javascript parsing
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: PC OS X 10.5
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on: 52814
Blocks:
  Show dependency treegraph
 
Reported: 2011-01-18 05:35 PST by Antti Koivisto
Modified: 2011-01-24 22:06 PST (History)
7 users (show)

See Also:


Attachments
experimental patch (11.87 KB, patch)
2011-01-18 05:37 PST, Antti Koivisto
no flags Details | Formatted Diff | Diff
patch for review (16.56 KB, patch)
2011-01-18 16:47 PST, Antti Koivisto
no flags Details | Formatted Diff | Diff
better size calculation and stylistic improvements (17.06 KB, patch)
2011-01-19 02:23 PST, Antti Koivisto
no flags Details | Formatted Diff | Diff
use shrinkToFit (16.98 KB, patch)
2011-01-19 04:52 PST, Antti Koivisto
oliver: review-
Details | Formatted Diff | Diff
fixes based on oliver's comments (18.88 KB, patch)
2011-01-19 15:44 PST, Antti Koivisto
oliver: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Antti Koivisto 2011-01-18 05:35:23 PST
WebCore memory cache could be used to save javascript function offsets. This could avoid quite a bit of work when reparsing the source.
Comment 1 Antti Koivisto 2011-01-18 05:37:23 PST
Created attachment 79268 [details]
experimental patch
Comment 2 Oliver Hunt 2011-01-18 09:23:40 PST
Comment on attachment 79268 [details]
experimental patch

View in context: https://bugs.webkit.org/attachment.cgi?id=79268&action=review

> Source/JavaScriptCore/parser/JSParser.cpp:121
> +    struct CachedFunctionInfo : public SourceProvider::CachedSourceInfo {
> +        CachedFunctionInfo(JSToken closeBraceToken)
> +            : closeBraceToken(closeBraceToken) 
> +        {
> +        }
> +        unsigned approximateByteSize() const
> +        {
> +            static const unsigned assummedAverageIdentifierSize = 20;
> +            unsigned size = sizeof(*this);
> +            size += declaredVariables.size() * assummedAverageIdentifierSize;
> +            size += usedVariables.size() * assummedAverageIdentifierSize;
> +            size += closedVariables.size() * assummedAverageIdentifierSize;
> +            size += writtenVariables.size() * assummedAverageIdentifierSize;
> +            return size;
> +        }
> +
> +        JSToken closeBraceToken;
> +        bool usesEval;
> +        Vector<RefPtr<StringImpl> > declaredVariables;
> +        Vector<RefPtr<StringImpl> > usedVariables;
> +        Vector<RefPtr<StringImpl> > closedVariables;
> +        Vector<RefPtr<StringImpl> > writtenVariables;
> +    };

The cached info doesn't need to store a functions declared or closed variables.  All it should need to store is the used and written free variables which is basically usedVariables - declaredVariables and writtenVariables - declaredVariables.

Rather than storing the entirety of the close brace token you should be able to simply store the start character and line number.

> Source/JavaScriptCore/parser/JSParser.cpp:1326
> +    if (CachedFunctionInfo* cachedInfo = findCachedFunctionInfo(openBracePos)) {
> +        // 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));
> +
> +        m_token = cachedInfo->closeBraceToken;
> +        m_lexer->setOffsetAfterCloseBraceToken(m_token);
> +        closeBracePos = m_token.m_info.startOffset;
> +
> +        next();
> +        return true;
> +    }

The ability to use the cache is should be determined by the type of treebuilder being used -- something like  TreeBuilder::CanUseFunctionCache will be fine.
Comment 3 Antti Koivisto 2011-01-18 16:47:21 PST
Created attachment 79355 [details]
patch for review

Function cache size seems to be around 10% of the source size on average.

Loading wsj.com the patch avoids parsing ~0.5M characters worth of js on the first load and ~1.5M when revisiting the site.
Comment 4 WebKit Review Bot 2011-01-18 16:49:52 PST
Attachment 79355 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1

Source/JavaScriptCore/parser/SourceProvider.h:60:  This { should be at the end of the previous line  [whitespace/braces] [4]
Total errors found: 1 in 10 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 5 Antti Koivisto 2011-01-19 02:23:45 PST
Created attachment 79405 [details]
better size calculation and stylistic improvements
Comment 6 WebKit Review Bot 2011-01-19 02:26:51 PST
Attachment 79405 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1

Source/JavaScriptCore/parser/SourceProvider.h:40:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Source/WebCore/loader/cache/CachedScript.h:34:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 2 in 10 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 7 Antti Koivisto 2011-01-19 04:52:26 PST
Created attachment 79410 [details]
use shrinkToFit
Comment 8 WebKit Review Bot 2011-01-19 04:54:19 PST
Attachment 79410 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1

Source/JavaScriptCore/parser/SourceProvider.h:40:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Source/WebCore/loader/cache/CachedScript.h:34:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 2 in 10 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 9 Oliver Hunt 2011-01-19 12:51:26 PST
Comment on attachment 79410 [details]
use shrinkToFit

View in context: https://bugs.webkit.org/attachment.cgi?id=79410&action=review

r- due to comments

> Source/JavaScriptCore/parser/Lexer.h:88
> +            ASSERT(token.m_type == CLOSEBRACE);
> +            m_lineNumber = token.m_info.line;
> +            setOffset(token.m_info.endOffset);
> +            if (UNLIKELY(m_code == m_codeEnd))
> +                m_current = -1;
> +            m_delimited = true;
> +            m_lastToken = CLOSEBRACE;

this should be a call to setOffset, although you'll need to transfer 
if (UNLIKELY(m_code == m_codeEnd))
     m_current = -1;

To setOffset as well.

> Source/JavaScriptCore/parser/SourceProvider.h:76
> +

I think we really want SourceProviderCache to hang off of SourceProvider itself.  It will allow it to be devirtualised sensibly.
Comment 10 Antti Koivisto 2011-01-19 15:44:46 PST
Created attachment 79506 [details]
fixes based on oliver's comments

- create a cache for all SourceProviders, not just those connected to WebCore cache
- use setOffset/setLineNumber to restore lexer state
Comment 11 Oliver Hunt 2011-01-19 16:00:36 PST
Comment on attachment 79506 [details]
fixes based on oliver's comments

r=me
Comment 12 Antti Koivisto 2011-01-19 16:14:57 PST
http://trac.webkit.org/changeset/76177
Comment 13 Simon Fraser (smfr) 2011-01-24 22:06:58 PST
This is leaky: bug 53061.