> 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.
> 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
The exact same things about arrays and linked lists were said in 1995 about 1995 machines. They ring true, if you pin down exactly what you mean by your choice of pathological cases.
Even if we completely eliminate all caching effects, so that every memory access is uniform, regardless of past access history, then arrays are still going to be faster in many cases than linked lists. Obviously, in the random access case: fetching the n-th element. Pointers are metadata; a linked list has metadata for every node, and that requires memory bandwidth to suck through the processor. If every list node has a word of pointer for a word of data, then it means scanning through a million word list means we are loading two million words. If the data is aggregated into an array, then scanning it means we are loading only one million words. That's half the cycles. Likely fewer instructions executed in the loop and so on.
Note that arguments like, "but in year 20XX, such a case now fits into my Ln cache" work toward arguing that caching is less relevant. The more cache you have, the less relevant it is. As a cache gets bigger, more and more situations that previously exhibited "poor locality" now have "good locality" of reference.
Your 2016 machine can cache much more of a given linked list than your 1995 machine; it performs relatively better with linked lists than the 1995 machine, even if we account for basic differences of instruction issue rate (pipelining, branch prediction, etc).
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).
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.
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.