Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

`sourceCode.getNodeByRangeIndex` performance issue #4989

Closed
mysticatea opened this Issue Jan 18, 2016 · 4 comments

Comments

Projects
None yet
3 participants
@mysticatea
Copy link
Member

mysticatea commented Jan 18, 2016

From https://gitter.im/eslint/eslint?at=569c4f4d3165a6af1a3c588c

sourceCode.getNodeByRangeIndex has an unintentional performance issue.

result is assigned always a new instance at L263, so the condition at L269 never gets true. So even if the matched node was found, this continues traversing until the last.

Currently:

// sourceCode.getNodeByRangeIndex(6)
Program ( var answer = 6 * 7; )
    found, dive into...
    VariableDeclaration ( var answer = 6 * 7; )
        found, dive into...
        VariableDeclarator ( answer = 6 * 7 )
            found, dive into...
            Identifier ( answer )
                found, dive into...
            Identifier :exit            // FOUND! I expect to break here but not.
            BinaryExpression ( 6 * 7 )
                Skip!
            BinaryExpression :exit
        VariableDeclarator :exit
    VariableDeclaration :exit
Program :exit

Expected:

// sourceCode.getNodeByRangeIndex(6)
Program ( var answer = 6 * 7; )
    found, dive into...
    VariableDeclaration ( var answer = 6 * 7; )
        found, dive into...
        VariableDeclarator ( answer = 6 * 7 )
            found, dive into...
            Identifier ( answer )
                found, dive into...
            Identifier :exit
            Break!
@lo1tuma

This comment has been minimized.

Copy link
Member

lo1tuma commented Jan 18, 2016

Wouldn’t it be better to remove the additional traversal in getNodeByRangeIndex and build a NodeStore similar to what we have with the TokenStore where we can access nodes directly by range index or location information?

@ilyavolodin

This comment has been minimized.

Copy link
Member

ilyavolodin commented Jan 18, 2016

@lo1tuma I'm not sure it's worth it. This is going to eat a lot of memory, and I don't see us using it too often.

@nzakas nzakas closed this in #4990 Jan 18, 2016

nzakas added a commit that referenced this issue Jan 18, 2016

Merge pull request #4990 from mysticatea/core/fix-get-node-by-range-i…
…ndex

Fix: `getNodeByRangeIndex` performance issue (fixes #4989)
@lo1tuma

This comment has been minimized.

Copy link
Member

lo1tuma commented Jan 18, 2016

@ilyavolodin Why do you think it would consume a lot of memory? We already have the AST in memory, the NodeStore would store only references to objects that already exist.

@ilyavolodin

This comment has been minimized.

Copy link
Member

ilyavolodin commented Jan 18, 2016

@lo1tuma On a large file, we are going to have a lot of AST Nodes, just the hash of index is going to take up memory space, even if content is going to be a reference, it's still not worth the trouble in my mind. I just can't think of a lot of places where we would need to get node by index.

@eslint eslint bot locked and limited conversation to collaborators Feb 6, 2018

@eslint eslint bot added the archived due to age label Feb 6, 2018

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
You can’t perform that action at this time.