7 ms·

Ropes, an Alternative to Strings [pdf] (1995)

133 points by pmoriarty 6y ago

cbhl 6y ago
If you're looking for an open-source implementation of a string-like sequence as a tree of chunks, consider absl::Cord. https://github.com/abseil/abseil-cpp/blob/master/absl/strings/cord.h https://github.com/abseil/abseil-cpp/blob/master/absl/string... Do read the caveats in the header comments before using it in lieu of std::string.
- deleted 6y ago
  [deleted]
chrisseaton 6y ago
TruffleRuby is an implementation of Ruby that uses ropes instead of character arrays for strings, if you want to see a modern implementation in practice. It works brilliantly for mostly string concatenation workloads, like rendering web page templates. Gets tricky when you decide to flatten it if people are repeatedly mutating single characters or indexing. Cool thing is that it can provide a char* interface to a rope data structure, in order to support C extensions not expecting ropes. https://rubybib.org/#menard2018 https://rubybib.org/#menard2018
- chubot 6y ago
  This was an interesting paper, and I read over it while thinking about implementing ropes for https://www.oilshell.org/ https://www.oilshell.org/ (which would be a huge change, affecting the entire interpreter, since all shell scripts mostly deal with strings) What surprised me is that Ruby template engines make heavy use of string concatenation? Like 'a' + 'b' ? The generated Ruby fragment from ERB makes heavy use ofstring concatenation, which is generally favorable to ropes. Theright-most graph of Figure 5 shows that TruffleRuby ropes are 9.4× faster than MRI, rendering around 870 000 templates per second. I would have thought the idiom for writing a template engine is to use something like Java's StringBuffer, or the Python pattern of appending immutable strings to a list, and joining them at the end. So you avoid a ton of intermediate strings that way. (And I have written a template engine myself in both Python and JS, and that is the technique I used, and it's plenty fast) Would that technique speed up ERB, or is there something I'm missing? Not to say it's not worthwhile to still do ropes, but it seems like low hanging fruit. ----- Though what turned me off of ropes is that for many workloads, most strings are small. And small strings are often smaller than records of pointers (and they have more locality). If I have a pointer to a string, a start offset, and an end offset, on machines that's 8 + 4 + 4 = 16 bytes, which is already approaching the size of an HTML tag or two. And a GC has to chase that pointer (in my situation), whereas a GC can stop if it's a blob of bytes. Not to say it's not a useful technique of course ... I think it does make sense as an optimization when you have existing workloads to measure, but I was hesistant to do it starting from scratch. ----- somewhat related: Elixir RAM and the Template of Doom https://www.evanmiller.org/elixir-ram-and-the-template-of-doom.html https://www.evanmiller.org/elixir-ram-and-the-template-of-do... (a syscall optimization that goes well with ropes)
  - chrisseaton 6y ago
    I don't think ERB literally does +, I think it does <<, which is exactly the same as the string buffer thing you're suggesting. But doesn't appending to a string buffer still mean copying a lot of bytes as you build up the final string? In ropes you don't need to copy anything, you just create a little node of a couple of words to remember that two strings were joined. Yeah there's non-locality and things like that, but most people are building up strings not reading them. Then you write out the final string - and we have system calls like writev that work with ropes. Finally, remember that if your string is created and used within a single compilation unit remember that rope nodes with disappear with escape-analysis and scalar-replacement-of-aggregates. Helps operations on strings fold and become constant.
    - bonzini 6y ago
      Appending to a string buffer that grows exponentially will copy roughly twice as many bytes as building the result in a buffer that has the exact size. If you have to copy out of the resizable buffer into an exact-size area of memory, that becomes three times.
      - kd5bjo 6y ago
        Also, once your buffer exceeds the virtual memory page size, those copies turn into page table updates that never touch the string data.
    - mpweiher 6y ago
      > copying a lot of bytes Depends on what you mean by "a lot", doesn't it? Yes, you are going to copy all the bytes in the final result once (at least). But it's hard to see how to avoid that, and no, delegating that task to the kernel doesn't magically/consistently make it faster. > you just create a little node of a couple of words Hmm..."just" creating a "little" node can often be quite expensive on today's machines. And "words" are pretty big, typically 8 bytes per word. > Yeah there's non-locality and things like that Well, non-locality and "things like that" are kind of a biggie, these days. The biggie, actually, most of the time. "...computation is essentially free, because it happens “in the cracks” between data fetch and data store; on a clocked processor, there is little difference in energy consumption between performing an arithmetic operation and performing a no-op." -- Andrew Black in Object-oriented programming: some history, and challenges for the next fifty years
