String reversal performance

Question

After being intrigued by this question I tried to copy the algorithm that the user Simon Nickerson suggested as well as the algorithm that the top answer provided from docjar: docjar algorithm.

I tested both out (which hopefully I did not make any performance breaking changes by removing the surrogate pair - dealing parts) and I found docjar algorithm to be almost four times faster than Simon's algorithm. Could anyone point out the significant difference between these two algorithms that has this impact on speed because I don't seem to be able to figure it out myself.
Cheers!

(Update) I did 100 trials using System.nanoTime() and I found docjar to average around 4380 nano seconds and the slower algorithm around 13684 nano seconds.

My modified docjar algorithm (4 times faster):

public static String fastReverse(String original)
{
    char[] comps = original.toCharArray();

    int n = comps.length - 1;

    for(int j = (n - 1) >> 1 ; j >= 0; --j)
    {           
        char temp = comps[j];
        char temp2 = comps[n - j];
        comps[j] = temp2;
        comps[n - j] = temp;
    }

    return new String(comps);
}

Simon's modified Algorithm(slower):

public static String reverse(String original)
{
    char[] comps = original.toCharArray();

    int n = comps.length;

    for(int i = 0; i < n / 2; i++)
    {
        char temp = comps[i];
        comps[i] = comps[n - i - 1];
        comps[n - i - 1] = temp;
    }

    return new String(comps);
}

Before we go any deeper, how exactly are you benchmarking those methods? — NPE, Jan 25 '15 at 14:19
Of course feel free to suggest any more advanced benchmarking methods as I'm an amateur on the subject — Alex Koukoulas, Jan 25 '15 at 14:34
@AlexKoukoulas: I suggest you read through this post first. If your results are still the same then it's worth taking a look. http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — Jeroen Vannevel, Jan 25 '15 at 14:35

Damian Nikodem · Answer 1 · 2015-01-25T14:34:14.873

Apart from benchmarking questions,

An initial reading shows that there is significantly more arithmetic occurring in Simon's algorithm.

In each loop the modified DocJar has:

1 boolean Expression
3 subtraction operations.
2 primitive Declarations
4 array lookups
4 assignments

Simon's algorithm has:

List item
1 Boolean expression
1 Division
1 Addition
1 Primitive Declaration
4 subtraction operations
4 array lookups
3 Assignments.

If you wanted to micro-optimize your version even further you could put the 2 char declarations outside of your for loop. (even though any decent compiler would do this for you, its not guaranteed )

String reversal performance

1 Answers1