Do you know of any assessment of performance characteristics for said ‘piece tables’? The thrust of TFA is essentially a performance comparison, so I can’t help but wonder why this implementation wasn’t addressed if it is present in one of the most widely used code editors. Also, VS Code is not known for its responsiveness for text editing, is this due to the ‘piece table’, or more likely, due to architectural decisions in the application more generally?

I’m not really up-to-date on any text editing implementation details, so if this is basic/common knowledge feel free to just tell me to Google it.

I implemented a Piece Tree like VS Code's not long ago and found the insert/delete performance fine, but performance for text retrieval (line retrieval, substring) queries wwas embarrassingly bad. Like, 10x slower than the other ropes I compared it with.

I think this comes down to two things:

1. Fragmentation. When a rope splits a string into two by inserting into it, it is able to rejoin the pieces to form a new string, which "greatly reduces space consumption and traversal times" (quote from the first paper on ropes: https://www.cs.tufts.edu/comp/150FP/archive/hans-boehm/ropes... ).

2. Proximity of nodes. In a Piece Tree, all of the inner nodes contain {start, length} piece data. You can construct the whole string represented by the Piece Tree through an in-order traversal. In contrast, the Rope only stores data at the leaves of the tree.

Imagine you are at the root of a Piece Tree that looks like this (where o = a node containing a piece).

      o
     / \
    o   o
   / \ / \
  o   oo  o

Say you want to get a substring from (root - 1) to (root + 1), one character before the tree's root up to one character after the root. How many tree nodes do you need to visit? We can understand by reminding ourselves that "the whole string can be reconstructed through an in order traversal", letting us know the order we need to visit nodes in.

      c
     / \
    v   v
   / \ / \
  o   cc  o

(where c = a node whose string we copy and v = a node we visit on our way to a node we need to copy). That is two separate O(log n) queries we make from the root of the tree for our substring operation.

What are ropes like in contrast?

      v
     / \
    v   o
   / \ / \
  c   co  o

You do still need basically two O(log n) queries, but not from the tree's root. You find the inner metadata node where the start of the substring and the end of the substring (and all strings in between) can be reached and make an in-order traversal from there, which is less traversal time. This, combined with the lower fragmentation that ropes enable (or rather that high fragmentation the Piece Tables have), makes them faster than Piece Trees in my experience.

(A Piece Table/Piece Tree is able to avoid creating new nodes if you insert consecutively, one character after another without backtracking to edit a previous part, since you could just extend the length of the piece. Real life benchmarking data tells me that's not a big advantage though: the text retrieval time is still embarrassingly bad.)

It's good to see Jetbrains avoid the Piece Table and its variants for Fleet (where they mention using a rope).

https://blog.jetbrains.com/fleet/2022/02/fleet-below-deck-pa...

(Note that the rope diagram I posted copies two strings and the Piece Tree copies three, which might be considered unfair. I didn't want to extend the rope diagram to make it copy three strings, but I would say this is actually an accurate depiction of reality considering the fragmentation the Piece Table/Tree has, meaning more nodes to visit.)