About expanding lines in .Net / C # and not only

Let's talk about strings, more precisely about turning them over using .Net / C #. It so happened that in the standard library there is no corresponding function. And as I am told, writing the line reversal function is quite a popular question at job interviews. Let's see how you can effectively flip a string using this platform.

Under the cat a comparative analysis of the performance of different methods of string reversal is given.


')
Khrr-rr ... - said the chainsaw.
Tyuyuyu ... - said the men.
© Old joke.

Well, let's start. All implementations were tested for performance with one line of 256 megabytes (128 × 1024 × 1024 characters) and 1024 × 1024 lines of 256 bytes (128 characters) in size. Before each measurement, garbage collection was forced (which is important with this amount of test data), the measurement was performed 50 times, the last 20 were discarded, the remaining values ​​were averaged. Conditional parrots were selected the number of ticks, issued by the object class Stopwatch.

The test was conducted on two computers: Athlon64 x2 4200+, 2GB Dual-Channel DDR2 RAM and Pentium4 HT 3GHz, 3GB DDR RAM. The main difference between the configurations in this test is the memory-cache ligament speed — the second system is much slower in this respect.

The technical formalities are done, now let's move on to the actual implementation. For greater clarity, unicode surrogate code points are not included here. We will consider approaches in the order of logic and “beautiful” implementation in the context of the surrounding “ecosystem”.

Comparative results of measurements are in the last part of this note. In the general case, the ReverseUnsafeCopy function turned out to be optimal , but if we restrict only the safe code - ReverseArrayManual . If you need a safe code and huge strings - you will have to suffer with ReverseStringBuilder .

Part one: “normal” methods.

1. ReverseStringBuilder

We will follow the recommendations and build a “big” string and take a special tool - the class StringBuilder. The idea is simple to horror: create a builder of the desired size and go along the line in reverse order, adding characters to the new line.

Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }

1. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
2. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
3. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
4. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
5. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
6. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }
7. Copy Source | Copy HTML static string ReverseStringBuilder( string str) { StringBuilder sb = new StringBuilder (str.Length); for ( int i = str.Length; i-- != 0 ; ) sb.Append(str[i]); return sb.ToString(); }

We try, we launch, yes ... Somehow it works slowly, we will dig further.

2. ReverseArrayFramework

Ha! So this builder is furnished with checks to ensure thread safety from all sides, no, we don’t need this. But the string is after all an array of symbols. So give it and turn it around, and convert the result back to a string:

Copy Source | Copy HTML

1. static string ReverseArrayFramework ( string str)
2. {
3. char [] arr = str.ToCharArray ();
4. Array .Reverse (arr);
5. return new String (arr);
6. }

It is quite another thing, it turned out 3.5 times faster. Hmm, maybe even better?

3. ReverseArrayManual

So we think. First, we have the data copied twice: first, from the string to the array, then inside the array. Secondly, Array.Reverse is a library method, so it has input data checks. Moreover, for atomic types, it is explicitly implemented as a native method, and this is an additional switching of the execution context. Let's try to turn the string into an array manually:

Copy Source | Copy HTML

1. static string ReverseArrayManual ( string originalString)
2. {
3. char [] reversedCharArray = new char [originalString.Length];
4. for ( int i = originalString.Length - 1 ; i> - 1 ; i--)
5. reversedCharArray [originalString.Length - i - 1 ] = originalString [i];
6. return new string (reversedCharArray);
7. }

4. ReverseManualHalf

Go ahead. In our case, the actions are symmetrical with respect to the middle of the line, which means you can put two indices in front of you and double the number of iterations:

Copy Source | Copy HTML

1. static string ReverseManualHalf ( string originalString)
2. {
3. char [] reversedCharArray = new char [originalString.Length];
4. int i = 0 ;
5. int j = originalString.Length - 1 ;
6. while (i <= j)
7. {
8. reversedCharArray [i] = originalString [j];
9. reversedCharArray [j] = originalString [i];
10. i ++; j--;
11. }
12. return new string (reversedCharArray);
13. }

Hmm ... Something went wrong, on a system with slow memory, the speed dropped one and a half times. Considering the specifics of configurations and implementations, we can assume that the memory speed and the processor cache are to blame: we used to work with two remote memory areas at the same time, now there are four, respectively, data pickup is performed more often.

