4
\$\begingroup\$

I am trying to write a NDK program for quicksorting an array. However, in my benchmarks C is doing consistently worse than Java, as indicated by my results:

Java 1190625 C 1809218

Java 895104 C 1372656

Java 1104792 C 1491198

Java 10766875 C 14929115

Java 9200104 C 9770833

Java 5740782 C 9177135

Could someone help me?

package com.example.bill.androidredblacktree;

import android.content.Intent;
import android.net.Uri;
import android.os.Debug;
import android.support.v4.content.FileProvider;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.support.v7.widget.Toolbar;
import android.util.Log;
import android.view.View;

import java.util.Arrays;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

public class QuicksortBenchmarks extends AppCompatActivity {


    public native void QuicksortCPassArray(int a[]);

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_quicksort_benchmarks);


                    int n1[] = {2000,20000};
                    int j1 = 0;
                    for (j1 = 0; j1 < n1.length; j1++) {
                        int counts=0;
                        for (int k1=0;k1<3;k1++) {
                            int i, n = n1[j1];
                            long startTime, estimatedTime, estimatedTime1;

                            int a[];
                            a = new int[n];
                            for (i = 0; i < n; i++) {
                                a[i] = i;
                            }

                            int z, j;
                            Random rnd = ThreadLocalRandom.current();
                            for (j = n - 1; j > 0; j--) {
                                z = rnd.nextInt(j + 1);
                                swap(a, z, j);
                            }

                            int b[]= Arrays.copyOf(a,a.length);

                            startTime = System.nanoTime();
                            quicksort(a, 0, n - 1);
                            estimatedTime = System.nanoTime() - startTime;
                            System.out.print("Java " + estimatedTime + '\n');

                            startTime = System.nanoTime();
                            QuicksortCPassArray(b);
                            estimatedTime1 = System.nanoTime() - startTime;                          
                            System.out.print("C " + estimatedTime1 + '\n');

                        }

                    }







    }

    private static void quicksort(int a[], int x, int y) {

        int q;
        if (x < y) {
            q = partition(a, x, y);
            quicksort(a, x, q - 1);
            quicksort(a, q + 1, y);
        }
    }

    private static int partition(int a[], int x, int y) {
        int temp = a[y];
        int i = x - 1;
        int j;
        for (j = x; j <= y - 1; j++) {
            if (a[j] <= temp) {
                i++;
                swap(a, i, j);
            }
        }
        swap(a, i + 1, y);
        return (i + 1);
    }

    private static void swap(int a[], int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private int[] shuffleArray(int a[]){
        int i;
        for (i = 0; i < a.length; i++) {
            a[i] = i;
        }

        int z;
        Random rnd = ThreadLocalRandom.current();
        for (int j = a.length - 1; j > 0; j--) {
            z = rnd.nextInt(j + 1);
            swap(a, z, j);
        }
        return a;

    }
}
#include <jni.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void quicksort(jint *a, jint x, jint y);

jint partition(jint *a, jint x, jint y);

void swap(jint *a, jint *b);


JNIEXPORT void JNICALL
Java_com_example_bill_androidredblacktree_QuicksortBenchmarks_QuicksortCPassArray(
        JNIEnv *env,
        jobject this,
        jintArray arr) {

    jint *c_array = (*env)->GetIntArrayElements(env, arr, 0);

    jint n = (*env)->GetArrayLength(env, arr);    

    quicksort(c_array, 0, n - 1);

    (*env)->ReleaseIntArrayElements(env, arr, c_array, 0);


}


void quicksort(jint *a, jint x, jint y) {
    jint q;
    if (x < y) {
        q = partition(a, x, y);
        quicksort(a, x, q - 1);
        quicksort(a, q + 1, y);
    }
}


jint partition(jint *a, jint x, jint y) {
    jint temp = *(a + y);
    jint i = x - 1;
    jint j;
    for (j = x; j <= y - 1; j++) {
        if (*(a + j) <= temp) {
            i++;
            jint temp1 = *(a + i);
            *(a + i) = *(a + j);
            *(a + j) = temp1;
            //swap(&a[i], &a[j]);
        }
    }
    jint temp2 = *(a + i + 1);
    *(a + i + 1) = *(a + y);
    *(a + y) = temp2;
    //swap(&a[i + 1], &a[y]);
    return (i + 1);
}


