27

Related to this question, based on a comment of user Eric Lippert.

Is there any scenario where the Rope data structure is more efficient than a string builder? It is some people's opinion that rope data structures are almost never better in terms of speed than the native string or string builder operations in typical cases, so I am curious to see realistic scenarios where indeed ropes are better.

8
  • 12
    My experience is admittedly limited; I've tried to add rope-style string representations to languages like VBScript and JScript. The number of cases in which we must aggressively reify internal strings into "real" buffer-based strings was so large, and the number of cases where runtime string manipulations actually grew large, complex strings was so small, that the net perf impact was negative. When we built the string logic in JScript.NET we simply used a stringbuilder rather than attempting ropes again. Dec 7, 2009 at 22:59
  • Perhaps one area where a rope would perform better would be a scenario where searching would prevail over other operations - so a rope representation of otherwise unstructured text, that needs frequent searching would be adequate, don't you think?
    – luvieere
    Dec 7, 2009 at 23:22
  • luvieere, searching would be slower. Dec 7, 2009 at 23:35
  • Why would it be, considering that substring is faster?
    – luvieere
    Dec 7, 2009 at 23:42
  • Extracting a substring from a given position, and searching a string for a matching substring are completely different operations. Dec 8, 2009 at 1:13

5 Answers 5

28
+100

The documentation for the SGI C++ implementation goes into some detail on the big O behaviours verses the constant factors which is instructive.

Their documentation assumes very long strings being involved, the examples posited for reference talk about 10 MB strings. Very few programs will be written which deal with such things and, for many classes of problems with such requirements reworking them to be stream based rather than requiring the full string to be available where possible will lead to significantly superior results. As such ropes are for non streaming manipulation of multi megabyte character sequences when you are able to appropriately treat the rope as sections (themselves ropes) rather than just a sequence of characters.

Significant Pros:

  • Concatenation/Insertion become nearly constant time operations
  • Certain operations may reuse the previous rope sections to allow sharing in memory.
    • Note that .Net strings, unlike java strings do not share the character buffer on substrings - a choice with pros and cons in terms of memory footprint. Ropes tend to avoid this sort of issue.
  • Ropes allow deferred loading of substrings until required
    • Note that this is hard to get right, very easy to render pointless due to excessive eagerness of access and requires consuming code to treat it as a rope, not as a sequence of characters.

Significant Cons:

  • Random read access becomes O(log n)
  • The constant factors on sequential read access seem to be between 5 and 10
  • efficient use of the API requires treating it as a rope, not just dropping in a rope as a backing implementation on the 'normal' string api.

This leads to a few 'obvious' uses (the first mentioned explicitly by SGI).

  • Edit buffers on large files allowing easy undo/redo
    • Note that, at some point you may need to write the changes to disk, involving streaming through the entire string, so this is only useful if most edits will primarily reside in memory rather than requiring frequent persistence (say through an autosave function)
  • Manipulation of DNA segments where significant manipulation occurs, but very little output actually happens
  • Multi threaded Algorithms which mutate local subsections of string. In theory such cases can be parcelled off to separate threads and cores without needing to take local copies of the subsections and then recombine them, saving considerable memory as well as avoiding a costly serial combining operation at the end.

There are cases where domain specific behaviour in the string can be coupled with relatively simple augmentations to the Rope implementation to allow:

  • Read only strings with significant numbers of common substrings are amenable to simple interning for significant memory savings.
  • Strings with sparse structures, or significant local repetition are amenable to run length encoding while still allowing reasonable levels of random access.
  • Where the sub string boundaries are themselves 'nodes' where information may be stored, though such structures are quite possible better done as a Radix Trie if they are rarely modified but often read.

As you can see from the examples listed, all fall well into the 'niche' category. Further, several may well have superior alternatives if you are willing/able to rewrite the algorithm as a stream processing operation instead.

