Performance: Fastest string reversing algorithms... (final results)

To start I got entries from Darren Neimke, Jerry Pisk, and Ryan Blake.  In most cases thes algorithms were the same as the ones I was going to use for demonstration, however, at the end of the competition, Darren managed to toss in one algorithm that I had overlooked because it is slow on small strings, but it actually started to pull ahead when I made some monstrous strings to test the final algorithms on.

The problem comes in three parts, allocation of a work buffer, reversing algorithm, and reintegration as a string.  That means to start we should examine the various ways that people used in order to allocate a buffer.  I'll even show one, that turns out to be not performant at all, but you'd think it would be.

  1. string.ToCharArray - Note, this function is equivalent to net char[] + an internal memory copy.  Most users have this as the basis of their algorithm and I'll show you why this in turn hurts perf.  In effect you are copying the data twice when you don't need to.
  2. new char[] -This is probably the best buffer you could use.  It has no data in it yet, but strings are immutable and you'll have the original string around the entire time as you do the reversal.
  3. StringBuilder - StringBuilder's actually use a String behind the scenes and have the ability to convert your *work* into an instantly accessible string.  The char[] overloads for string actually have to copy your buffer into place.  This could be a solution for solving a buffer and reintegration?

Those are the three types of buffer used so far.  There could be more, but people didn't send them in.  I'm interested in seeing a few more if anyone has them.  I experimented with memory streams and a few other ideas, but the third part of the problem, getting an actual string, always hurt other attempts.

Alrighty, so how do we reverse the string once we have it?  There are lots of answers to that depending on the buffers we used, so I'll mention them all here.

  1. ToCharArray and Inline - This is an inline swap using the ToCharArray method.  It involves making a swap of two array locations.  This means you are going to have a single helper variable come along for the ride, since you can't make a swap without storing a temporary local.  Because of this temporary local, these algorithms fall short a bit.  Note that as the front approaches the back, i < j, there is a point where i = j.  Most authors actually did a replacement when this occured.  However, if i = j, then you don't need to do a replacement, and you perform in one less operation.  Any odd character in the middle of a string is already reversed ;-)
  2. ToCharArray using Original - This is a modified version that uses the original string.  This actually comes out to be a bit faster, because we get rid of one copy for every 2 characters.  None of the author's found this method, and I can't blame them.  Why in the hell would you use the original string when you have a copy of it ;-)
  3. ToCharArray using Array.Reverse - This is a surprising algorithm.  Because we get back into unmanaged code for the reversal, it actually performs better over very large strings than any of the other algorithms.  We are still making the extra copy, but in this case it doesn't matter at all.  Darren found this one all on his own.  I wouldn't have even tried it, because logically finding that ToCharArray was making an extra copy, I would have assumed it to still be slower (and it still is for strings less than ~100 characters).
  4. char[] using Original - This method uses a character array only.  This method gets by doing the original copy and instead saves all copying for the reversal layer.  In this scenario, you have to iterate until i <= j, because you need to restore that middle character.  This generally results in one extra unneeded replacement per run of the algorithm, but that isn't bad.
  5. StringBuilder using Append - Slow, don't use it.  StringBuilder is riddled with thread checks making it extremely slow.
  6. StringBuilder using initial String - Slow, don't use it.  StringBuilder is riddled with thread checks making it extremely slow.

The surprising part is how poorly StringBuilder actually performs.  Let's stop and think about what we are doing in the other algorithms.  We are making a copy, doing work on the buffer, then effectively making another copy to turn it back into a string.  The turning it back into a string part is actually a big operation and there isn't anything we can do to limit it's overhead.  Now with a StringBuilder we are making a copy that already is a now mutable string.  We can then update our buffer, and finally get a string back without incurring the extra copy.  To bad all of the bogus thread checking in there kills our performance.

Alrighty, I said three parts.  Turning the buffer back into a string is as easy as constructing a new string, or calling ToString in the case of a StringBuilder.  All there is to it, algorithms are complete.  Here they are, refactored into testable C# with the appropriate attributions to each submitter.

Contributor Code
Myself
Jerry Pisk
Ryan Blake
Darren Neimke
We all came up with this one. I've denoted both versions with the faster one being uncommented. Also note that most authors replaced the *odd* character in the middle of a string, which lost them one cycle ;-)
private static string ReverseUsingCharArrayCopy(string input) {
    char[] reversed = input.ToCharArray();
        
    for(int i = 0, j = reversed.Length - 1; i < j; i++, j--) {
        reversed[j] = input[i];
        reversed[i] = input[j];
//            char temp = reversed[i];
//            reversed[i] = reversed[j];
//            reversed[j] = temp;
    }
    return new String(reversed);
}
                