void swap(jint *a, jint *b) {
    jint temp = *a;
    *a = *b;
    *b = temp;
}
\$\endgroup\$
  • \$\begingroup\$ Can you include the definition of jint? Also, how are you calculating the times in the C portion? Are you including the calls to get the array in the timing? \$\endgroup\$ – user1118321 Apr 8 at 5:06
  • \$\begingroup\$ @user1118321 jint is the int type of the JNI function. I am including the calls to the C function as I'm measuring the time in the Java program. \$\endgroup\$ – Bill Apr 8 at 5:59
  • \$\begingroup\$ "jint is the int type of the JNI function." - well yeah, I get that's what it is, but how is it defined? Is it just a typedef that makes an alias of int or is it some other sort of thing? Aren't all types in Java objects? \$\endgroup\$ – user1118321 Apr 9 at 2:01
  • \$\begingroup\$ @user1118321 To be honest, I do not know. I suppose it's an alias of int. \$\endgroup\$ – Bill Apr 9 at 9:04
  • \$\begingroup\$ According to the documentation jint is a 32-bit signed integer native type. I just wanted to make sure because Java handles native types a little differently than C or C-based OOP languages. \$\endgroup\$ – user1118321 Apr 10 at 2:53
1
\$\begingroup\$

Tested on Windows

I tried your program natively on Windows to see what would happen. First, I modified the Java and C files to remove all of the Android related code/naming. Second, I increased the array sizes to 200000 and 2000000. Then I used Visual Studio C++ to compile the C file, using this command:

cl /LD csort.c /I<$JAVA_HOME>\include /I<$JAVA_HOME>\include\win32

(where <$JAVA_HOME> was the name of my Java home directory).

Then I compiled and ran the Java portion:

% javac qsort.java
% java -Djava.library.path=. qsort

Java 23927588 C 29405966
Java 17247793 C 29613407
Java 16999298 C 28819718
Java 192228697 C 371417828
Java 193105113 C 344951184
Java 193282387 C 344107735

As you can see, the C sort was slower than the Java sort, just like what you encountered.

Turn optimizations on

I instrumented the C code to print out timestamps after each line of C code and found that the GetIntArrayElements() and ReleaseIntArrayElements() were not using any time. All of the time was spent in quicksort() itself. So I was puzzled by why the C code would be slower than the Java code.

Then I thought about turning optimizations on. I recompiled the C code with an additional /O2 flag:

cl /LD csort.c /I<$JAVA_HOME>\include /I<$JAVA_HOME>\include\win32 /O2

I reran the test:

java -Djava.library.path=. qsort 

Java 21830161 C 12143244
Java 16070011 C 11936736
Java 16373243 C 13104565
Java 186278523 C 143997203
Java 189248011 C 144834744
Java 193083653 C 141156471

Now you can see that the C code is actually about 30% faster than the Java code.

Modified code

Here is the modified code in case you want to try it yourself:

qsort.java

import java.util.Arrays;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

public class qsort {
    public native void QuicksortCPassArray(int a[]);

    static {
        System.loadLibrary("csort");
    }

    public static void main(String [] args)
    {
        int n1[] = {200000, 2000000};
        int j1 = 0;
        for (j1 = 0; j1 < n1.length; j1++) {
            int counts=0;
            for (int k1=0;k1<3;k1++) {
                int i, n = n1[j1];
                long startTime, estimatedTime, estimatedTime1;

                int a[];
                a = new int[n];
                for (i = 0; i < n; i++) {
                    a[i] = i;
                }

                int z, j;
                Random rnd = new Random(System.currentTimeMillis());
                for (j = n - 1; j > 0; j--) {
                    z = rnd.nextInt(j + 1);
                    swap(a, z, j);
                }

                int b[]= Arrays.copyOf(a,a.length);

                startTime = System.nanoTime();
                quicksort(a, 0, n - 1);
                estimatedTime = System.nanoTime() - startTime;
                System.out.print("Java " + estimatedTime + ' ');

                startTime = System.nanoTime();
                new qsort().QuicksortCPassArray(b);
                estimatedTime1 = System.nanoTime() - startTime;
                System.out.print("C " + estimatedTime1 + '\n');

            }

        }
    }

    private static void quicksort(int a[], int x, int y) {

        int q;
        if (x < y) {
            q = partition(a, x, y);
            quicksort(a, x, q - 1);
            quicksort(a, q + 1, y);
        }
    }

    private static int partition(int a[], int x, int y) {
        int temp = a[y];
        int i = x - 1;
        int j;
        for (j = x; j <= y - 1; j++) {
            if (a[j] <= temp) {
                i++;
                swap(a, i, j);
            }
        }
        swap(a, i + 1, y);
        return (i + 1);
    }