3
  • What would you think of the idea of a using an array of arrays to store strings, where each intermediate array would generally have a length within a certain range (perhaps 256-1023 characters)? That would eliminate much of the lg(N) overhead of ropes, but still reduce by a factor of 30-60 the cost of copying large parts of a string [string concatenation would often require creating a new character-sequence object to hold the concatenation of the last segment of one string and the first segment of the other, but for large strings that would still be cheaper than copying everything.
    – supercat
    Sep 11, 2015 at 20:15
  • @supercat: if the segments are of variable length you get O(N) indexing, if they are of the same length, you get a C++ std::deque which is a an O(N) concatenation. Jan 7, 2016 at 21:38
  • 1
    @ybungalobill: If the data structure holds the starting offset for each segment, a single random indexing operation would be o(lgN). Concatenation would require rebuilding the master structure, which would be O(N), but with a much smaller constant than with linear string. Finding an index near a recently-found one would be O(lg(d)) where d is the distance between the recently-found one and the desired one.
    – supercat
    Jan 9, 2016 at 17:38
12

the short answer to this question is yes, and that requires little explanation. Of course there's situations where the Rope data structure is more efficient than a string builder. they work differently, so they are more suited for different purposes.

(From a C# perspective)

The rope data structure as a binary tree is better in certain situations. When you're looking at extremely large string values (think 100+ MB of xml coming in from SQL), the rope data structure could keep the entire process off the large object heap, where the string object hits it when it passes 85000 bytes.

If you're looking at strings of 5-1000 characters, it probably doesn't improve the performance enough to be worth it. this is another case of a data structure that is designed for the 5% of people that have an extreme situation.

12

The 10th ICFP Programming Contest relied, basically, on people using the rope data structure for efficient solving. That was the big trick to get a VM that ran in reasonable time.

Rope is excellent if there are lots of prefixing (apparently the word "prepending" is made up by IT folks and isn't a proper word!) and potentially better for insertions; StringBuilders use continuous memory, so only work efficiently for appending.

Therefore, StringBuilder is great for building strings by appending fragments - a very normal use-case. As developers need to do this a lot, StringBuilders are a very mainstream technology.

Ropes are great for edit buffers, e.g. the data-structure behind, say, an enterprise-strength TextArea. So (a relaxation of Ropes, e.g. a linked list of lines rather than a binary tree) is very common in the UI controls world, but that's not often exposed to the developers and users of those controls.

You need really really big amounts of data and churn to make the rope pay-off - processors are very good at stream operations, and if you have the RAM then simply realloc for prefixing does work acceptably for normal use-cases. That competition mentioned at the top was the only time I've seen it needed.

1
  • 9
    When I was doing that competition, I didn't know about rope - so I invented my own solution: as string builders are great for appending, and as the problem was prefixing, I simply stored my string .. backwards. Elegant somehow :)
    – Will
    Dec 11, 2009 at 6:32
2

Most advanced text editors represent the text body as a "kind of rope" (though in implementation, leaves aren't usually individual characters, but text runs), mainly to improve the the frequent inserts and deletes on large texts.

Generally, StringBuilder is optimized for appending and tries to minimize the total number of reallocations without overallocating to much. The typical guarantee is (log2 N allocations, and less than 2.5x the memory). Normally the string is built once and may then be used for quite a while without being modified.

Rope is optimized for frequent inserts and removals, and tries to minimize amount of data copied (by a larger number of allocations). In a linear buffer implementation, each insert and delete becomes O(N), and you usually have to represent single character inserts.

1

Javascript VMs often use ropes for strings.

Maxime Chevalier-Boisvert, developer of the Higgs Javascript VM, says:

In JavaScript, you can use arrays of strings and eventually Array.prototype.join to make string concatenation reasonably fast, O(n), but the "natural" way JS programmers tend to build strings is to just append using the += operator to incrementally build them. JS strings are immutable, so if this isn't optimized internally, incremental appending is O(n2 ). I think it's probable that ropes were implemented in JS engines specifically because of the SunSpider benchmarks which do string appending. JS engine implementers used ropes to gain an edge over others by making something that was previously slow faster. If it wasn't for those benchmarks, I think that cries from the community about string appending performing poorly may have been met with "use Array.prototype.join, dummy!".

Also.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.