Using NDK for Performance: Dalvik vs. Native

Posted on Apr 8, 2010 (4 years ago). Seen 21,429 times. 6 comments. Permalink Feed
Photo Marko Gargenta
@MarkoGargenta
Member since Jan 19, 2007
Location: San Francisco
Stream Posts: 42
Tagged as: Android Tutorial
Updated for non-recursive algorithm, by popular demand

NDK is very useful for developing parts of your Android application in native code. The main motivation is performance.

In this example, I wrote a simple SDK+NDK application that uses the same Fibonacci algorithm implemented both in C and Java. The results in performance are astonishing.

The Activity: /src/com/marakana/Fibonacci.java

This is the activity that specifies a simple UI to enter the number for which we want to compute Fibonacci value. It also provides simple output.


Code:

package com.marakana;

import android.app.Activity;
import android.os.Bundle;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;

public class Fibonacci extends Activity implements OnClickListener {
TextView textResult;
Button buttonGo;
EditText editInput;

@Override
public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.main);

// Find UI views
editInput = (EditText) findViewById(R.id.editInput);
textResult = (TextView) findViewById(R.id.textResult);
buttonGo = (Button) findViewById(R.id.buttonGo);
buttonGo.setOnClickListener(this);
}

public void onClick(View view) {
int input = Integer.parseInt(editInput.getText().toString());
long start, stop;
int result;
String out = "";

// Dalvik - Recursive
start = System.currentTimeMillis();
result = FibLib.fibJ(input);
stop = System.currentTimeMillis();
out += String.format("Dalvik recursive: %d (%d msec)", result, stop - start);

// Dalvik - Iterative
start = System.currentTimeMillis();
result = FibLib.fibJI(input);
stop = System.currentTimeMillis();
out += String.format("\nDalvik iterative: %d (%d msec)", result, stop - start);

// Native - Recursive
start = System.currentTimeMillis();
result = FibLib.fibN(input);
stop = System.currentTimeMillis();
out += String.format("\nNative recursive: %d (%d msec)", result, stop - start);

// Native - Iterative
start = System.currentTimeMillis();
result = FibLib.fibNI(input);
stop = System.currentTimeMillis();
out += String.format("\nNative iterative: %d (%d msec)", result, stop - start);

textResult.setText(out);
}
}


The Layout: res/layout/main.xml

The straight-forward XML layout for the activity above.

Code:

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:orientation="vertical" android:layout_width="fill_parent"
android:layout_height="fill_parent" android:gravity="center_horizontal">
<TextView android:layout_width="fill_parent"
android:layout_height="wrap_content" android:text="@string/app_name"
android:gravity="center" android:textSize="40sp"
android:layout_margin="10dp" />
<LinearLayout android:layout_width="wrap_content"
android:layout_height="wrap_content">
<EditText android:layout_width="wrap_content"
android:layout_height="wrap_content" android:id="@+id/editInput"
android:hint="Input" android:textSize="30sp" android:inputType="number"
android:layout_margin="10dp"></EditText>
<Button android:layout_width="wrap_content"
android:layout_height="wrap_content" android:id="@+id/buttonGo"
android:text="Go" android:textSize="30sp" android:layout_margin="10sp"></Button>
</LinearLayout>

<TextView android:layout_width="wrap_content"
android:layout_height="wrap_content" android:id="@+id/textResult"
android:text="RESULT" android:textSize="20sp"></TextView>

</LinearLayout>



JNI Interface to Native Code: /src/com/marakana/FibLib.java

This code represents the JNI interface from Java to the native code. It also provides the pure Java version of Fibonacci function so that we can compare the speed.

Code:

package com.marakana;

public class FibLib {

// Java implementation - recursive
public static int fibJ(int n) {
if (n <= 0)
return 0;
if (n == 1)
return 1;
return fibJ(n - 1) + fibJ(n - 2);
}

// Java implementation - iterative
public static int fibJI(int n) {
int previous = -1;
int result = 1;
for (int i = 0; i <= n; i++) {
int sum = result + previous;
previous = result;
result = sum;
}
return result;
}

// Native implementation
static {
System.loadLibrary("fib");
}

// Native implementation - recursive
public static native int fibN(int n);

// Native implementation - iterative
public static native int fibNI(int n);
}



Auto-generated JNI Header: /jni/com_marakana_FibLib.h

For how this works, see my NDK example.

Code:

/* DO NOT EDIT THIS FILE - it is machine generated */
#include <jni.h>
/* Header for class com_marakana_FibLib */