- pmoriarty 6y ago
  Chicken Scheme has a rope egg: http://wiki.call-cc.org/eggref/5/rope http://wiki.call-cc.org/eggref/5/rope
- ibraheemdev 6y ago
  Hey Chris. Completely unrelated question. I've been following your work on truffleruby (it looks pretty awesome btw), and I was wondering what the ultimate goal was? Do you believe truffleruby can eventually become the goto Ruby for Rails developers? Is Shopify going to completely move to truffle and the graalvm?
  - deleted 6y ago
    [deleted]
neolog 6y ago
(1995)
secondcoming 6y ago
SGI's C++ shipped with a rope implementation but it was never standardised oddly. https://stackoverflow.com/questions/2826431/stl-rope-when-and-where-to-use https://stackoverflow.com/questions/2826431/stl-rope-when-an...
- jeffbee 6y ago
  GNU still ships it. https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/ext/rope https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-...
deleted 6y ago
[deleted]
doomrobo 6y ago
Here's some very thorough documentation of the use of ropes a modern text editor https://abishov.com/xi-editor/docs/rope_science_00.html https://abishov.com/xi-editor/docs/rope_science_00.html
ibraheemdev 6y ago
Would calling it a 'tree' be more fitting than 'rope'? The paper already used the term 'leaves'
- sgtnoodle 6y ago
  The word "tree" already has a very general and overloaded meaning within the context of data structures. Presumably, this "rope" implementation is using a tree structure internally, but that's true of many thousands of things; it's a basic foundation of data structures and computer science. I assume "rope" was chosen as a tongue in cheek alternative to "string".
- jeffbee 6y ago
  I always figured rope was just meant to imply that it was bigger than string.
- chrisseaton 6y ago
  'Ropes' are built using 'trees'. They're more specific than trees. Otherwise, why do we say 'trees' when we could use the more general term 'graphs' if that's your argument?
omginternets 6y ago
What's the catch? Why hasn't this become the standard way to represent text?
- jeffbee 6y ago
  Representing a short string as a contiguous vector of characters takes much less CPU time. The rope doesn't really hit its stride until you want to do something that a vector is bad at, such as splicing something into the middle of a long string.
- ehnto 6y ago
  I did like the quote "While strings are occasionally the right choice..." Nearly three decades of utility since, quite the occasion! Certainly, we could all have been wrong this entire time. So often in programming I find that my working, perfectly useful software, unbeknownst to me, was wrong all along! Imagine my face on the day! (I am being facetious, it is of course perfectly valid to challenge the status quo)
- raphlinus 6y ago
  It depends hugely on the workload. Ropes are ideal for editing sessions, where you have a sequence of small edits on a large string. But if the string is small, just storing it contiguously is simpler and faster. They're also good for forming larger strings by concatenating smaller ones. But if you can structure your code so that it just appends to a buffer, for example, by threading a mutable string buffer reference through function calls rather than returning strings, that's also faster. So, as with most such tradeoffs, it depends on what you're trying to do.
- vbezhenar 6y ago
  CPUs are very fast at copying memory. And continuous memory allows for efficient use of CPU caches. So for small string sizes simple algorithms are better. Another reason might be compacting GC. When you compact the heap, you need to rewrite pointers. So you need less objects overall and less pointers. When your string is just one array, it's much more friendly than having bunch of substrings with pointers. If you're dealing with megabyte strings, you need to think about algorithms, ropes might be the right choice.
RcouF1uZ4gsC 6y ago
I think the ropes are less useful now than they were in 1995 because of the evolution of CPU and memory systems. In 1995 100 Mhz was considered a fast speed, and memory access was not that much slower than the CPU. Now CPU's are in the GHZ ranges, and memory is a huge bottleneck. This is why a significant portion of the CPU is the integrated memory controller and various levels of cache. With the current paradigm, cache friendliness will often trump something that has fewer instructions. With regular strings, scanning or copying a string is in order memory access which will take advantage of pre-fetching of the cache. With ropes, there will be pointer chasing which will cause all sorts of cache misses. So, I think ropes are likely an even more niche use case than they were in 1995.
- fn1 6y ago
  This is also why ArrayList is almost always faster than LinkedList in Java.
