Add a simple queue implementation with better performance than Array.shift
#49623
Conversation
….shift` This lets us clean up the hack introduced in microsoft#49581
typescript-bot
added
Author: Team
For Uncommitted Bug
|
amcasey:Queue |
Co-authored-by: Mateusz Burzyński <[email protected]>
|
@captain-yossarian Neither change is particularly specific to TS. Basically, when you |
|
@amcasey Thank you very much for explanation |
| const q = [node]; | ||
| while (q.length && i < 100) { | ||
| const q = createQueue<Expression>(); | ||
| q.enqueue(node); |
There was a problem hiding this comment.
To me this part of the code seems like that order wouldnt matter so always using last element so i wonder if always using last element and keeping tail thats used to add more items and sets array.length to compact array once in a while might be better.
Thoughts?
There was a problem hiding this comment.
I didn't read it carefully when I made the change - I just checked that it would behave the same after. Reading it now, it looks like switching from a queue to a stack would change a BFS to a DFS, which may or may not be desirable.
| @@ -504,18 +504,18 @@ namespace ts.server { | |||
| // If `getResultsForPosition` returns results for a project, they go in here | |||
| const resultsMap = new Map<Project, readonly TResult[]>(); | |||
|
|
|||
| const queue: ProjectAndLocation[] = []; | |||
| const queue = createQueue<ProjectAndLocation>(); | |||
There was a problem hiding this comment.
Even here, does order matter if not we could get away with having to move array elements right?
There was a problem hiding this comment.
I believe order does matter, though that doesn't necessarily mean we couldn't accomplish the same thing with a stack.
There was a problem hiding this comment.
why does order matter ? in all find all references etc when aggregating results between project, the order shouldnt matter right ? Yes our baselines may change but from end to end result perspective order shouldnt matter ?
There was a problem hiding this comment.
I believe the search order affects the value of isDefinition. I believe it's also the case that FAR is asymmetric (B being a reference to A, does not imply that A is a reference to B), but I think we've already decided to ignore that restriction, so it's probably just isDefinition. Now that isDefinition is computed in a post-pass, it's possible that we can drop the strict ordering, but I'm frankly pretty burned out on rewriting this code. I have no objections if you'd like to, but I'd suggest we wait until 4.9, now that we're in the RC period.
This lets us clean up the hack introduced in #49581