4 ms·

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, an

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.
- jcelerier 6y ago
  > 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). in a 2020 machine with a normal workload I have yet to see a list outperform a contiguous array outside of pathological cases > The point of ropes is to handle very long strings. Scanning a long string, many kilobytes or even megabytes long I mean, my 2016 CPU has 20 megabytes of L3 cache, you can fit a fair amount of text in that, likely more than 99.9% of average text editor usage
  - konjin 6y ago
    >in a 2020 machine with a normal workload I have yet to see a list outperform a contiguous array outside of pathological cases I guess an size(array)+1 is a pathological case. Shame it seems to happen in every code base I've looked at.
    - jcelerier 6y ago
      the question is, how often does it happen when compared to iterating over your loop ? Like, every codebase I've worked on had some array sorting at some point in it... but the frequency of needing to sort something vs having to loop over all the X makes it a completely not-relevant thing. If the only time you add an element to an array is as a result of the user clicking somewhere, then I'd say it's definitely not worth taking into account if your array isn't 5000000 elements (which it will likely won't be if you are giving the user the ability to just add something to it).
      - konjin 6y ago
        Enough to explode a rocket every decade. Not everyone works on js.
        jcelerier 6y ago
        I would be very surprised if there is any code that could potentially allocate in the hot (lol) path of a rocket. There'll just be static arrays in there.
skohan 6y ago
Maybe there's a hybrid approach. For instance, I can imagine a rope-like data structure where the nodes are sized to a cache row for example. It might not be optimal from a memory usage standpoint, but there are probably use cases where it could make sense
the5avage 6y ago
Exactly. And you additionally need GC or reference counting. If you write a text editor you certainly should think about something like that, but claiming it should be the default string type is a bit off. You should probably only use data structures with a lot of indirection if you really can measure it to be faster in the situation.
konjin 6y ago
The point isn't reading, the point is writing. Inserting a single character into a string is an O(n) operation. Inserting one in a rope is basically O(log(n)), same for deletion.
chrisseaton 6y ago
> memory is a huge bottleneck ... cache friendliness will often trump something that has fewer instructions Aren't these all arguments in favour of ropes? Ropes are write-only when being constructed. They're not just cache friendly, they're cache oblivious!

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.

jcelerier 6y ago
> 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). in a 2020 machine with a normal workload I have yet to see a list outperform a contiguous array outside of pathological cases > The point of ropes is to handle very long strings. Scanning a long string, many kilobytes or even megabytes long I mean, my 2016 CPU has 20 megabytes of L3 cache, you can fit a fair amount of text in that, likely more than 99.9% of average text editor usage
- konjin 6y ago
  >in a 2020 machine with a normal workload I have yet to see a list outperform a contiguous array outside of pathological cases I guess an size(array)+1 is a pathological case. Shame it seems to happen in every code base I've looked at.
  - jcelerier 6y ago
    the question is, how often does it happen when compared to iterating over your loop ? Like, every codebase I've worked on had some array sorting at some point in it... but the frequency of needing to sort something vs having to loop over all the X makes it a completely not-relevant thing. If the only time you add an element to an array is as a result of the user clicking somewhere, then I'd say it's definitely not worth taking into account if your array isn't 5000000 elements (which it will likely won't be if you are giving the user the ability to just add something to it).
    - konjin 6y ago
      Enough to explode a rocket every decade. Not everyone works on js.
      - jcelerier 6y ago
        I would be very surprised if there is any code that could potentially allocate in the hot (lol) path of a rocket. There'll just be static arrays in there.

skohan 6y ago

Maybe there's a hybrid approach. For instance, I can imagine a rope-like data structure where the nodes are sized to a cache row for example. It might not be optimal from a memory usage standpoint, but there are probably use cases where it could make sense

the5avage 6y ago

Exactly. And you additionally need GC or reference counting. If you write a text editor you certainly should think about something like that, but claiming it should be the default string type is a bit off. You should probably only use data structures with a lot of indirection if you really can measure it to be faster in the situation.

konjin 6y ago

The point isn't reading, the point is writing. Inserting a single character into a string is an O(n) operation. Inserting one in a rope is basically O(log(n)), same for deletion.

chrisseaton 6y ago

> memory is a huge bottleneck ... cache friendliness will often trump something that has fewer instructions Aren't these all arguments in favour of ropes? Ropes are write-only when being constructed. They're not just cache friendly, they're cache oblivious!