- kazinator 6y ago
  > memory access was not that much slower than the CPU. Yes it was. 1995 was not 1965. > This is why a significant portion of the CPU is the integrated memory controller and various levels of cache. Microprocessor architectures available in 1995 had L1 and L2 caches. L2 was available for Pentiums, so it basically trickled to the consumer market. These caches were small: misses were more likely, so optimizing for locality was super important. I remember hearing that same talk in the 1990's: you don't want linked lists: think of the pointer chasing and cache misses, and the storage overhead for the pointers that wastes your precious little cache space (8K in an 80486). > With regular strings, scanning or copying a string is in order memory access which will take advantage of pre-fetching of the cache. The point of ropes is to handle very long strings. Scanning a long string, many kilobytes or even megabytes long, is not a simple memory access, though. If you have to copy the entire tail of the flat string to insert a character, but a rope does not, the rope can win in that case. See the motivating statements in the paper: "Common string operations should scale to long strings. There should be nopractical bound on the length of strings. Performance should remain acceptable for long strings." There are various trade-off levels possible in ropes depending on the chunk sizes: a rope can have a small number of large pieces or a large number of small ones. I suspect why ropes are perhaps not popular is that people don't care that much about the utmost performance in string processing. A performance hiccup in some string processing isn't going to make video skip, a game framerate lag, or a CNC cutter spoil a piece. A lot of text processing is batch processing, or else non-real-time interactive (like in a text editor). Moreover, the cases where ropes are useful (huge strings) are a niche within text processing. People often don't have long strings so they don't feel the sting of bad performance.
pjmlp 6y ago
Mesa/Cedar on Xerox PARC also used ropes for its strings implementation, as info.
vanderZwan 6y ago
I recall that a couple of years ago most browsers started putting a lot of effort into optimizing their string implementations regarding concatenation, so that makes me wonder: do browsers use ropes? Or is there some other data structure that is better optimized for how people commonly use strings in the browser?
skohan 6y ago
Xi was planning to use a rope as the main data structure right?
- raphlinus 6y ago
  xi-editor does use xi-rope as its main text storage data structure. This part worked well; the problems with xi were much more around the CRDT and the fully async design. I did a RustLab talk on the use of immutable data structures (of which rope is a good example) for incremental UI, and this will be published soonish.
  - skohan 6y ago
    Yeah I remember thinking the async design seemed a bit over-engineered. It seemed like they were approaching the UI constraints almost like they were developing a game engine, which doesn't seem needed for a text editor. For a great many actions, in that setting it's acceptable to have synchronous actions between key press and view update.
shouyatf 6y ago
Interestingly, this data structure looks quite similar to iolist in erlang.
mikewarot 6y ago
I think a hybrid approach would work these days... because pointers are 8 bytes long, and you need a few of them just to make a node... perhaps all chunks less than N (200ish?) bytes long could be stored flat in the node? Also, it would be good to store both the Byte Count, and the Character Count, now that we have UTF-8, etc... and ensure characters don't get split across nodes. This would give us structures that work well in multi-processor environments, due to the immutability and lock-free nature, handle Unicode in a sane and safe manner that saves a lot of headaches, and does small common operations in a fast manner saving many pointer operations.
rmu09 6y ago
The tk (of tcl/tk) multiline text widget uses a BTree to store the text.
einpoklum 6y ago
Premature optimization is the root of all evil. If we were to use these instead of strings by default, we would probably end up referring to them as nooses rather than ropes.
ulucs 6y ago
I wouldn't expect this to be obscure information, but JS uses ropes for strings as a default: https://accidentallyquadratic.tumblr.com/post/142387131042/nodejs-left-pad https://accidentallyquadratic.tumblr.com/post/142387131042/n...
jbperry 6y ago
AvalonEdit, the text editor for SharpDevelop implemented ropes. I think SharpDevelop was folded into MonoDevelop and the text editor there was changed. So I don't think MonoDevelop currently uses ropes? http://avalonedit.net/ http://avalonedit.net/ https://github.com/icsharpcode/AvalonEdit/blob/master/ICSharpCode.AvalonEdit/Utils/CharRope.cs https://github.com/icsharpcode/AvalonEdit/blob/master/ICShar...

