LongString: When things become unequal (comparing two long strings) – Part 2

 

Hi All,

In Part 1 of the LongString post I have shown how we can tackle the problem of running out of memory when manipulating long string using a class similar to the LongString. In Part 2 I will discuss a problem which arises from my implementation of LongString class when implementing the IEquatable<LongString> interface. As you may recall, the LongString is an aggregation of regular strings which are less or equal than a given value. The direct result of this definition is that two equal long strings may have a completely different representation (even if the given value is the same). I will discuss editing operations in Part 3 of this series but you may consider the case where for the given value of 3 the long string (“AB”,”CD”) is equal to the long string (“ABC”,”D”) but they have a different internal representation.

Implementing Equality

The first thing I did was to check how the framework string implements the equality method. You can see the code below but essentially since the strings are represented as a continues memory block the code simply goes over all the bytes and bitwise compares them (with a small optimization which I will not discuss).

10. private unsafe static bool EqualsHelper(string strA, string strB)
11.     {
12.       int i = strA.Length;
13.       if (i != strB.Length)
14.       {
15.         return false;
16.       }
17.       char* ptr = &strA.m_firstChar;
18.       char* ptr2 = &strB.m_firstChar;
19.       while (i >= 12)
20.       {
21.         if (*(long*)ptr != *(long*)ptr2 || *(long*)(ptr + (IntPtr)8 / 2) != *(long*)(ptr2 + (IntPtr)8 / 2) || *(long*)(ptr + (IntPtr)16 / 2) != *(long*)(ptr2 + (IntPtr)16 / 2))
22.         {
23.         IL_7D:
24.           while (i > 0 && *(int*)ptr == *(int*)ptr2)
25.           {
26.             ptr += (IntPtr)4 / 2;
27.             ptr2 += (IntPtr)4 / 2;
28.             i -= 2;
29.           }
30.           return i <= 0;
31.         }
32.         ptr += (IntPtr)24 / 2;
33.         ptr2 += (IntPtr)24 / 2;
34.         i -= 12;
35.       }
36.       goto IL_7D;
37.     }

I wanted to implement something similar and therefore my first implementation was like this:

99. public bool EqualsVerySlow(LongString other)
100. {
101.   if (Length != other.Length) return false;
102.   for (int i = 0; i < Length; i++)
103.   {
104.     if (this[i] != other[i])
105.     { return false; }
106.   }
107.   return true;
108. }

But then I discovered that I didn’t implement the indexer yet so I simply use the method from Part 1 which returns the internal indices (within the array of strings and in a string) GetItemIndexForCharIndex which resulted in this simple code:

90. public char this[int index]
91. {
92.   get
93.   {
94.     Tuple<int, int> innerIndex = GetItemIndexForCharIndex(index);
95.     return _items[innerIndex.Item1][innerIndex.Item2];
96.   }
97. }

The main problem here is that the implementation of GetItemIndexForCharIndex calculates the indices by going over the entire array of strings. This is OK for the indexer but it is not very good when used in a loop therefore it is time to implement the enumerator. A simple enumerator which “remembers” the current position and moves forward should be enough for this case.

148. class LongStringEnumerator : IEnumerator<char>
149. {
150.   LongString _innerString;
151.   int _currentIndex;
152.   int _currentCharIndex;
153.  
154.   public LongStringEnumerator(LongString target)
155.   {
156.     _innerString = target;
157.     _currentIndex = 0;
158.     _currentCharIndex = 0;
159.   }
160.  
161.   public char Current
162.   {
163.     get
164.     { return _innerString._items[_currentIndex][_currentCharIndex]; }
165.   }
166.  
167.   public void Dispose(){}
168.  
169.   object System.Collections.IEnumerator.Current
170.   {
171.     get
172.     { return Current; }
173.   }
174.  
175.   public bool MoveNext()
176.   {
177.     _currentCharIndex++;
178.     if (_currentCharIndex >= _innerString._items[_currentIndex].Length)
179.     {
180.       _currentCharIndex = 0;
181.       _currentIndex++;
182.       if (_currentIndex >= _innerString._items.Count)
183.       {
184.         return false;
185.       }
186.     }
187.     return true;
188.   }
189.  
190.   public void Reset()
191.   {
192.     _currentCharIndex = 0;
193.     _currentIndex = 0;
194.   }
195. }

Now I can fix the Equal code to use the enumerator instead of the indexer.

