6
\$\begingroup\$

I am implementing merge sort in Java and I have a performance problem in this method:

    private static void marge(int[] source, int[] buffer, int startingIndex, int count) {
        int index1 = startingIndex;
        int index2 = startingIndex + count / 2;
        int maxIndex1 = index2;
        int maxIndex2 = startingIndex + count;

        for(int i = 0; i < count; i++){
            if(index2 >= maxIndex2 || (index1 < maxIndex1 && source[index1] < source[index2])){
                buffer[startingIndex + i] = source[index1];
                index1++;
            }
            else{
                buffer[startingIndex + i] = source[index2];
                index2++;
            }
        }

//      System.arraycopy(source, startingIndex, buffer, startingIndex, count);
    }

If I replace this method content with the content of the comment, like this:

private static void marge(int[] source, int[] buffer, int startingIndex, int count) {
    System.arraycopy(source, startingIndex, buffer, startingIndex, count);
}

It performs 10 to 20 times faster. I understand that I have more calculations in my original method but "10 to 20 times" seems too much for me.

Do you have any idea how to improve performance?

\$\endgroup\$
  • 5
    \$\begingroup\$ System.arraycopy calls native code, so it will always be much faster: grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… \$\endgroup\$ – konijn Apr 3 '14 at 15:31
  • \$\begingroup\$ @konjin out of pure interest.. if you implemented the same algorithm like the native code one, how much faster would it be when written in native code? \$\endgroup\$ – Vogel612 Apr 3 '14 at 15:44
  • 2
    \$\begingroup\$ Who is marge? Please update the function name to something meaningful -- did you mean "merge"? \$\endgroup\$ – Hogan Apr 3 '14 at 15:46
  • \$\begingroup\$ @Vogel612 - This is almost impossible to do since native code (machine language) allows you to copy data with a single instruction cf en.wikipedia.org/wiki/MOV_%28x86_instruction%29 \$\endgroup\$ – Hogan Apr 3 '14 at 18:19
6
\$\begingroup\$

Some pointers:

  • You keep adding 2 numbers here: startingIndex + i, that could probably be avoided if you went for(int i = startIndex; i < lastIndex; i++){ where lastIndex would be startIndex + count

  • Since ++ happens post evaluation you could simply do buffer[startingIndex + i] = source[index1++];, it does not have to be a separate statement

  • Short circuit logic : if index2 >= maxIndex2, then you should probably have a System.arraycopy copy that fills the rest into index1 and get out. You could the same for when index1 > maxIndex1 but obviously you would fill into index2 then

From a naming perspective, I would rather read upperIndex and lowerIndex than index1 and index2

Totally untested, I would try something like this:

private static void merge(int[] source, int[] buffer, int startingIndex, int count) {
    int lowerIndex = startingIndex;
    int lowerBound = startingIndex + count / 2;
    int upperIndex = lowerBound;
    int upperBound = startingIndex + count;

    for(int i = startingIndex ; i < upperBound ; i++){
        if(upperIndex >= upperBound ){
          System.arraycopy(source, lowerIndex , buffer, i, i - startingIndex );
          return;
        }
        if(lowerIndex >= lowerBound ){
          System.arraycopy(source, upperIndex , buffer, i, i - startingIndex );
          return;
        }
        buffer[i] = source[lowerIndex] < source[upperIndex] ? source[lowerIndex++] : source[upperIndex++]
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.