back

by raphlinus·9y ago·view on hn ↗
The first part of the article is true; gap buffers are not a data structure particularly optimized for multiple cursor edits. The conclusion is ridiculous. Of course you can provoke noticeable slowdown by doing an edit with thousands of cursors, but most people are doing small edits to small files, so the cost of the memmove operations is probably in the microseconds per cursor range. If multiple cursors feel intuitive to use and gives immediate visual feedback, why shouldn't people use them?

I say this as someone who has chosen a more sophisticated data structure (ropes) in the editor I'm working on.

5 comments
Beside data structure based on B+ tree (ropes), what do you think about Relaxed Radix Balanced Vector tree[0]? It is cache-friendly and immutable as well.

[0](https://icfp17.sigplan.org/event/icfp-2017-papers-persistenc...)

Looks pretty neat, thanks for the link. From a quick look, it seems like the performance characteristics will be pretty similar to a xi-style rope (it seems extremely unlikely to me that the time spent finding the child is significant, so the radix trick can't save much time), and it's a bit more complex. That said, I do expect it to perform nicely for read-only access to large documents, which is definitely an important use case.

It would make a fun project for somebody to implement it and compare the performance. I'd certainly take the PR for it if the performance was better :)

[edit: followup] The rope implementation in xi has an additional heuristic that tries not to split lines across leaf boundaries (ie most leaves should end in a newline). It also has a hard constraint of not splitting a unicode codepoint. Thus, leaves and subtrees would have an unpredictable number of elements (as opposed to being a clean power of two when full) and I think that pretty much invalidates using the radix to select the child.

I took it as a joke. Obviously one shouldn't concern themselves with how their editors store the text while editing. Furthermore macros or rectangular editing (which the author argues are superior to multiple cursors) have exactly the same performance issues on big files. If multiple cursors are really useful then one should use them.

But I think the author makes a good case about why it's a rather pointless feature in the end. Macros and rectangular edition are strictly more powerful than multiple cursors. That's a good reason to prefer them over multiple cursors.

I'd say multiple cursors are strictly more powerful than rectangular edits, since every rectangle can be outlined using multiple cursors, but they can also cover non-rectangular areas. Macros are of course even more powerful.

What I like about multiple cursors is the immediate feedback, although I have yet to see an implementation that can emulate search-and-replace with capture groups.

You can have immediate feedback for search-and-replace without multiple cursors too, no?
My solution is to put the buffer implementation into a module that is used as a dependency for a standardized "buffer" functionality. That way, if I know a piece-buffer or rope will be more efficient, I can choose which implementation to fills the dependency.
> the editor I'm working on.

Why are you working on an editor? Serious question.

What editor are you working on?
He's the author of the Xi editor: https://github.com/google/xi-editor