posted on Monday, July 17, 2006 10:20 PM by amachanic

More on string reversal!

Cross-posted from SQLBlog! - http://www.sqlblog.com

In the last installment, I showed a potentially fastest method using Array.Reverse.

After finding and fixing a bug in method #3 posted in my last installment (it is, in fact, quite a bit faster than method #1 when you don't have a big huge bug in the code ) creating a new method, and hearing from Mladenp about a method he came up with, I decided that I should post another round of results.  So, here are the five methods I'm now testing:

        public static string Reverse1(string s)
        {
            StringBuilder sb = new System.Text.StringBuilder(s.Length);
            int i = s.Length;

            while (i-- > 0)
            {
                sb.Append(s[i]);
            }

            return sb.ToString();
        }

        public static string Reverse2(string s)
        {
            char[] rev = s.ToCharArray();
            Array.Reverse(rev);
            return (new string(rev));
        }

        public static string Reverse3(string s)
        {
            char[] charArray = s.ToCharArray();

            int i = charArray.Length;

            StringBuilder sb = new System.Text.StringBuilder(i);           

            while (i-- > 0)
            {
                sb.Append(charArray[i]);
            }

             return sb.ToString();
        }

        public static string Reverse4(string s)
        {
            char[] charArray = s.ToCharArray();

            int i = charArray.Length;
            int j = i-1;

            string[] outStr = new string[i];

            while (i-- > 0)
            {
                outStr[j - i] = charArray[i].ToString();
            }

            return String.Join("", outStr);
        }

        public static string Reverse5(string s)
        {
            char[] charArray = s.ToCharArray();
            int len = s.Length - 1;

            for (int i = 0; i < len; i++, len--)
            {
                charArray[i] ^= charArray[len];
                charArray[len] ^= charArray[i];
                charArray[i] ^= charArray[len];
            }

            return new string(charArray);
        }

Results (10000 iterations, 26-character string):

Reverse1: 106.767 ms
Reverse2: 12.752 ms
Reverse3: 61.902 ms
Reverse4: 87.963 ms
Reverse5: 12.15 ms

Winner, by a very small margin: Mladenp's XOR method!

Anyone else want to weigh in?  Submissions are open!

Comments

# Interesting Finds: July 18, 2006 @ Tuesday, July 18, 2006 10:39 PM

Anonymous

# Comparing XOR with Array.Reverse() @ Wednesday, July 19, 2006 8:50 AM

Perhaps Mladenp should volunteer to rewrite the .NET Array.Reverse routine. It reads something like:

<pre>
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
public static void Reverse(Array array, int index, int length)
{
int num1;
int num2;
//Exception handling
if (!Array.TrySZReverse(array, index, length))
{
num1 = index;
num2 = (index + length) - 1;
object[] objArray1 = array as object[];
if (objArray1 == null)
{
goto Label_00DE;
}
while (num1 < num2)
{
object obj1 = objArray1[num1];
objArray1[num1] = objArray1[num2];
objArray1[num2] = obj1;
num1++;
num2--;
}
}
return;
Label_00DE:
if (num1 >= num2)
{
return;
}
object obj2 = array.GetValue(num1);
array.SetValue(array.GetValue(num2), num1);
array.SetValue(obj2, num2);
num1++;
num2--;
goto Label_00DE;
}
</pre>

Strange Pants

# re: More on string reversal! @ Wednesday, July 19, 2006 5:50 PM

StrangePants:

The same guys who wrote that would probably ask you in an interview how to switch two integers using XOR and then deduct points if you got it wrong :)

amachanic

# re: More on string reversal! @ Thursday, July 20, 2006 5:21 PM

#5 is actually twice as slow as #2 (try giving it a bigger string).

Stop trying to outwit the framework. What people are not seeing is that in the case of a value type this is actually being done by unmanaged code ...

