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

JIT/Compiler Optimization of Fibonacci calculation

[intermediate-high level]
Hi All,


Today I want to consider the following case:
In my application I want to use some Fibonacci numbers (this is just a hypothetical example :)). I want to see if I can make the JIT/C++ Compiler to put the actual number instead of calling the calculation method. I made two implementations of the calculation but I will show only one, recursive and horribly slow implementation (don't ever use it or even consider of using it!):

    static int FibonacciRecursive(int level)
    {
      if (level == 0)
        return 0;
      if (level == 1)
        return 1;
      return FibonacciRecursive(level - 1) + FibonacciRecursive(level - 2);
    }

And my code for the tests is:

    static void Main(string[] args)
    {
      Console.ReadLine();
      int result = FibonacciRecursive(45);
      Console.Out.WriteLine(result);
    }
I added the ReadLine so that I will have time to attach a debugger when I run the code. The 45th Fibonacci number, if you were wondering, is 1134903170 and not long after that it overflows int :).
I will save you the reading time and not try my code in debug mode. I will first run my code from Visual Studio by pressing "Run" and here is the result (I added comments in case your assembly is a little rusty):

;      int result = FibonacciRecursive(45);
00000022  mov         ecx,2Dh ;put 45 in the ecx register (this is how methods in .net expect their first argument)
00000027  call        dword ptr ds:[006C1F34h] ;call the FibonacciRecursive method 
0000002d  mov         dword ptr [ebp-0Ch],eax ;get the return value from eax register and put it in the "result" variable
00000030  mov         eax,dword ptr [ebp-0Ch] 
00000033  mov         dword ptr [ebp-8],eax 

As you can see there was no optimization in this case, in fact we can see the two lines 
0000002d  mov         dword ptr [ebp-0Ch],eax 
00000030  mov         eax,dword ptr [ebp-0Ch] 
Which copy the return value of the function (stored in eax) to the result variable and then copy it back to eax.

Now I will run the same code but attach the debugger at a later stage (after JIT generated the code) here is the result (again I added some comments):
00000013  mov         ecx,2Ch ;put 44 in ecx register
00000018  call        dword ptr ds:[001A37F8h] ;call the FibonacciRecursive method
0000001e  mov         esi,eax ;put the result in esi register
00000020  mov         ecx,2Bh ;put 43 in the ecx register
00000025  call        dword ptr ds:[001A37F8h] ;call the FibonacciRecursive method
0000002b  add         eax,esi ;add the results of the two calls into eax register

As you can see the code is much more optimized. Which means JIT generates different code if it sees a debugger attached so even when you compile in Release with optimization and run in VS you don't see the most optimized code. 
You can also see that the JIT compiler unwinded the recursion and put its code inline but again the JIT compiler called the method and did not generate the result directly as I wanted. If you are beginning to doubt this is at all possible, keep reading.

Now I will change the call to 
int result = FibonacciRecursive(1);
 and run it without VS. Here is the result:
00000019  mov         edx,1 
Just as we wanted! Instead of calling the method it simply put 1 as the result.
Lets try running it with 
int result = FibonacciRecursive(2);
The result is quite interesting:
00000013  mov         ecx,1 ;put 1 in the ecx register
00000018  call        dword ptr ds:[001937F8h] ;call FibonacciRecursive
0000001e  mov         esi,eax ;put the result in esi register
00000020  mov         ecx,0 ;put 0 in the ecx register
00000025  call        dword ptr ds:[001937F8h] ;call FibonacciRecursive
0000002b  add         eax,esi ;add the results of the two calls
This is really nice. Now we have two calls which are non recursive. This makes me wonder why it didn't run the same logic as it did in the previous run and replaced the method calls with the actual values. My guess would be to speed up the compilation time as it is done in runtime.

These are all my tries in .NET and as you can see I failed to achieve my goal. One could say that this is not possible but I want to look at a little C++ trick which can achieve just what I want. This trick is taken from a programming paradigm known as Generic Programming. This is the C++ code:

#include <iostream>

template <int N>
struct Fibonacci
{
  static const long result = Fibonacci<N-1>::result+Fibonacci<N-2>::result;
};

template <>
struct Fibonacci<0>
{
  static const long result = 0;
};

template <>
struct Fibonacci<1>
{
  static const long result = 1;
};


int main()
{
  std::cout << Fibonacci<45>::result;
  return 0;  
}

and when run, it compiles into this:

01001000  mov         ecx,dword ptr [__imp_std::cout (1002048h)] 
01001006  push        43A53F82h  ; 1134903170 decimal == 43A53F82 hexadecimal
0100100B  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (1002044h)]  

This is exactly what I wanted. The compiler simply pushes the 45th Fibonacci element onto the stack and calls cout. (In C++ arguments are passed using stdcall convention where all the arguments are pushed to the stack.)

That's it for this week.
Thank you for reading.

Boris.