Rope

What is this?

A highly efficient and performant immutable list data structure with value-like semantics.

Why use this?

• Get the benefits of functional programming, without the overhead of making copies on edit.
• Replace some or all of the following types (see [Comparison with .NET Built in Types]):
  • string
  • T[]
  • List<T>
  • ImmutableList<T>
  • StringBuilder
• Fewer memory allocations and faster edit and search performance (see [Performance]).

How does it work?

This is a C# implementation of a Rope<T> data structure. See the paper Ropes: an Alternative to Strings: h.-j. boehm, r. atkinson and m. plass

A Rope is an immutable sequence built using a b-tree style data structure that is useful for efficiently applying and storing edits, most commonly used with strings, but any list or sequence can be efficiently edited using the Rope data structure.

Where a b-tree is generally used with every node in the tree storing a single element, a rope contains arrays of elements and only subdivides on the edits. This makes it more CPU-cache coherant when performing operations such as searching / memory comparisons.

The data structure then decides at edit time whether it is optimal to rebalance the tree using the following heuristic: A rope of depth n is considered balanced if its length is at least Fn+2.

Note: This implementation of Rope<T> has a hard-coded upper-bound depth of 46 added to the heuristic from the paper. As this seemed to be optimal for my workloads, your mileage may vary.

How do I use it?

dotnet add package FlatlinerDOA.Rope

using Rope;

// Converting to a Rope<char> doesn't allocate any strings (simply points to the original memory).
Rope<char> myRope1 = "My favourite text".ToRope();

// In fact strings are implicitly convertible to Rope<char>, this makes Rope<char> a drop in replacement for `string` in most cases;
Rope<char> myRope2 = "My favourite text";

// With Rope<T>, splits don't allocate any new strings either.
IEnumerable<Rope<char>> words = myRope2.Split(' ');

// Calling ToString() allocates a new string at the time of conversion.
Console.WriteLine(words.First().ToString());

// Warning: Assigning a Rope<char> to a string requires calling .ToString() and hence copying memory.
string text2 = (myRope2 + " My second favourite text").ToString();

// Better: Assigning to another rope makes a new rope out of the other two ropes, no string allocations or copies.
Rope<char> text3 = myRope2 + " My second favourite text";

// Value-like equivalence, no need for SequenceEqual!.
Assert.IsTrue("test".ToRope() == ("te".ToRope() + "st".ToRope()));
Assert.IsTrue("test".ToRope().GetHashCode() == ("te".ToRope() + "st".ToRope()).GetHashCode());

// Store a rope of anything, just like List<T>! 
// This makes an immutable and thread safe list of people.
Rope<Person> ropeOfPeople = [new Person("Frank", "Stevens"), new Person("Jane", "Seymour")];

In built support for Diffing and Patching

Compare two strings (Rope<char>).

Rope<char> sourceText = "abcdef";
Rope<char> targetText = "abefg";

// Create a list of differences.
Rope<Diff<char>> diffs = sourceText.Diff(targetText);

// Recover either side from the list of differences.
Rope<char> recoveredSourceText = diffs.ToSource();
Rope<char> recoveredTargetText = diffs.ToTarget();

// Create a Patch string (like Git's patch text)
Rope<Patch<char>> patches = diffs.ToPatches(); // A list of patches
Rope<char> patchText = patches.ToPatchString(); // A single string of patch text.
Console.WriteLine(patchText);
/** Outputs:
@@ -1,6 +1,5 @@
    ab
-cd
    ef
+g
*/

// Parse out the list of patches from the patch text.
Rope<Patch<char>> parsedPatches = Patches.Parse(patchText);

Create diffs of any type (Rope<T>).

// Compare two lists of people
public record class Person(string FirstName, string LastName);

Rope<Person> original =
[
    new Person("Stephen", "King"),
    new Person("Jane", "Austen"),
    new Person("Mary", "Shelley"),
    new Person("JRR", "Tokien"),
    new Person("James", "Joyce"),
];

Rope<Person> updated =
[
    new Person("Stephen", "King"),
    new Person("Jane", "Austen"),
    new Person("JRR", "Tokien"),
    new Person("Frank", "Miller"),
    new Person("George", "Orwell"),
    new Person("James", "Joyce"),
];

Rope<Diff<Person>> changes = original.Diff(updated, DiffOptions<Person>.Default);
Assert.AreEqual(2, changes.Count(d => d.Operation != Operation.Equal));

// Convert to a Delta string
Rope<char> delta = changes.ToDelta(p => p.ToString());

// Rebuild the diff from the original list and a delta.
Rope<Diff<Person>> fromDelta = Delta.Parse(delta, original, Person.Parse);

// Get back the original list
Assert.AreEqual(fromDelta.ToSource(), original);

