Reverse a String 4x Faster

Naive string reversal (e.g. http://www8.cs.umu.se/~isak/snippets/strrev.c) is simple and might feel optimal. However, if we treat a string as if it were an 8-byte array, then we can do a reversal with an eighth as many swaps. With this in mind, we’ll do the same reversal algorithm, but this time on 8-byte chunks. This doesn’t completely reverse the list, though. We need to reverse each 8-byte piece about itself. Fortunately, we can reverse the bytes quickly with our friends, >> and |. Finally, we’ll have a small piece left over in the middle that needs to be reversed in smaller chunks.

EDIT: A lot of people have mentioned that this code only works for ASCII strings. However, since UTF-8 and UTF-16 strings are usually reversed by first reversing each byte (or two bytes) and then reversing each unicode sequence (http://stackoverflow.com/questions/199260/how-do-i-reverse-a-utf-8-string-in-place), this algorithm can be used in reversing them as well.

Here’s the code:

void strrev(char *str, int len){
	//temp swap variables
	int i = 0, j = len / 8 - 1, endpoint = len / 16, temp1, temp2;
	unsigned long long int *str_i1 = (unsigned long long int*)str, *str_i2 = str + len % 8; //separate arrays used to deal with alignment 
	while(i < endpoint){
		temp1 = str_i1[i];
		temp2 = str_i2[j];
		//reversing the first
		temp1 = (temp1 << 32) | (temp1 >> 32);
		temp1 = ((temp1 & 0xFFFF0000FFFF0000) >> 16)  |  ((temp1 & 0x0000FFFF0000FFFF) <> 8)   |  ((temp1 & 0x00FF00FF00FF00FF) << 8);
		//reversing the second
		temp2 = (temp2 << 32) | (temp2 >> 32);
		temp2 = ((temp2 & 0xFFFF0000FFFF0000) >> 16)  |  ((temp2 & 0x0000FFFF0000FFFF) <> 8)  |  ((temp2 & 0x00FF00FF00FF00FF) << 8);
		str_i1[i] = temp2;
		str_i2[j] = temp1;
		i++;
		j--;
	}
	//for the middle piece (always less than 16 bytes), we use a naive reversal
	char temp_c;
	i = len / 2 + (len % 16) / 2;
	j = len / 2 + (len % 16) / 2;
	while(i < len / 2){
		temp_c = str[i];
		str[i] = str[j];
		str[j] = temp_c;
		i++;
		j--;
	}
}

This runs about 4 times faster than my naive implementation using the O3 flag with gcc.

The code I used to actually compare things is here: https://gist.github.com/michaeleisel/f4b5212b65fed5bf2004

3 thoughts on “Reverse a String 4x Faster

  1. This is cool, not necessarily novel, and the above commenter is correct, this won’t work for utf-8 encoded glyphs Unicode indexed at > 128

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s