Home

Awesome

Rope

logo

Build Status License

NuGet downloads Size

What is this?

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

Why use this?

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.

FeatureRope<T>StringBuilderList{T}ReadOnlyMemory{T}ImmutableList{T}ImmutableArray{T}
Supports items of any type
Immutable edits
Thread safe<sup>1.</sup><sup>1.</sup>
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)
AddO(1) <sup>2.</sup>O(log N)O(1) <sup>3.</sup>O(N) <sup>4.</sup>O(log N)O(N) <sup>4.</sup>
Value-like Equality <sup>5.</sup>
More than 2 billion elements (long index)

Performance

Performance - AddRange

AddRange

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

MethodEditCountMeanErrorStdDevGen0Gen1Gen2Allocated
Rope10322.6 ns1.56 ns1.30 ns0.0496--832 B
StringBuilder1020,424.1 ns46.48 ns41.20 ns43.121335.2478-723272 B
List101,170,757.8 ns23,156.59 ns21,660.69 ns498.0469498.0469498.04692098128 B
Rope10022,060.6 ns137.07 ns128.22 ns2.34990.0610-39584 B
StringBuilder100293,721.1 ns2,960.33 ns2,769.09 ns395.9961383.7891-6640952 B
List1009,110,871.4 ns179,104.14 ns219,955.97 ns734.3750734.3750734.375016781223 B
Rope500415,645.5 ns1,144.69 ns893.70 ns41.99226.8359-702864 B
StringBuilder5002,561,640.0 ns24,520.41 ns22,936.41 ns2687.50002671.8750949.218832947836 B
List50042,869,839.1 ns831,131.28 ns1,051,114.95 ns2916.66672916.66672916.666767126461 B

Performance - AddRange (Immutable Collections)

AddRangeImmutable

MethodEditCountMeanErrorStdDevGen0Gen1Gen2Allocated
Rope10356.9 ns6.63 ns6.20 ns0.0496--832 B
ImmutableList
.Builder107,700,966.8 ns152,284.06 ns232,553.85 ns992.1875976.5625-16633835 B
ImmutableList107,328,406.3 ns144,002.40 ns134,699.94 ns992.1875976.5625-16635411 B
ImmutableArray10457,004.7 ns8,949.78 ns14,452.23 ns996.0938996.0938996.09384335446 B
Rope10022,539.8 ns126.04 ns117.90 ns2.34990.0610-39584 B
ImmutableList
.Builder100214,688,974.5 ns4,289,220.24 ns8,365,794.66 ns11000.000010500.00002000.0000152739984 B
ImmutableList100206,931,377.8 ns4,000,014.25 ns3,741,615.81 ns11000.000010666.66672000.0000152768739 B
ImmutableArray100102,947,759.8 ns2,231,458.55 ns6,544,481.64 ns24400.000024400.000024400.0000338327974 B

Performance - InsertRange

InsertRange

MethodEditCountMeanErrorStdDevMedianGen0Gen1Gen2Allocated
RopeOfChar101.400 μs0.0120 μs0.0094 μs1.402 μs0.1774--2.92 KB
ListOfChar10741.599 μs2.4556 μs2.0506 μs741.928 μs499.0234499.0234499.02342052.84 KB
StringBuilder1018.175 μs0.1077 μs0.0955 μs18.165 μs43.121331.3416-706.32 KB
RopeOfChar10035.324 μs0.4283 μs0.3796 μs35.221 μs3.84520.0610-63.3 KB
ListOfChar10010,949.444 μs217.4859 μs444.2661 μs10,756.000 μs734.3750734.3750734.375016420.48 KB
StringBuilder100315.408 μs4.5317 μs4.2390 μs314.411 μs395.9961379.8828-6485.3 KB
RopeOfChar10001,900.043 μs6.0456 μs5.0484 μs1,898.135 μs183.593872.2656-3022.17 KB
ListOfChar10001,433,052.443 μs5,397.8058 μs4,785.0142 μs1,432,979.650 μs3000.00003000.00003000.0000131361.66 KB
StringBuilder100024,700.136 μs905.6912 μs2,670.4509 μs25,727.847 μs5406.25005375.00001625.000064277.44 KB

Performance - Split then Concat

Split then Concat