LINQ and Reverse method

There is still a relatively beautiful and short way with LINQ, but it does not hold water in terms of performance - it works 3-3.5 times slower than the method based on StringBuilder. The reason is pumping data through IEnumerable and a virtual call for each iteration. For those who wish, the following is the implementation:

Copy Source | Copy HTML

1. static string ReverseStringLinq ( string originalString)
2. {
3. return new string (originalString.Reverse (). ToArray ());
4. }

Memory usage

The problem is not so critical in most cases, but all the “quick” of the considered methods make an intermediate copy of the string as an array of characters. On synthetic tests, this is manifested in the fact that only the first method was able to wrap a 512MB string, the rest fell down due to System.OutOfMemoryException. Also, we should not forget that unnecessary temporary objects increase the frequency of GC, and although it is optimized to the horror, it still eats. In the next part, in addition to speed optimizations, we will also look for a solution to this problem.

Part two: when you want faster and more efficiently, or unsafe code.

Using unsafe code gives us one interesting advantage: the lines that were previously immutable can now be changed, but you need to be extremely careful and change only the copies of the lines - the library minimizes the number of copies of one line, and along with the internment of lines this can lead to sad consequences for applications.

So, by creating a new line of the desired size, we can look at it as an array and fill it with the necessary data. Well, do not forget about the lack of checks on the validity of indices, which also speed up the work of the code. However, due to the specificity of strings in .Net, we cannot simply create a string of the desired length. You can either make a string from a duplicate character (such as a blank) using the String constructor (char, int), or copy the source string using String.Copy (String).

Armed with this knowledge, we write the following two implementations.

5. ReverseUnsafeFill

Make a string of spaces and fill it in reverse order:

Copy Source | Copy HTML

1. static unsafe string ReverseUnsafeFill ( string str)
2. {
3. if (str.Length <= 1 ) return str;
4. String copy = new String ( '' , str.Length);
5. fixed ( char * buf_copy = copy)
6. {
7. fixed ( char * buf = str)
8. {
9. int i = 0 ;
10. int j = str.Length - 1 ;
11. while (i <= j)
12. {
13. buf_copy [i] = buf [j];
14. buf_copy [j] = buf [i];
15. i ++; j--;
16. }
17. }
18. }
19. return copy;
20. }

6. ReverseUnsafeCopy

Copy and flip the line:

Copy Source | Copy HTML

1. static unsafe string ReverseUnsafeCopy ( string str)
2. {
3. if (str.Length <= 1 ) return str;
4. char tmp;
5. String copy = String .Copy (str);
6. fixed ( char * buf = copy)
7. {
8. char * p = buf;
9. char * q = buf + str.Length - 1 ;
10. while (p <q)
11. {
12. tmp = * p;
13. * p = * q;
14. * q = tmp;
15. p ++; q--;
16. }
17. }
18. return copy;
19. }

As the measurements showed, the second version runs noticeably faster on slow memory and slightly slower on fast :) There are several reasons for this: operating with two remote memory areas instead of four and the difference in the speed of copying a memory block and simply filling it in a loop. Those interested can try to make a full pass version of ReverseUnsafeFill (this can reduce the number of data captures from the memory into the cache) and try it out on a slow memory, but I have reason to believe that it will be anyway slower (although I may be mistaken).

7. ReverseUnsafeXorCopy

What's next? It is rumored that the exchange using the XOR operator works faster than copying through the third variable (by the way, it also looks quite nice in the pluses: “a ^ = b ^ = a ^ = b;”, in C #, alas, this line does not work) . Well, let's check in practice.

Copy Source | Copy HTML

1. static unsafe string ReverseUnsafeXorCopy ( string str)
2. {
3. if (str.Length <= 1 ) return str;
4. String copy = String .Copy (str);
5. fixed ( char * buf = copy)
6. {
7. char * p = buf;
8. char * q = buf + str.Length - 1 ;
9. while (p <q)
10. {
11. * p ^ = * q;
12. * q ^ = * p;
13. * p ^ = * q;
14. p ++; q--;
15. }
16. }
17. return copy;
18. }

