JS_Eval is ~485x slower on long single-line scripts since v0.16.0 (O(n²) parsing regression)

[starxg]

Summary

Starting with QuickJS-NG v0.16.0, JS_Eval is approximately 485 times
slower than v0.15.1 when parsing 80,000 identifier references on a single
line in a Debug build.

With v0.16.0, the same identifier references evaluate approximately 440
times faster when separated by line breaks. Release builds are also affected,
with the one-line script taking approximately 166 times longer than the
equivalent multi-line script.

The measured JS_Eval time increased from approximately 31 ms in v0.15.1
to approximately 15 seconds in v0.16.0.

Reproduction

A complete CMake reproducer is available here:

https://github.com/starxg/quickjs-slowly

The reproducer generates two semantically equivalent scripts:

static std::string make_script(const bool one_line) {
    std::string script = "var a = 0;";

    for (int i = 0; i < 80000; ++i) {
        script += one_line ? "a;" : "a;\n";
    }

    return script;
}

They contain the same 80,000 identifier references:

// One line
var a = 0;a;a;a;a;...

// Multiple lines
var a = 0;a;
a;
a;
a;
...

The program evaluates the one-line version first, followed by the
multiple-line version:

eval(make_script(true));
eval(make_script(false));

Only the JS_Eval call is timed. Script generation, runtime/context creation,
and runtime/context destruction are excluded from the measurement.

Steps to reproduce

The project uses vcpkg:

git clone https://github.com/starxg/quickjs-slowly.git
cd quickjs-slowly

export VCPKG_ROOT=/path/to/vcpkg

cmake --preset Debug
cmake --build cmake-build-debug

./cmake-build-debug/quickjs_slowly

For a Release build:

cmake --preset Release
cmake --build cmake-build-release

./cmake-build-release/quickjs_slowly

Results

Average of three runs:

QuickJS version	Build type	One line	Multiple lines
v0.15.1	Debug	31 ms	29 ms
v0.16.0	Debug	15,039 ms	34 ms
v0.16.0	Release	1,826 ms	11 ms

With QuickJS-NG v0.16.0:

• Debug: the one-line script is approximately 440 times slower.
• Release: the one-line script is approximately 166 times slower.
• The one-line Debug result regressed from approximately 31 ms in v0.15.1
  to approximately 15 seconds in v0.16.0.

Both scripts complete successfully without throwing an exception.

Expected behavior

Parsing time should scale approximately with the number of tokens or the
input size.

Adding or removing line breaks between semicolon-terminated statements
should not change parsing time by several orders of magnitude.

The one-line script should have performance comparable to v0.15.1.

Suspected cause

The regression appears to have been introduced by commit
d90ab51:

Report the correct column for an undefined global reference

The commit added the following code to the TOK_IDENT path in
js_parse_postfix_expr:

const uint8_t *identifier_line_start = s->token.ptr;

while (identifier_line_start > s->buf_start &&
       identifier_line_start[-1] != '\n' &&
       identifier_line_start[-1] != '\r')
    identifier_line_start--;

int identifier_col_num =
    (int)(s->token.ptr - identifier_line_start) + 1;

This scans backward from every identifier reference to the beginning of its
line.

For the one-line reproducer, the amount of work is approximately:

offset(identifier 1) +
offset(identifier 2) +
...
offset(identifier N)

As the offset grows for every identifier, the total parsing cost becomes
O(n²).

In the multiple-line version, each backward scan stops almost immediately at
the preceding newline, so the same identifier references are parsed in
approximately linear time.

Profiling frequently shows js_parse_expr_binary in the outer
recursive-descent parser stack, while the hot leaf is inside
js_parse_postfix_expr at this backward scan.

Suggested fix

Track the start of the current source line in JSParseState, or maintain an
accurate token column during lexical analysis, so the identifier column can
be obtained in O(1) time.

This would preserve the improved error location introduced by d90ab51
without scanning backward for every identifier reference.

Environment

• QuickJS-NG: v0.16.0
• Architecture: arm64
• Hardware: Apple M3 Pro
• OS: macOS 15.7.3
• Compiler: Apple Clang 17.0.0
• CMake: 4.1.2
• Ninja: 1.13.1
• Package manager: vcpkg

[starxg]

#1630