That method (!Array.TrySZReverse(array, index, length) is actually a native call (a special type of native call that is implemented in the CLR (note is marked with the internal call attribute). If you are interested in these functions take a look at ecall.cpp in the SSCLI.

for small amounts of data managed will be slightly faster than the overhead of moving to native code, as the data gets bigger though the native code wins. Try using 1mb strings ;)

Formanaged code though I think you will be hard pressed to be much faster than

public static unsafe string GregsReallyUnsafeReverse(string s) {
fixed (char* start = s) {
char* begin = start;
char* end = start + s.Length;
while (begin < end) {
*begin ^= *start;
*start ^= *begin;
*begin ^= *start;
begin++;
end--;
}
}
return s;
}

I could make this much faster in unmanaged code as I could exchange 32 bits at a time (then use ah al etc registers to reorder the bytes in the 32 bit integer). This would be much faster than doing it byte by byte. It might even be faster to do it 32 bits at a time and use some smart bitwise operations to do that but I don't have time right now to play with the special cases involved (i.e. handling problems with alignment:))

Cheers,

Greg Young

Greg Young

# re: More on string reversal! @ Thursday, July 20, 2006 5:29 PM

Actually


public static unsafe string GregsReallyUnsafeReverse(string s) {
fixed (char* start = s) {
char* begin = start;
char* end = start + s.Length;
char* stop = start + (end - start) / 2;
while (begin < stop) {
*begin ^= *start;
*start ^= *begin;
*begin ^= *start;
begin++;
end--;
}
}
return s;
}

is slightly faster.

Cheers,

Greg

Greg Young

# re: More on string reversal! @ Thursday, July 20, 2006 5:49 PM

and it would have helped if I put up working versions of the code eh? Don't you hate it when you put up non-working code (so embarassing) :)


here is the working version of the code :)

public static unsafe string GregsReallyUnsafeReverse(string s) {
string ret = (string) s.Clone();
fixed (char* start = ret) {
char* begin = start;
char* end = start + s.Length - 1;
char* stop = start + (end - start) / 2;
while (begin < stop) {
*begin ^= *end;
*end ^= *begin;
*begin ^= *end;
begin++;
end--;
}
}
return ret;
}


the benchmarks ...

string is 1..10000 concated total size is about 38k per string.

Test : Reverse1 took 1171315662.35268 ns, average ns = 1171315.66235268
Test : Reverse2 took 147645068.318747 ns, average ns = 147645.068318747
Test : Reverse3 took 1152222168.75683 ns, average ns = 1152222.16875683
Test : Reverse4 took 4251252009.79753 ns, average ns = 4251252.00979753
Test : Reverse5 took 386969000.765223 ns, average ns = 386969.000765223
Test : GregsUnsafe took 128630624.977027 ns, average ns = 128630.624977027

Greg Young

# Performance : String Reverse @ Friday, July 21, 2006 1:04 AM

I can never stay away from a performance challenge. While the others focus on the loop let's focus somewhere else!

Anonymous

# re: More on string reversal! @ Friday, July 21, 2006 1:28 AM

Here is a 25% speed up over my last (includes returning a "good" string to the client as opposed to doing it in place)

public static unsafe string GregsInt32Reverse(string s) {
UInt32 Low;
UInt32 High;

string ret = string.Copy(s);
fixed (char* start = ret) {
UInt32* begin = (UInt32*)start;
UInt32* end = (UInt32*)(start + s.Length - 2);
UInt32* stop = begin + (end - begin) / 2;
while (begin <= stop) {
Low = *begin;
Low = ((Low) << 16)| (Low >> 16);
High = *end;
High = ((High) << 16) | (High >> 16);
*begin = High;
*end = Low;
begin++;
end--;
}
}
return ret;
}

Greg Young

# re: More on string reversal! @ Sunday, July 23, 2006 6:48 PM

WOW!

This has gotten way out of hand :))))

And all i was trying to do is to remind how XOR works for switching 2 values and exampled it with reversing a string. :)

Does anyone accutally HAS to reverse a 1 MB string??
I haven't seen that yet...

Have fun all!

Mladen