133 points by pmoriarty 6y ago

cbhl 6y ago

If you're looking for an open-source implementation of a string-like sequence as a tree of chunks, consider absl::Cord. https://github.com/abseil/abseil-cpp/blob/master/absl/strings/cord.h https://github.com/abseil/abseil-cpp/blob/master/absl/string... Do read the caveats in the header comments before using it in lieu of std::string.

deleted 6y ago
[deleted]

chrisseaton 6y ago

TruffleRuby is an implementation of Ruby that uses ropes instead of character arrays for strings, if you want to see a modern implementation in practice. It works brilliantly for mostly string concatenation workloads, like rendering web page templates. Gets tricky when you decide to flatten it if people are repeatedly mutating single characters or indexing. Cool thing is that it can provide a char* interface to a rope data structure, in order to support C extensions not expecting ropes. https://rubybib.org/#menard2018 https://rubybib.org/#menard2018

chubot 6y ago
This was an interesting paper, and I read over it while thinking about implementing ropes for https://www.oilshell.org/ https://www.oilshell.org/ (which would be a huge change, affecting the entire interpreter, since all shell scripts mostly deal with strings) What surprised me is that Ruby template engines make heavy use of string concatenation? Like 'a' + 'b' ? The generated Ruby fragment from ERB makes heavy use ofstring concatenation, which is generally favorable to ropes. Theright-most graph of Figure 5 shows that TruffleRuby ropes are 9.4× faster than MRI, rendering around 870 000 templates per second. I would have thought the idiom for writing a template engine is to use something like Java's StringBuffer, or the Python pattern of appending immutable strings to a list, and joining them at the end. So you avoid a ton of intermediate strings that way. (And I have written a template engine myself in both Python and JS, and that is the technique I used, and it's plenty fast) Would that technique speed up ERB, or is there something I'm missing? Not to say it's not worthwhile to still do ropes, but it seems like low hanging fruit. ----- Though what turned me off of ropes is that for many workloads, most strings are small. And small strings are often smaller than records of pointers (and they have more locality). If I have a pointer to a string, a start offset, and an end offset, on machines that's 8 + 4 + 4 = 16 bytes, which is already approaching the size of an HTML tag or two. And a GC has to chase that pointer (in my situation), whereas a GC can stop if it's a blob of bytes. Not to say it's not a useful technique of course ... I think it does make sense as an optimization when you have existing workloads to measure, but I was hesistant to do it starting from scratch. ----- somewhat related: Elixir RAM and the Template of Doom https://www.evanmiller.org/elixir-ram-and-the-template-of-doom.html https://www.evanmiller.org/elixir-ram-and-the-template-of-do... (a syscall optimization that goes well with ropes)
- chrisseaton 6y ago
  I don't think ERB literally does +, I think it does <<, which is exactly the same as the string buffer thing you're suggesting. But doesn't appending to a string buffer still mean copying a lot of bytes as you build up the final string? In ropes you don't need to copy anything, you just create a little node of a couple of words to remember that two strings were joined. Yeah there's non-locality and things like that, but most people are building up strings not reading them. Then you write out the final string - and we have system calls like writev that work with ropes. Finally, remember that if your string is created and used within a single compilation unit remember that rope nodes with disappear with escape-analysis and scalar-replacement-of-aggregates. Helps operations on strings fold and become constant.
  - bonzini 6y ago
    Appending to a string buffer that grows exponentially will copy roughly twice as many bytes as building the result in a buffer that has the exact size. If you have to copy out of the resizable buffer into an exact-size area of memory, that becomes three times.
    - kd5bjo 6y ago
      Also, once your buffer exceeds the virtual memory page size, those copies turn into page table updates that never touch the string data.
  - mpweiher 6y ago
    > copying a lot of bytes Depends on what you mean by "a lot", doesn't it? Yes, you are going to copy all the bytes in the final result once (at least). But it's hard to see how to avoid that, and no, delegating that task to the kernel doesn't magically/consistently make it faster. > you just create a little node of a couple of words Hmm..."just" creating a "little" node can often be quite expensive on today's machines. And "words" are pretty big, typically 8 bytes per word. > Yeah there's non-locality and things like that Well, non-locality and "things like that" are kind of a biggie, these days. The biggie, actually, most of the time. "...computation is essentially free, because it happens “in the cracks” between data fetch and data store; on a clocked processor, there is little difference in energy consumption between performing an arithmetic operation and performing a no-op." -- Andrew Black in Object-oriented programming: some history, and challenges for the next fifty years