Darren Neimke
This method came as a surprise to me, but it actually performs faster over large strings by about 5% over the fastest algorithm. I'll dig the rotor and find out why.
private static string ReverseUsingCharArrayCopyAndReverse(string input) {
    char[] reversed = input.ToCharArray();
    Array.Reverse(reversed);
    return new String(reversed);
}
                
Me
Darren Neimke
This kicks the pants off of the ToCharArray version because we get rid of the extra copying of data. This was my original posting for fastest algorithm, and it remains so for strings less than ~100-150 characters.
private static string ReverseUsingCharArrayInline(string input) {
    char[] reversed = new char[input.Length];
    for(int i = 0, j = reversed.Length - 1; i <= j; i++, j--) {
        reversed[i] = input[j];
        reversed[j] = input[i];
    }
    return new String(reversed);
}
                
Me
I'm not a Unicode guy, so I'm not sure if my surrogate range checking code is good enough for business. Hell, I'm not really sure it works at all, I just wrote a basic algorithm that knows how to reverse items that might be composed of more than a single data block. If the algorithm I'm using here isn't accurate, then replace the range check with an IsSurrogate check and go back to the slow days ;-)
private static string ReverseUsingCharArrayInlineWithSurrogates(string input) {
    char[] reversed = new char[input.Length];
    for(int i = 0, j = input.Length - 1; i < input.Length; i++, j--) {
        if ( input[j] >= 0xD800 && input[j] <= 0xDFFF ) {
            reversed[i+1] = input[j--];
            reversed[i++] = input[j];
        } else {
            reversed[i] = input[j];
        }
    }
    return new String(reversed);
}
                
Me
One of the StringBuilder attempts. This is the fastest one and that isn't saying much because it is still far too slow for practical usage. Every call to the indexer is invoking some threading gods, as is the call to ToString().
private static string ReverseUsingStringBuilderInline(string input) {
    StringBuilder sb = new StringBuilder(input);
    for(int i = 0, j = input.Length - 1; i <= j; i++, j--) {
        sb[i] = input[j];
        sb[j] = input[i];
    }
    return sb.ToString();
}
                

Alrighty, the above leads to some concepts for tuning our algorithm to be different based on the size of the string.  We don't want to negatively weight our algorithm to only perform well under certain circumstances.  My recommendation would be to find a sutiable cut-off in character length for when the array reversal actually becomes faster.  In addition I propose to find out why the array reversal becomes so quick, after all, we are still copying the data one extra time in the ToCharArray call.  The slowness of the reversal is only apparent at small string lengths, and at these lengths both the original ToCharArray with swapping and the fast char[] allocation are much faster.

// Small strings
00:00:01.1816992 ToCharArray
00:00:01.4721168 ToCharArray /w Reverse
00:00:00.6609504 new char[]
00:00:00.9914256 new char[] with Surrogate Awareness
// Large strings
00:00:09.3334208 ToCharArray
00:00:07.5408432 ToCharArray /w Reverse
00:00:08.2218224 new char[]
00:00:15.1317584 new char[] with Surrogate Awareness

To note, the array reverse can never be surrogate aware, so if we wanted that feature, we couldn't use our super fast over large strings algorithm.  Well, I think this algorithm is cooked guys.  Thanks for participating and enjoy the results.

Published Thursday, June 10, 2004 6:32 PM by Justin Rogers

Comments

Thursday, June 10, 2004 11:24 PM by Wesner Moise

# re: Performance: Fastest string reversing algorithms... (final results)

Actually, for large buffers, I suspect that you will get better performance by using StringBuilder with a capacity equal to the length of the original string.

But instead of using indexing, try appending blocks of characters with StringBuilder.Append using a char array of some fixed size such as 1024 characters. This eliminates the range-checking overheard associated with using Append, because you are appending several characters at once. At StringBuilder reuses the underlying string.

This uses less memory for large strings and potentially improve performance by invoking fewer garbage collections.

Thursday, June 10, 2004 11:46 PM by Justin Rogers

# re: Performance: Fastest string reversing algorithms... (final results)

