4 ms·

Interesting! I find it amazing that they went all the way into implementing a CDRT to support efficient plugins. At the moment I am also writing a text-editor

Interesting! I find it amazing that they went all the way into implementing a CDRT to support efficient plugins. At the moment I am also writing a text-editor with my partner, to show-case the C++ RRB-Trees implementations in Immer [1]. We are just started, but my plan is to stop at 1000k lines. Interestingly, with such persistent data structure, you go already a long way in implementing undo, parallel processing, and many editing algorithms are super simple thanks to slicing/concat. Memory consumption is still sub-optimal (also I am using wchar_t to simplify my life), but I am very satisfied with the results so far (it is the fastest editor I have on my machine when editing 1GB file, also can edit a ~100MB file on a Raspberry --- larger files fail only due to excessive memory use :/). [1] https://github.com/arximboldi/immer https://github.com/arximboldi/immer

geezerjay 10y ago
Pardon my ignorance, but what's a CDRT?
- NamPNQ 10y ago
  CDRT maybe Conflict-free Replicated Data Types
- untangle 10y ago
  Probably meant CRDT https://hal.inria.fr/inria-00445975/document https://hal.inria.fr/inria-00445975/document
- oconnor663 10y ago
  Here's the relevant section: https://github.com/google/xi-editor/blob/master/doc/rope_science/rope_science_09.md#a-crdt-approach-to-async-plugins-and-undo https://github.com/google/xi-editor/blob/master/doc/rope_sci...
hawski 10y ago
I wonder how rope behaves after lots of changes. Take 1GB file, modify every line multiple times. Now whole file is partitioned severely. Moving around a file could be much slower. For me moving around file quickly is much more important then big edits. Probably practically it's still good enough. I'm developing my own text editor. To test naive implementation of text editing routines - array of line strings. I concatenated all sources of recent Linux kernel 4.6.3 once. From what I remember it was all .c, .h and .S files. Resulting file had 542MB and 19'726'498 lines. It was good enough even adding a line at front.
- raphlinus 10y ago
  The true strength of the rope data structure its performance in worst case conditions. Even after a huge series of edits, it recombines leaves and rebalances the tree so it's almost as efficient as when it's loaded freshly. It's not like a piece table, which is amazingly efficient at first and then fragments. [The actual analysis is much more subtle, as the tree invariants are a minimum and maximum number of children for non-root non-leaf nodes, and a minimum and maximum leaf size. When freshly loaded, the code is careful to maximally pack both, and after extensive editing the distribution will be more varied. However, it's still rigorously O(log n), so it ends up being a small constant factor. Might be worth doing some empirical performance testing.]

geezerjay 10y ago

Pardon my ignorance, but what's a CDRT?

NamPNQ 10y ago
CDRT maybe Conflict-free Replicated Data Types
untangle 10y ago
Probably meant CRDT https://hal.inria.fr/inria-00445975/document https://hal.inria.fr/inria-00445975/document
oconnor663 10y ago
Here's the relevant section: https://github.com/google/xi-editor/blob/master/doc/rope_science/rope_science_09.md#a-crdt-approach-to-async-plugins-and-undo https://github.com/google/xi-editor/blob/master/doc/rope_sci...

hawski 10y ago

I wonder how rope behaves after lots of changes. Take 1GB file, modify every line multiple times. Now whole file is partitioned severely. Moving around a file could be much slower. For me moving around file quickly is much more important then big edits. Probably practically it's still good enough. I'm developing my own text editor. To test naive implementation of text editing routines - array of line strings. I concatenated all sources of recent Linux kernel 4.6.3 once. From what I remember it was all .c, .h and .S files. Resulting file had 542MB and 19'726'498 lines. It was good enough even adding a line at front.

raphlinus 10y ago
The true strength of the rope data structure its performance in worst case conditions. Even after a huge series of edits, it recombines leaves and rebalances the tree so it's almost as efficient as when it's loaded freshly. It's not like a piece table, which is amazingly efficient at first and then fragments. [The actual analysis is much more subtle, as the tree invariants are a minimum and maximum number of children for non-root non-leaf nodes, and a minimum and maximum leaf size. When freshly loaded, the code is careful to maximally pack both, and after extensive editing the distribution will be more varied. However, it's still rigorously O(log n), so it ends up being a small constant factor. Might be worth doing some empirical performance testing.]