pmoriarty 6y ago
Chicken Scheme has a rope egg: http://wiki.call-cc.org/eggref/5/rope http://wiki.call-cc.org/eggref/5/rope
ibraheemdev 6y ago
Hey Chris. Completely unrelated question. I've been following your work on truffleruby (it looks pretty awesome btw), and I was wondering what the ultimate goal was? Do you believe truffleruby can eventually become the goto Ruby for Rails developers? Is Shopify going to completely move to truffle and the graalvm?
- deleted 6y ago
  [deleted]

neolog 6y ago

(1995)

secondcoming 6y ago

SGI's C++ shipped with a rope implementation but it was never standardised oddly. https://stackoverflow.com/questions/2826431/stl-rope-when-and-where-to-use https://stackoverflow.com/questions/2826431/stl-rope-when-an...

jeffbee 6y ago
GNU still ships it. https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/ext/rope https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-...

deleted 6y ago

[deleted]

doomrobo 6y ago

Here's some very thorough documentation of the use of ropes a modern text editor https://abishov.com/xi-editor/docs/rope_science_00.html https://abishov.com/xi-editor/docs/rope_science_00.html

ibraheemdev 6y ago

Would calling it a 'tree' be more fitting than 'rope'? The paper already used the term 'leaves'

sgtnoodle 6y ago
The word "tree" already has a very general and overloaded meaning within the context of data structures. Presumably, this "rope" implementation is using a tree structure internally, but that's true of many thousands of things; it's a basic foundation of data structures and computer science. I assume "rope" was chosen as a tongue in cheek alternative to "string".
jeffbee 6y ago
I always figured rope was just meant to imply that it was bigger than string.
chrisseaton 6y ago
'Ropes' are built using 'trees'. They're more specific than trees. Otherwise, why do we say 'trees' when we could use the more general term 'graphs' if that's your argument?

omginternets 6y ago

What's the catch? Why hasn't this become the standard way to represent text?

jeffbee 6y ago
Representing a short string as a contiguous vector of characters takes much less CPU time. The rope doesn't really hit its stride until you want to do something that a vector is bad at, such as splicing something into the middle of a long string.
ehnto 6y ago
I did like the quote "While strings are occasionally the right choice..." Nearly three decades of utility since, quite the occasion! Certainly, we could all have been wrong this entire time. So often in programming I find that my working, perfectly useful software, unbeknownst to me, was wrong all along! Imagine my face on the day! (I am being facetious, it is of course perfectly valid to challenge the status quo)
raphlinus 6y ago
It depends hugely on the workload. Ropes are ideal for editing sessions, where you have a sequence of small edits on a large string. But if the string is small, just storing it contiguously is simpler and faster. They're also good for forming larger strings by concatenating smaller ones. But if you can structure your code so that it just appends to a buffer, for example, by threading a mutable string buffer reference through function calls rather than returning strings, that's also faster. So, as with most such tradeoffs, it depends on what you're trying to do.
vbezhenar 6y ago
CPUs are very fast at copying memory. And continuous memory allows for efficient use of CPU caches. So for small string sizes simple algorithms are better. Another reason might be compacting GC. When you compact the heap, you need to rewrite pointers. So you need less objects overall and less pointers. When your string is just one array, it's much more friendly than having bunch of substrings with pointers. If you're dealing with megabyte strings, you need to think about algorithms, ropes might be the right choice.

RcouF1uZ4gsC 6y ago

I think the ropes are less useful now than they were in 1995 because of the evolution of CPU and memory systems. In 1995 100 Mhz was considered a fast speed, and memory access was not that much slower than the CPU. Now CPU's are in the GHZ ranges, and memory is a huge bottleneck. This is why a significant portion of the CPU is the integrated memory controller and various levels of cache. With the current paradigm, cache friendliness will often trump something that has fewer instructions. With regular strings, scanning or copying a string is in order memory access which will take advantage of pre-fetching of the cache. With ropes, there will be pointer chasing which will cause all sorts of cache misses. So, I think ropes are likely an even more niche use case than they were in 1995.