    private static void swap(int a[], int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private int[] shuffleArray(int a[]){
        int i;
        for (i = 0; i < a.length; i++) {
            a[i] = i;
        }

        int z;
        Random rnd = ThreadLocalRandom.current();
        for (int j = a.length - 1; j > 0; j--) {
            z = rnd.nextInt(j + 1);
            swap(a, z, j);
        }
        return a;

    }
}

csort.c

(only changed the name of the function)

#include <jni.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void quicksort(jint *a, jint x, jint y);

jint partition(jint *a, jint x, jint y);

void swap(jint *a, jint *b);

JNIEXPORT void JNICALL
Java_qsort_QuicksortCPassArray(
        JNIEnv *env,
        jobject this,
        jintArray arr) {

    jint *c_array = (*env)->GetIntArrayElements(env, arr, 0);

    jint n = (*env)->GetArrayLength(env, arr);

    quicksort(c_array, 0, n - 1);

    (*env)->ReleaseIntArrayElements(env, arr, c_array, 0);
}


void quicksort(jint *a, jint x, jint y) {
    jint q;
    if (x < y) {
        q = partition(a, x, y);
        quicksort(a, x, q - 1);
        quicksort(a, q + 1, y);
    }
}


jint partition(jint *a, jint x, jint y) {
    jint temp = *(a + y);
    jint i = x - 1;
    jint j;
    for (j = x; j <= y - 1; j++) {
        if (*(a + j) <= temp) {
            i++;
            jint temp1 = *(a + i);
            *(a + i) = *(a + j);
            *(a + j) = temp1;
            //swap(&a[i], &a[j]);
        }
    }
    jint temp2 = *(a + i + 1);
    *(a + i + 1) = *(a + y);
    *(a + y) = temp2;
    //swap(&a[i + 1], &a[y]);
    return (i + 1);
}


void swap(jint *a, jint *b) {
    jint temp = *a;
    *a = *b;
    *b = temp;
}
\$\endgroup\$
  • \$\begingroup\$ You are the real MVP! Thank you for taking the time to try to figure out the solution to my stupid problem, I appreciate it. Do you have any idea what -O2 does and it takes so little time while using O2? \$\endgroup\$ – Bill Apr 10 at 9:57
  • 1
    \$\begingroup\$ @Bill For the Visual C++ compiler that I used, the /O2 flag means "optimize for speed". If you are building for Android, you are probably using the clang compiler, which has similar optimization options such as -O2 and -O3 (the higher the number the more aggressive the optimizations allowed). \$\endgroup\$ – JS1 Apr 10 at 18:47
  • 1
    \$\begingroup\$ @Bill As for what exactly /O2 does to make the code faster, some possibilities are: inlining functions, unrolling loops, common subexpression elimination, etc. You can look at this article if you want to learn about optimizing compilers. \$\endgroup\$ – JS1 Apr 10 at 18:53
2
\$\begingroup\$

Performance

What are you trying to determine with this test? I ask because if you're simply trying to compare the speed of sorting in Java vs. sorting in C, you haven't constructed the test correctly. As it stands, the calls to GetIntArrayElements(), GetArrayLength(), and ReleaseIntArrayElements() are doing work that's not counted in the Java case.

If, on the other hand, you're trying to determine if converting your data from Java format to C format and then sorting it in C is faster than just sorting it in Java, then you've got a reasonable test. But the results should be fairly unsurprising. (Though it's always good to test your assumptions!)

If I'm understanding the documentation correctly, the calls to GetIntArrayElements() and ReleaseIntArrayElements() may be allocating, copying, and freeing memory. Those operations can be time consuming and may explain the differences you're seeing. You should run your code under a profiler to see for sure.

That said, your implementation is about twice as fast as the built-in qsort() function, which needs to make a function call for each comparison. That's pretty decent.

Naming

I realize this is just simple sorting but you really should name your function arguments better. For quicksort(), the arguments are the array, the start index of the range to sort and the end index of the range to sort. Honestly, a is fine for a general-purpose sort function. (If you are writing something more specific and you know the array will represent something specific, you should name the array argument based on that.) But there's no reason you can name x and y something like startIndex and endIndex, or at least start and end.

Likewise, when you have a bunch of temporary variables, naming them temp, temp1, and temp2 is useless. In partition() the variable temp is the value in the last element of the range, so just call it lastElement. temp1 and temp2 are used for swapping, so you could name them swap. Although, personally, calling the swap() function you wrote would be clearer and it would likely be inlined anyway, giving you the same speed when compiled with optimizations on.

\$\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.