CODEWITHSUNDEEP
visual-studio-coderopes
Le Phong Vu
Le Phong Vu

Reputation: 156

Which Data structure used in Visual Studio Code

I know that Notepad++ used Gap Buffer, and XI editor used Rope. But I don't know which data structure behind the Visual Studio Code.

Do you know which data structure used in Visual Studio Code?

Upvotes: 0

Views: 927

Answers (1)

bouteillebleu
bouteillebleu

Reputation: 2493

Based on an article on the Visual Studio website about how the text buffer was implemented for Visual Studio Code 1.21, the text buffer is apparently represented by a piece table - a data structure that stores the initial text in one node, and then subsequent edits in other nodes.

They then improved its performance by:

  • caching the starts of lines, to make it easier to jump around the text buffer
  • making sure the initial text didn't get too big for their Javascript engine (V8) to handle, by storing the initial text as a list of buffers
  • reworking that cache of starts of lines to use a red-black tree for even better performance

to get what the author calls a "Multiple buffer piece table with red-black tree, optimized for line model" and then immediately shortens to "piece tree".

Upvotes: 2

Related Questions