Which Data structure used in Visual Studio Code

820 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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