Suspecting something and testing is a universal binary pair. Let me know when you've tested it, and that the tests you've run have disproven the very poor StringBuilder (10x worse than the comparitive algorithms in all cases I've tested). Drop us the source code and throw your hat into the competition.

Friday, June 11, 2004 12:02 AM by Justin Rogers

# re: Performance: Fastest string reversing algorithms... (final results)

In the interest of putting to rest any argument between myself and Wesner over the viability of the StringBuiler, I purpose the following algorithm. Note the algorithm uses a character array now to reverse a good deal of characters before trying the append.

Even with the speed boost supplied by our real reversing algorithms demonstrated in the article above, the StringBuilder still takes on the order of 1.1 seconds for shorter strings and 18 seconds for longer strings. I'm still inclined to use the character array reversal algorithms if I truly want to handle long strings.

private static string ReverseUsingStringBuilderCopy(string input) {
StringBuilder sb = new StringBuilder(input.Length);
char[] buffer = new char[Math.Min(input.Length, 1024)];
Console.WriteLine(buffer.Length);
int offset = 0;

for(int i = input.Length - 1; i >= 0; i--) {
buffer[offset++] = input[i];

// We could move our final append
// into this loop, but that would invoke
// two compares per iteration
if ( offset == buffer.Length ) {
Console.WriteLine("Append Buffer in Loop");
sb.Append(buffer, 0, offset);
offset = 0;
}
}
if ( offset > 0 ) {
Console.WriteLine("Appending final buffer");
sb.Append(buffer, 0, offset);
}

return sb.ToString();
}
Friday, June 11, 2004 12:30 AM by Justin Rogers

# re: Performance: Fastest string reversing algorithms... (final results)

However, what is a long string?

Strings less than about 150 characters I'll group into class 1. Strings of about 5000 characters or less I'm going to group into class 2. Anything above is class 3.

A string-builder matched with buffered chunking using class 1 strings gets it's butt kicked by our other algorithms. In fact, anything less than our buffer size, and it doesn't even help if we use string builders, since the allocated buffer kills any chance of using *less* memory. On the upper end of class 2 strngs the builder method starts to get better again, though it is still getting it's butt kicked. As we start into our class 3 strings, the string builder can actually match the other algorithms because of memory limits and it's reliance on a small work buffer. I used a string of 1024*50 characters in order to demonstrate a class 3 string. I like the results, and I think the string builder might be an adequate scenario for reversing strings when your input data is larger than your work buffer. I do propose a better construct for doing this operation than what I proposed before. This one adds a single division step to get rid of the comparison check each time through.

private static string ReverseUsingStringBuilderCopy(string input) {
StringBuilder sb = new StringBuilder(input.Length);
char[] buffer = new char[Math.Min(input.Length, 1024)];

int fullBuffers = input.Length / 1024;
int i = input.Length - 1;
int offset = 0;

for(int fullBuffer = 0; fullBuffer < fullBuffers; fullBuffer++) {
for(offset = 0; offset < buffer.Length; offset++) {
buffer[offset] = input[i--];
}
sb.Append(buffer, 0, buffer.Length);
}

for(offset = 0; i >= 0; i--, offset++) {
buffer[offset] = input[i];
}
sb.Append(buffer, 0, offset);

return sb.ToString();
}
Friday, June 11, 2004 3:49 PM by Kevin Dente

# re: Performance: Fastest string reversing algorithms... (final results)

Interesting. However, has anyone ever actually needed to reverse a string in a real application? :P
Friday, June 11, 2004 10:51 PM by Justin Rogers

# re: Performance: Fastest string reversing algorithms... (final results)

String reversal is often used to determine palindromic identity, reformat portions of a string for different UI displays, perform basic cryptographic cyphers, and is a great root of examination to understand basic performance characteristics about a language or platform. The string reversal process in .NET is probably one of the most unique forms of string reversal, compared to other languages that allow in place string manipulation.
Saturday, June 12, 2004 5:08 PM by Austin Ehlers

# Another alternative

How about unsafe code:

unsafe static void ReverseString(string source)
{
int y=source.Length-1;
int mid=source.Length/2;
fixed(char* sfixed=source)
{
char* s=sfixed;
char t;
for(int x=0; x<mid; x++, y--)
{
t=s[x];
s[x]=s[y];
s[y]=t;
} }
}
Results with 1million iterations:
Method 20 200 2000
ReversePointer 0.453125 2.546875 23.171875
ReverseCharArrayCopy 3.71875 12.09375 95.78125
ReverseCharArrayCopyAndReverse 4.59375 11.484375 81.4375
ReverseUsingStringBuilderInline 8.828125 67.546875 658.34375
ReverseUsingStringBuilderCopy 2.875 13.578125 117.015625
Saturday, June 12, 2004 5:21 PM by Justin Rogers

# re: Performance: Fastest string reversing algorithms... (final results)

Well, for one, that breaks just about every single rule of string immutability and can really cause the .NET run-time to heave. You should read up on Brad Abrams blog and check out various comments from Brian Grunkmeyer.

Functionally, what you've posted works. However it breaks the .NET run-time at the lowest levels. Even allocating a new string full of nothing but space, and then copying the reversed string into it is breaking the rules.
Saturday, June 12, 2004 6:23 PM by Austin Ehlers

# re: Performance: Fastest string reversing algorithms... (final results)

Unsafe code is for those who need fast access, and know what their code will do. None of the "special bits" used to designate a string with non-ASCII characters are contained in the range of
fixed(char* c=str)
c[0] to c[str.Length-1]

The length of the string is an Int32 stored just before c[0]. The non-ASCII info is stored in the top-two bits on the int. (0xC0000000)
Saturday, June 12, 2004 6:54 PM by Justin Rogers

# re: Performance: Fastest string reversing algorithms... (final results)

One of the tenets of the first competition was that thread safety was a must. Your method, for obvious reasons is not thread safe because you overwrite the string in place. If, however, you copied your string, then everything would be fine, so I'll take your algorithm and append a string output = string.Copy(input);, and then work over the copied string. That'll prove it to be thread safe.

Another thing to note is that since we are making a proper copy of the string first, and we are not changing the contents of the string, only the ordering, we can hopefully disregard negative side effects of using the NLS bits...

I'll make a posting later with the methods devised, there are faster versions of the algorithm than what you posted when using unsafe code.
Saturday, June 12, 2004 7:34 PM by Austin Ehlers

# re: Performance: Fastest string reversing algorithms... (final results)

Ok, added string.Copy in the for-loop. Also, I actually tested 10million, not 1. Here's the new results:

C:\>f 20 1000000
ReversePointer method: 00:00:00.1250000
ReverseCharArrayCopy method: 00:00:00.3437500
ReverseCharArrayCopyAndReverse method: 00:00:00.4843750
ReverseUsingStringBuilderInline method: 00:00:00.8906250
ReverseUsingStringBuilderCopy method: 00:00:00.3125000

C:\>f 200 1000000
ReversePointer method: 00:00:00.5468750
ReverseCharArrayCopy method: 00:00:01.1562500
ReverseCharArrayCopyAndReverse method: 00:00:01.1875000
ReverseUsingStringBuilderInline method: 00:00:07.0156250
ReverseUsingStringBuilderCopy method: 00:00:01.5000000

C:\>f 2000 1000000
ReversePointer method: 00:00:04.7656250
ReverseCharArrayCopy method: 00:00:09.5000000
ReverseCharArrayCopyAndReverse method: 00:00:08.4843750
ReverseUsingStringBuilderInline method: 00:01:09.4687500
ReverseUsingStringBuilderCopy method: 00:00:12.6875000

I also didn't know this was a contest (I followed the link here from a NG post)
Tuesday, October 21, 2008 1:38 AM by afseki

# re: Performance: Fastest string reversing algorithms... (final results)

return new String(Array.Reverse(myString.ToCharArray()));

Friday, December 5, 2008 7:09 PM by Semil

# re: Performance: Fastest string reversing algorithms... (final results)

<a href= spiritez.com ></a>

Tuesday, June 16, 2009 4:33 PM by Bob

# re: Performance: Fastest string reversing algorithms... (final results)

Why aren't the algorithms checking for a null input?

Tuesday, June 15, 2010 8:58 AM by kikus

# re: Performance: Fastest string reversing algorithms... (final results)

как всегда на высоте

Tuesday, June 15, 2010 9:10 AM by kikus

# re: Performance: Fastest string reversing algorithms... (final results)

отлично написано, у автора прям талант

Monday, March 26, 2012 4:37 PM by hype8912

# re: Performance: Fastest string reversing algorithms... (final results)

VB has a built in function for working with strings already. I somehow remember this from my VB6 coder days. I'm not sure what the performance of it would be against the algorithms posted but it may be worth seeing how MS actual coded it and see if it adds any safety or functionality the posted methods may be missing.

Sunday, March 10, 2013 7:27 PM by Stevens

# re: Performance: Fastest string reversing algorithms... (final results)

Get the full Fat Loss Factor program that reveals information that nobody else reveals.

Fat people can also look attractive, but yes, the slimmer and thinner ones can

win the battle easily. Your body, just having woken up, has

little to no fuel left from the day before.

Sunday, March 10, 2013 8:21 PM by Granger

# re: Performance: Fastest string reversing algorithms... (final results)

Just utilize the anti Cellulite therapy Cream for your thigh, midsection,

tummy, or chin and view the excess fat disappear.

Although cellulite laser treatment is certainly one of the ways to get rid of cellulite, the best way is to

use the best cellulite creams that will get rid of your cellulite and banish good.

It is usually experienced in many women and it is widely recognized as something that can lead to distrust.

Monday, March 11, 2013 5:08 PM by Puckett

# re: Performance: Fastest string reversing algorithms... (final results)

To begin with, the system does not work for all people. In the past 10 years

the Linden Method for Anxiety attacks has proven effective in the treatment

of all panic disorders. Before you try this method, gather first as much information as you need by reading several reviews

about the method.