Bug 112957 - JSC: op_debug bytecode charPosition to column computation is O(n^2)
Summary: JSC: op_debug bytecode charPosition to column computation is O(n^2)
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Mark Lam
Keywords: InRadar
Depends on:
Reported: 2013-03-21 13:19 PDT by Mark Lam
Modified: 2013-03-21 19:00 PDT (History)
11 users (show)

See Also:

the patch (14.25 KB, patch)
2013-03-21 17:57 PDT, Mark Lam
ggaren: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Mark Lam 2013-03-21 13:19:43 PDT
With a minified script all on a single line, the computation of debug hook column numbers will be an O(n^2) operation.  We’re going to fix this by computing a line start column table (on demand) for the SourceProvider, and using that to fix up op_debug bytecode column numbers whenever we link an UnlinkedCodeBlock into a CodeBlock.  The computation of the SourceProvider line start column table should be an O(n) operation, and the op_debug column number fixup in the CodeBlock constructor should be an O(log(n)) operation. 

Thereafter, the op_debug column number can be fetched directly from the opcode operand and is ready for use with no further computation.
ref: <rdar://problem/13466251>.
Comment 1 Mark Lam 2013-03-21 17:57:13 PDT
Created attachment 194405 [details]
the patch
Comment 2 Geoffrey Garen 2013-03-21 18:22:15 PDT
Comment on attachment 194405 [details]
the patch

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

> Source/JavaScriptCore/parser/SourceProvider.cpp:53
> +        m_lineStarts = adoptPtr(new Vector<size_t>());

This code should be a separate accessor function named lineStarts().

> Source/JavaScriptCore/parser/SourceProvider.cpp:57
> +            m_lineStarts->append(static_cast<int>(index));

Why cast to int here, when appending to a size_t vector?

> Source/JavaScriptCore/parser/SourceProvider.cpp:71
> +    if (lineStartPosition > charPosition)

The if should use brackets.

> Source/WTF/wtf/text/StringImpl.h:1113
> +inline size_t findNextLineStart(const CharacterType* characters, unsigned length, unsigned index = 0)

Since this is a complement to reverseFindLineTerminator, let's call it "findLineTerminator" or "forwardFindLineTerminator".

> Source/WTF/wtf/text/StringImpl.h:1137
> +        // There can only be a start of a new line if there are more characters
> +        // beyond the current character.
> +        if (index < length) {
> +            // The 3 common types of line terminators are 1. \r\n (Windows), 
> +            // 2. \r (old MacOS) and 3. \n (Unix'es).
> +
> +            if (c == '\n')
> +                return index; // Case 3: just \n.
> +
> +            CharacterType c2 = characters[index];
> +            if (c2 != '\n')
> +                return index; // Case 2: just \r.
> +
> +            // Case 1: \r\n.
> +            // But, there's only a start of a new line if there are more
> +            // characters beyond the \r\n.
> +            if (++index < length)
> +                return index; 

Why is the logic here for what is a newline different from the logic when searching backwards?
Comment 3 Geoffrey Garen 2013-03-21 18:31:39 PDT
Comment on attachment 194405 [details]
the patch

I see -- this function returns the character after the line terminator. I think "lineStart" is a fine name for that, and now I see why it needs different logic.
Comment 4 Mark Lam 2013-03-21 19:00:35 PDT
Thanks for the review.  Updated and landed in r146552: <http://trac.webkit.org/changeset/146552>.