There are some people are trying to get the “fastest” string reverse function. http://sqljunkies.com/WebLog/amachanic/archive/2006/07/17/22253.aspx
http://weblogs.sqlteam.com/mladenp/archive/2006/03/19/9350.aspx
There is some history on this problem at Justin Roger's blog
You know me, I can't stay away from a performance challenge...
Here is my original submission (about what you would expect and it’s a fairly naïve implementation) … Note that using the same string (breaking immutabilty rules and doing it in place) is not acceptable as an optimization :)
|
public static unsafe string GregsUnsafeReverse(string s) {
string ret = string.Copy(s);
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;
} |
|
Listing 1: unsafe code to reverse string |
There are two other unsafe entries over on Justin Roger's blog with similar performance characteristics.
What no one is talking about is that this is a piss poor way of doing it. We are copying 16 bits at a time. I think we can do much better. In this example I will use int32s to do it (although it can be done even faster with int64s (especially on a 64 bit machine)). If I could get it to use a ROTL instead, this should easily beat the copy.
|
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;
} |
|
Listing 2: Reverse using int32s |
As for the difference .. it’s about 25% faster (this is 1000 iterations with an 80k string)
Test : GregsUnsafeReverse took 424749975.105176 ns, average ns = 424749.97510517
Test : GregsInt32Reverse took 329840796.768017 ns, average ns = 329840.796768017
I am sure someone can grab this and squeak out some more performance by using int64s but I am lazy so I will just leave it at “this is how you could make it even faster” J Another thing which would make it faster is if I could just use ROTL instead of shifting + oring but I can’t seem to figure out a way to get the JIT to output that for me
Posted
07-21-2006 1:00 AM
by
Greg