fn1 6y ago
This is also why ArrayList is almost always faster than LinkedList in Java.
kazinator 6y ago
> memory access was not that much slower than the CPU. Yes it was. 1995 was not 1965. > This is why a significant portion of the CPU is the integrated memory controller and various levels of cache. Microprocessor architectures available in 1995 had L1 and L2 caches. L2 was available for Pentiums, so it basically trickled to the consumer market. These caches were small: misses were more likely, so optimizing for locality was super important. I remember hearing that same talk in the 1990's: you don't want linked lists: think of the pointer chasing and cache misses, and the storage overhead for the pointers that wastes your precious little cache space (8K in an 80486). > With regular strings, scanning or copying a string is in order memory access which will take advantage of pre-fetching of the cache. The point of ropes is to handle very long strings. Scanning a long string, many kilobytes or even megabytes long, is not a simple memory access, though. If you have to copy the entire tail of the flat string to insert a character, but a rope does not, the rope can win in that case. See the motivating statements in the paper: "Common string operations should scale to long strings. There should be nopractical bound on the length of strings. Performance should remain acceptable for long strings." There are various trade-off levels possible in ropes depending on the chunk sizes: a rope can have a small number of large pieces or a large number of small ones. I suspect why ropes are perhaps not popular is that people don't care that much about the utmost performance in string processing. A performance hiccup in some string processing isn't going to make video skip, a game framerate lag, or a CNC cutter spoil a piece. A lot of text processing is batch processing, or else non-real-time interactive (like in a text editor). Moreover, the cases where ropes are useful (huge strings) are a niche within text processing. People often don't have long strings so they don't feel the sting of bad performance.

pjmlp 6y ago

Mesa/Cedar on Xerox PARC also used ropes for its strings implementation, as info.

vanderZwan 6y ago

I recall that a couple of years ago most browsers started putting a lot of effort into optimizing their string implementations regarding concatenation, so that makes me wonder: do browsers use ropes? Or is there some other data structure that is better optimized for how people commonly use strings in the browser?

skohan 6y ago

Xi was planning to use a rope as the main data structure right?

raphlinus 6y ago
xi-editor does use xi-rope as its main text storage data structure. This part worked well; the problems with xi were much more around the CRDT and the fully async design. I did a RustLab talk on the use of immutable data structures (of which rope is a good example) for incremental UI, and this will be published soonish.
- skohan 6y ago
  Yeah I remember thinking the async design seemed a bit over-engineered. It seemed like they were approaching the UI constraints almost like they were developing a game engine, which doesn't seem needed for a text editor. For a great many actions, in that setting it's acceptable to have synchronous actions between key press and view update.

shouyatf 6y ago

Interestingly, this data structure looks quite similar to iolist in erlang.

mikewarot 6y ago

I think a hybrid approach would work these days... because pointers are 8 bytes long, and you need a few of them just to make a node... perhaps all chunks less than N (200ish?) bytes long could be stored flat in the node? Also, it would be good to store both the Byte Count, and the Character Count, now that we have UTF-8, etc... and ensure characters don't get split across nodes. This would give us structures that work well in multi-processor environments, due to the immutability and lock-free nature, handle Unicode in a sane and safe manner that saves a lot of headaches, and does small common operations in a fast manner saving many pointer operations.

rmu09 6y ago

The tk (of tcl/tk) multiline text widget uses a BTree to store the text.

einpoklum 6y ago

Premature optimization is the root of all evil. If we were to use these instead of strings by default, we would probably end up referring to them as nooses rather than ropes.

ulucs 6y ago

I wouldn't expect this to be obscure information, but JS uses ropes for strings as a default: https://accidentallyquadratic.tumblr.com/post/142387131042/nodejs-left-pad https://accidentallyquadratic.tumblr.com/post/142387131042/n...

jbperry 6y ago

AvalonEdit, the text editor for SharpDevelop implemented ropes. I think SharpDevelop was folded into MonoDevelop and the text editor there was changed. So I don't think MonoDevelop currently uses ropes? http://avalonedit.net/ http://avalonedit.net/ https://github.com/icsharpcode/AvalonEdit/blob/master/ICSharpCode.AvalonEdit/Utils/CharRope.cs https://github.com/icsharpcode/AvalonEdit/blob/master/ICShar...