MethodEditCountMeanErrorStdDevGen0Gen1Gen2Allocated
RopeOfChar10573.1 ns4.15 ns3.88 ns0.0515--864 B
StringBuilder1017,382.5 ns347.14 ns439.02 ns23.529111.7493-394912 B
ListOfChar10521,531.2 ns3,077.00 ns2,727.68 ns41.015641.015641.0156262894 B
RopeOfChar1005,517.7 ns18.94 ns14.79 ns0.4807--8064 B
StringBuilder100153,816.0 ns2,649.38 ns2,212.35 ns199.951270.5566-3357352 B
ListOfChar1004,481,838.8 ns38,092.78 ns33,768.26 ns39.062539.062539.0625265776 B
RopeOfChar100056,027.3 ns322.81 ns286.16 ns4.7607--80064 B
StringBuilder10001,519,246.3 ns30,125.60 ns41,236.26 ns1968.7500498.0469123.046932981794 B
ListOfChar100044,472,061.7 ns370,549.50 ns346,612.23 ns---294593 B

Performance - Equals

Equals

MethodLengthMeanErrorStdDevAllocated
Rope<char>104.640 ns0.0256 ns0.0239 ns-
StringBuilder105.057 ns0.0254 ns0.0237 ns-
string102.124 ns0.0047 ns0.0039 ns-
Rope<char>1004.628 ns0.0272 ns0.0255 ns-
StringBuilder1006.404 ns0.0120 ns0.0112 ns-
string1004.102 ns0.0201 ns0.0188 ns-
Rope<char>10004.611 ns0.0253 ns0.0236 ns-
StringBuilder100027.342 ns0.1317 ns0.1232 ns-
string100028.369 ns0.1189 ns0.1112 ns-
Rope<char>100004.646 ns0.0172 ns0.0161 ns-
StringBuilder10000274.231 ns1.8964 ns1.7739 ns-
string10000276.374 ns1.0101 ns0.8434 ns-

Performance - IndexOf

IndexOf

MethodLengthMeanErrorStdDevMedianGen0Allocated
Rope1018.62 ns0.059 ns0.055 ns18.62 ns0.001932 B
Rope10024.91 ns0.080 ns0.075 ns24.89 ns0.001932 B
Rope100055.89 ns0.101 ns0.089 ns55.89 ns0.001932 B
Rope1000083.87 ns0.109 ns0.091 ns83.88 ns0.001932 B
IndexOf1061.17 ns0.285 ns0.253 ns61.12 ns0.001932 B
'IndexOf (Fragmented Find)'1062.37 ns1.252 ns1.391 ns63.50 ns0.001932 B
IndexOf10063.37 ns0.256 ns0.227 ns63.28 ns0.001932 B
'IndexOf (Fragmented Find)'10059.36 ns0.144 ns0.135 ns59.33 ns0.001932 B
IndexOf1000588.18 ns1.596 ns1.493 ns588.58 ns0.0191320 B
'IndexOf (Fragmented Find)'1000103.18 ns0.439 ns0.411 ns103.14 ns0.0114192 B
IndexOf100001,158.36 ns2.464 ns2.305 ns1,157.89 ns0.06291056 B
'IndexOf (Fragmented Find)'100002,245.40 ns28.287 ns26.460 ns2,234.64 ns0.07631328 B
String1017.85 ns0.285 ns0.253 ns17.77 ns0.002948 B
String1003,933.89 ns62.442 ns55.353 ns3,922.67 ns0.0076224 B
String100023,674.90 ns205.594 ns192.313 ns23,758.94 ns0.09162024 B
String1000036,379.40 ns435.649 ns407.506 ns36,422.10 ns1.159720024 B

Performance - Create New

Create New Empty

MethodMeanErrorStdDevMedianGen0Allocated
Rope<char>.Empty0.0003 ns0.0006 ns0.0005 ns0.0000 ns--
'new List<char>()'2.2120 ns0.0305 ns0.0255 ns2.2146 ns0.001932 B
'new StringBuilder()'6.5696 ns0.1487 ns0.1712 ns6.6044 ns0.0062104 B

Create New With Length 10

MethodMeanErrorStdDevGen0Allocated
string.ToRope()5.815 ns0.1009 ns0.0943 ns0.001932 B
'new Rope<char>(array)'5.430 ns0.0174 ns0.0154 ns0.001932 B
'new List<char>(array)'16.955 ns0.1281 ns0.1135 ns0.004880 B
'new StringBuilder(string)'8.575 ns0.0361 ns0.0338 ns0.0062104 B

License and Acknowledgements