The result is 1.2-1.5 times slower than the exchange of copies. The trick, which worked for the rapid exchange of values ​​on registers, did not justify itself for variables (which is characteristic, in many C / C ++ compilers, it also does not win).

Looking for explanations of this fact, we will go inside the application and read the resulting CIL code.

Part Three: we climb into CIL and .Net library codes.

Why sharing through XOR was worse

For an answer to this question, it is worth looking at the CIL code generated for the two ways to exchange. To make these instructions seem clearer, let me explain their purpose: ldloc .N - loads a local variable N on the stack, stloc .N - reads the top of the stack into a local variable N , xor - calculates the value of the XOR operation for two values ​​at the top of the stack and loads the result on the stack instead.

Copy Exchange	Exchange based on XOR	Perfect exchange CIL
int a, b; int tmp = a; a = b; b = tmp;	int a, b; a ^ = b; b ^ = a; a ^ = b;
.locals init (<br/> [0] int32 a,<br/> [1] int32 b,<br/> [2] int32 tmp)	.locals init (<br/> [0] int32 a,<br/> [1] int32 b)<br/>	.locals init (<br/> [0] int32 a,<br/> [1] int32 b)<br/>
L_0004: ldloc .0<br/> L_0005: stloc .2<br/> L_0006: ldloc .1<br/> L_0007: stloc .0<br/> L_0008: ldloc .2<br/> L_0009: stloc .1<br/> <br/> <br/> <br/> <br/> <br/>	L_0004: ldloc .0<br/> L_0005: ldloc .1<br/> L_0006: xor <br/> L_0007: stloc .0<br/> L_0008: ldloc .1<br/> L_0009: ldloc .0<br/> L_000a: xor <br/> L_000b: stloc .1<br/> L_000c: ldloc .0<br/> L_000d: ldloc .1<br/> L_000e: xor <br/> L_000f: stloc .0<br/>	L_0004: ldloc .0<br/> L_0005: ldloc .1<br/> L_0006: stloc .0<br/> L_0007: stloc .1<br/> <br/> <br/> <br/> <br/> <br/> <br/> <br/>

As you can easily see, the version with the XOR operator requires more virtual machine operations. Moreover, during subsequent compilation into the native code, it is likely that there is optimization, which will replace the typical exchange via the third variable with a more efficient exchange operation, taking into account the capabilities of the processor used. As a side effect of the analysis, we get a hypothetical “perfect” exchange for CIL, it would be interesting to check whether its use will give any effect, but for this you need to mess with ilasm or reflection / emit, maybe even get together. However, the resulting code will be even less applicable than unsafe c # so there is not much practical interest.

How does Array.Reverse work?

Well, while we are looking at the insides of the assemblies with a reflector, it makes sense to look at the implementation of the library methods used in the first part. Apart here is Array.Reverse, which relies on a certain function Array.TrySZReverse, implemented as a native method. So, download Shared Source Common Language Infrastructure 2.0 - source .net 2.0 and see what kind of animal it is :) After a brief search, in the file “sscli20 \ clr \ src \ vm \ comarrayhelpers.h” there is a template function Reverse (in this the case of KIND will correspond to UINT16), which (surprise!) is terribly like the implementation of ReverseUnsafeCopy.

Copy Source | Copy HTML

1. static void Reverse ( KIND array [], UNIT32 index, UNIT32 count) {
2. LEAF_CONTRACT;
4. _ASSERTE (array! = NULL);
5. if (count == 0) {
6. return ;
7. }
8. UNIT32 i = index;
9. UNIT32 j = index + count - 1 ;
10. while (i <j) {
11. KIND temp = array [i];
12. array [i] = array [j];
13. array [j] = temp;
14. i ++;
15. j--;
16. }
17. }

Part Four: Binary Marathon Results

The analysis of the measurement results is given in the first two parts, here only comparative diagrams depicting the performance ratio of the above functions are shown. The exact numbers in the “ticks” are too dependent on the configuration and it is unlikely to be of particular interest, everyone can independently measure the speed using the provided pieces of code.

Comparison of the best methods from the first two parts

On fast memory

On slow memory

Comparison of all methods in debug and release configurations on fast memory

Large lines

Short strings

Comparison of all methods in debug and release configurations on slow memory

Large lines

Short strings