129. public bool Equals(LongString other)
130. {
131.   if (Length != other.Length)
132.     return false;
133.  
134.   LongStringEnumerator enumerator = new LongStringEnumerator(this);
135.   LongStringEnumerator enumerator2 = new LongStringEnumerator(other);
136.  
137.   do
138.   {
139.     if (enumerator.Current != enumerator2.Current)
140.       return false;
141.     enumerator2.MoveNext();
142.   }
143.   while (enumerator.MoveNext());
144.  
145.   return true;
146. }

One question remains… How bad is this solution? I have run some performance tests and it turns out that this equals method is about 30 to 50 times slower than the equals method of a regular string. In absolute terms, this equals method takes up to 20ms when comparing two 1,000,000 char long strings with only one different character (in a random position). The original method is so fast that it cannot be measured in ms .

Conclusion

The main problem with the long string is going to be performance (in terms of time) compared to the regular string. We see that if an algorithm required mainly comparisons then the LongString is not a good choice. Still, remember that the LongString was designed for a very specific scenario in which it should perform better. In the next part I will implement some editing methods.

A small note about concurrency. Just out of curiosity I have implemented the slow method using the TPL:

110. public bool EqualsSlow(LongString other)
111. {
112.   if (Length != other.Length)
113.     return false;
114.  
115.   bool isEqual = true;
116.   Parallel.For(0, Length, (i, loopState) =>
117.   {
118.     if (this[i] != other[i])
119.     {
120.       isEqual = false;
121.       loopState.Break();
122.     }
123.  
124.   });
125.  
126.   return isEqual;
127. }

This was indeed faster in some cases over the very slow implementation but I cannot compete with the concurrency done in the CPU (which will be used to run the original Equals method of string). This implementation may give you some ideas on how to improve the Equals implementation of LongString (e.g. run a forward and a backward enumerators in separate tasks).

Thank you for reading,

Boris

LongString: A long string for the small heap – Part 1

 

Hi All,

Today I am going to write about strings. I think that the most famous feature of the .Net string is its immutability and this property of the string is a source of comfort in many cases but also a source of pain in others. In this post I will describe a scenario where the immutability of a string may cause a serious degradation of performance and suggest a LongString class (with a partial implementation) which may somehow help in this case. To understand the problem in the scenario I am about to describe we have to throw in another .Net player – The large object heap (LOH for short). If you are unsure of how the LOH works you can read this Microsoft article but I will give a brief description of the relevant parts. The LOH is an additional heap used by the CLR to store large objects (and sometimes other object). How large? Currently (.Net 4) the magic number is 85,000 bytes and above. Every object allocated by the CLR which takes more than this number of byes will not be allocated on the regular heap but on the LOH. The problem is that the LOH has two undesirable properties:

1. The objects on the LOH are always Generation 2 (i.e. you need a full GC run to remove them from memory).
2. The memory in the LOH is not compacted because the CLR doesn’t want to copy such large objects around the memory. This may cause fragmentation in the LOH and sometimes to an OutOfMemory exception (even when there is plenty of memory remaining).

Now for the problematic scenario. Consider the case where you have a string which can be edited by the user and an internal mechanism that stores that string. Lets assume that for every change done by the user you must update some other data and display that data to the user immediately. In the general case this will not be a big problem because the strings will be pretty small. For every change you will be able to “edit” the internal string (by replacing it with a new instance) and the old instance will be garbage collected, probably as Generation 0. The problem begins when your string exceeds the magic number or actually half of the magic number since string characters are in Unicode. Then every generation of a new string will create a new instance on the LOH and the old instances will not be removed until full GC is run. If you are not careful enough and the string undergoes several manipulations then each such cycle may cause several objects to be allocated on the LOH and create fragmentation.

At this point some of you would stop me and say “Then use a StringBuilder, it is editable”. This is true, the StringBuilder is indeed a sort of editable version of the string class but internally it represents the data as a character array so the same problem remains (although not as severely as with String since the array will be reallocated much less).

I am going to propose an initial implementation of a LongString class which will be only rarely allocated on the LOH. The idea is simple, the LongString will keep an array of strings, each string is of length equal or less than a given number. It looks something like this:

8. public class LongString
9. {
10.   private int _runSize;
11.   private List<string> _items;
12.   private int _length;
13.  
14.   public LongString(string data, int runSize)
15.   {
16.     _runSize = runSize;
17.     _items = SplitString(data, runSize);
18.     _length = GetTotalLength();
19.   }
20.  
21.   private int GetTotalLength()
22.   {
23.     int count = 0;
24.     foreach (string item in _items)
25.     {
26.       count += item.Length;
27.     }
28.  
29.     return count;
30.   }

Note that for brevity reasons I have omitted all the range/null checks from the code. Those checks are very important and mandatory in any code!

So, what are the pros and what are the cons of this implementation? The main advantage is that with a high enough runSize we can avoid the LOH altogether. The only part of the object that may grow too large is the items list but for run size of 100 we would be able to represent a string 100 times larger than we could with the regular string class without it being allocated on the LOH. I doubt that in any practical use you will have strings which are over 400Mb big (and you can always increase the runSize even more). The main disadvantage is that we don’t use the regular string class which means compatibility issue with any other existing code and some time and space penalties for all the extra calculations we do and data we store for the functionality of the regular string.

I will start by implementing the Substring method.

32. private LongString(List<string> items, int runSize)
33. {
34.   _runSize = runSize;
35.   _items = items;
36.   _length = GetTotalLength();
37. }
38.  
39.  
40. public string Substring(int startIndex, int length)
41. {
42.   Tuple<int, int> innerStratIndex = GetItemIndexForCharIndex(startIndex);
43.   Tuple<int, int> innerEndIndex = GetItemIndexForCharIndex(startIndex + length - 1);
44.  
45.  
46.   if (innerStratIndex.Item1 == innerEndIndex.Item1) //This is the case when the substring is contained within one item
47.   {
48.     return _items[innerStratIndex.Item1].Substring(innerStratIndex.Item2, innerEndIndex.Item2 - innerStratIndex.Item2 + 1);
49.   }
50.  
51.   StringBuilder result = new StringBuilder(); //Can be optimized by calculating the exact length
52.  
53.   result.Append(_items[innerStratIndex.Item1].Substring(innerStratIndex.Item2));
54.  
55.   for (int i = innerStratIndex.Item1 + 1; i < innerEndIndex.Item1; i++)
56.   {
57.     result.Append(_items[i]);
58.   }
59.  
60.   result.Append(_items[innerEndIndex.Item1].Substring(0, innerEndIndex.Item2 + 1));
61.   return result.ToString();
62. }
63.  
64. public LongString LongSubstring(int startIndex, int length)
65. {
66.   Tuple<int, int> innerStratIndex = GetItemIndexForCharIndex(startIndex);
67.   Tuple<int, int> innerEndIndex = GetItemIndexForCharIndex(startIndex + length - 1);
68.  
69.   List<string> result = new List<string>();
70.   if (innerStratIndex.Item1 == innerEndIndex.Item1) //This is the case when the substring is contained within one item
71.   {
72.     result.Add(_items[innerStratIndex.Item1].Substring(innerStratIndex.Item2, innerEndIndex.Item2 - innerStratIndex.Item2 + 1));
73.   }
74.   else
75.   {
76.     result.Add(_items[innerStratIndex.Item1].Substring(innerStratIndex.Item2));
77.  
78.     for (int i = innerStratIndex.Item1 + 1; i < innerEndIndex.Item1; i++)
79.     {
80.       result.Add(_items[i]);
81.     }
82.  
83.     result.Add(_items[innerEndIndex.Item1].Substring(0, innerEndIndex.Item2 + 1));
84.   }
85.   return new LongString(result, _runSize);
86. }
87.  
88.  
89. /// <summary>
90. /// Returns a tuple where the first value is the index of the string that contains startIndex within the _items array
91. /// and the second value is the offset within that item (string)
92. /// </summary>
93. /// <param name="index">The index of the character within the full string</param>
94. /// <returns></returns>
95. private Tuple<int, int> GetItemIndexForCharIndex(int index)
96. {
97.   int indexRemaining = index;
98.   int itemIndex = 0;
99.   while (indexRemaining >= 0)
100.   {
101.     if (_items[itemIndex].Length <= indexRemaining)
102.     {
103.       indexRemaining -= _items[itemIndex].Length;
104.       itemIndex++;
105.       continue;
106.     }
107.     return new Tuple<int, int>(itemIndex, indexRemaining);
108.   }
109.   return null;
110. }

The code is quite simple. I have added a special private constructor that allows me to create a LongString from a list of strings. This allows me to speed up the internal cloning process without going through a regular string again. The substring operation is straight forward, cut away the start and the beginning of the target string from the saved string parts and copy all the parts in the middle as they are.

In the next post I will show more implementations of various methods of the LongString class.

Thank you for reading, Boris.