#ifndef _Included_com_marakana_FibLib
#define _Included_com_marakana_FibLib
#ifdef __cplusplus
extern "C" {
#endif
/*
* Class: com_marakana_FibLib
* Method: fibN
* Signature: (I)I
*/
JNIEXPORT jint JNICALL Java_com_marakana_FibLib_fibN
(JNIEnv *, jclass, jint);

/*
* Class: com_marakana_FibLib
* Method: fibNI
* Signature: (I)I
*/
JNIEXPORT jint JNICALL Java_com_marakana_FibLib_fibNI
(JNIEnv *, jclass, jint);

#ifdef __cplusplus
}
#endif
#endif



C Implementation of the JNI Header: /jni/fib.c

This is where we provide the actual C version of the Fibonacci function.

Code:

#include "com_marakana_FibLib.h"


jint fibN(jint n) {
if(n<=0) return 0;
if(n==1) return 1;
return fibN(n-1) + fibN(n-2);
}

jint fibNI(jint n) {
jint previous = -1;
jint result = 1;
jint i=0;
jint sum=0;
for (i = 0; i <= n; i++) {
sum = result + previous;
previous = result;
result = sum;
}
return result;
}

JNIEXPORT jint JNICALL Java_com_marakana_FibLib_fibN
(JNIEnv *env, jclass obj, jint n) {
return fibN(n);
}

JNIEXPORT jint JNICALL Java_com_marakana_FibLib_fibNI
(JNIEnv *env, jclass obj, jint n) {
return fibNI(n);
}



NDK Makefile: /jni/Android.mk

Again, for how this works, see my NDK example.

Code:

LOCAL_PATH := $(call my-dir)

include $(CLEAR_VARS)

LOCAL_MODULE := fib
LOCAL_SRC_FILES := fib.c

include $(BUILD_SHARED_LIBRARY)


Create your library using NDK, and run your app. The result should look like this:

On Emulator


On HTC Hero

I think the picture is worth 1000 words. There's clearly a huge (order of magnitude) improvement in running certain computation-intensive code outside Dalvik, when running recursively. Iterative computations are much closer together.

Source:
http://thenewcircle.com/static/tutorials/Fibonacci.zip
http://thenewcircle.com/static/tutorials/Fibonacci.apk

Comments

Posted on Apr 8, 2010
Photo Mike Leahy
Founder
EGR Software
Member since Apr 8, 2010
Can you do a non-recursive version as that will be a valuable data point. Of course the native version is going to be faster regardless, but it will take out recursive method calling overhead. I haven't looked into it, but it may be possible to unroll the non-recursive implementation too a little bit. There are ways to make things faster. Of course once the improved Dalvik VMs get out there and conceivable JIT of some sort things will be way different too. So this is today's Dalvik performance which will be a lot slower than Dalvik performance in one year or so.
Posted on Apr 9, 2010
Photo Aleksandar Gargenta
Technical Program Manager
Twitter Inc
Member since Jan 19, 2007
Location: San Francisco
I second that. I would love to see if the non-recursive version of the algorithm makes a significant difference for Dalvik.

Of course, JIT powered Dalvik is the way to go - and the early version already shows a huge promise (with a 3x performance boost), but I wonder when this will trickle down to our mortal phones... and what effect will JIT have on memory footprint and battery life....
Posted on Nov 23, 2010
Photo Ronald Ammann
Avira GmbH
Member since Nov 23, 2010
In the meanwhile do you have any results comparing native NDK vs. JIT Dalvik (FroYo)
Posted on Nov 23, 2010
Photo Marko Gargenta
@MarkoGargenta
Member since Jan 19, 2007
Location: San Francisco
I don't but will update this soon...
Posted on Jul 31, 2011
Photo Ekko Smith
Software Engineer
-
Member since Jul 31, 2011
Hi,

Very cool post.
I have a few questions which i hope you can answer :

Consider the scenario : 3 *.cpp files : x.cpp, y.cpp, z.cpp and 3 *.h header files : x.h, y.h and z.h. They work on a separate project because they #include "ownlib.h" and have the additional static lib ownlibrary.lib attached to the project (for which i don't have the sources to build it again inside the *.jni).

Can i make the Java *.jni - Android NDK ndk-build compile the *.so? Is there a way that i can specify it to use my ownlibrary.lib? From what i tried so far i have "identifier not found" errors.

Here is my Android.mk file.

LOCAL_PATH:= $(call my-dir)

include $(CLEAR_VARS)

LOCAL_MODULE := libgl2jni
LOCAL_CFLAGS := -Werror
LOCAL_SRC_FILES := /
/ x.cpp /
/ y.cpp /
/ z.cpp /
/ gl_code.cpp

LOCAL_LDLIBS := -llog -lGLESv2

include $(BUILD_SHARED_LIBRARY)

x.cpp also #include <algorithm> and even though i use "using namespace std;" , i get "identifier not found" for min(), max() ... function calls.

Thanks
Posted on Feb 14, 2012
Photo Sundaresha Maligera
NCS
Member since Feb 14, 2012
Is it possible to develop a webview using native code(C)....Help me please