JSC: op_debug bytecode charPosition to column computation is O(n^2)

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Mark Lam]

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>.

[Mark Lam]

Created attachment 194405 [details]
the patch

[Geoffrey Garen]

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?

[Geoffrey Garen]

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.

[Mark Lam]

Thanks for the review.  Updated and landed in r146552: <http://trac.webkit.org/changeset/146552>.