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