// Get back the updated list.
Assert.AreEqual(fromDelta.ToTarget(), updated);

// Make a patch text
Rope<Patch<Person>> patches = fromDelta.ToPatches();

// Convert patches to text
Rope<char> patchText = patches.ToPatchString(p => p.ToString());

// Parse the patches back again
Rope<Patch<Person>> parsedPatches = Patches.Parse(patchText, Person.Parse);
Assert.AreEqual(parsedPatches, patches);

Comparison with .NET Built in Types

A comparison could be drawn between a Rope and a StringBuilder as they use a very similar technique for efficient edits. List{T} is included as a commonly used alternative.

|Feature|Rope<T>|StringBuilder|List{T}|ReadOnlyMemory{T}|ImmutableList{T}|ImmutableArray{T}| |-------|-------------|-------------|-------|-----------------|----------------|-----------------| |Supports items of any type|✅|❌|✅|✅|✅|✅| |Immutable edits|✅|❌|❌|❌|✅|✅|✅| |Thread safe|✅^1.|❌|❌|✅^1.|✅|✅|✅| |Copy free Append (avoid double allocations)|✅|✅|❌|❌|❌|❌| |Copy free Insert|✅|✅|❌|❌|❌|❌| |Copy free Remove|✅|❌|❌|❌|❌|❌| |Copy free split|✅|❌|❌|❌|❌|❌| |GC Friendly (No LOH, stays in Gen 0)|✅|❌|❌|✅|❌|✅| |Create()|O(1)|O(N)|O(N)|O(1)|O(N)|O(N)| |this[]|O(log N)|O(log N)|O(1)|O(1)|O(log N)|O(1)| |Add|O(1) ^2.|O(log N)|O(1) ^3.|O(N) ^4.|O(log N)|O(N) ^4.| |Value-like Equality ^5.|✅|❌|❌|❌|❌|❌| |More than 2 billion elements (long index)|✅|❌|❌|❌|❌|❌|

• ^1. Thread safe as long as initial Array is not modified.
• ^2. Average is case O(1) (amortized). Worst case is O(log N) when a rebalance is required.
• ^3. Average is case O(1) (amortized). Worst case is O(N) when capacity increase is required.
• ^4. Copying to a new instance is required.
• ^5. Structural and reference invariant GetHashCode and Equals comparison.

Performance

Performance - AddRange

Working with a string of length - 32644 characters. - MaxLeafLength = ~32kb, Max Depth = 46

| Method | EditCount | Mean | Error | StdDev | Gen0 | Gen1 | Gen2 | Allocated | |-------------- |---------- |----------------:|--------------:|----------------:|----------:|----------:|----------:|-----------:| | Rope | 10 | 322.6 ns | 1.56 ns | 1.30 ns | 0.0496 | - | - | 832 B | | StringBuilder | 10 | 20,424.1 ns | 46.48 ns | 41.20 ns | 43.1213 | 35.2478 | - | 723272 B | | List | 10 | 1,170,757.8 ns | 23,156.59 ns | 21,660.69 ns | 498.0469 | 498.0469 | 498.0469 | 2098128 B | | Rope | 100 | 22,060.6 ns | 137.07 ns | 128.22 ns | 2.3499 | 0.0610 | - | 39584 B | | StringBuilder | 100 | 293,721.1 ns | 2,960.33 ns | 2,769.09 ns | 395.9961 | 383.7891 | - | 6640952 B | | List | 100 | 9,110,871.4 ns | 179,104.14 ns | 219,955.97 ns | 734.3750 | 734.3750 | 734.3750 | 16781223 B | | Rope | 500 | 415,645.5 ns | 1,144.69 ns | 893.70 ns | 41.9922 | 6.8359 | - | 702864 B | | StringBuilder | 500 | 2,561,640.0 ns | 24,520.41 ns | 22,936.41 ns | 2687.5000 | 2671.8750 | 949.2188 | 32947836 B | | List | 500 | 42,869,839.1 ns | 831,131.28 ns | 1,051,114.95 ns | 2916.6667 | 2916.6667 | 2916.6667 | 67126461 B |

Performance - AddRange (Immutable Collections)

| Method | EditCount | Mean | Error | StdDev | Gen0 | Gen1 | Gen2 | Allocated | |----------------------- |---------- |-----------------:|----------------:|----------------:|-----------:|-----------:|-----------:|------------:| | Rope | 10 | 356.9 ns | 6.63 ns | 6.20 ns | 0.0496 | - | - | 832 B | | ImmutableList .Builder | 10 | 7,700,966.8 ns | 152,284.06 ns | 232,553.85 ns | 992.1875 | 976.5625 | - | 16633835 B | | ImmutableList | 10