Our senior design project is basically a feasibility study of Real Time Java on Embedded Systems. Real time capabilities aside, one task we have to do is write a program in Java, write the same program in C, and time how long it takes to execute. The program does bilinear interpolation which is just sort of a number crunching thing.
I realize many factors can affect the performance. The program tested in Java and C has no real time constraints and is single threaded. It simply performs bilinear interpolation for a specified number of runs. We time the total time spent on all of the runs and divide it by the number of calculations to get the time per run.
I don't remember specific numbers, but we ended up with C being something like 315 times faster than Java. That is huge! We asked the company who did the RTJ implementation for us how much we can expect C to be faster and were told that with fully compiled (not interpreted) Java code, C will be approximately 3 times faster. We have not yet tested with compiled code since we do not have enough Flash memory to compile everything, so we are in the process of profiling and compiling only a portion of the Java code.
I concerned that even with compiled code, our Java program is going to be many many times slower than C. I've searched and found a few numbers thrown around, which was that interpreted Java code is 10-20x slower than C.
Has anyone done any work with this and have a rough idea? I've looked at the code to determine if there is something happening with the Java VM that would cause it to be so much slower. I think pretty much all of the variables used are on the stack. I think the garbage collector only runs when references to objects on the heap are no longer referenced, something that I don't think we are doing. Any ideas on things that could be happening with the JVM to cause such a slowdown, or things to avoid doing? Thanks
Java code
C code
I realize many factors can affect the performance. The program tested in Java and C has no real time constraints and is single threaded. It simply performs bilinear interpolation for a specified number of runs. We time the total time spent on all of the runs and divide it by the number of calculations to get the time per run.
I don't remember specific numbers, but we ended up with C being something like 315 times faster than Java. That is huge! We asked the company who did the RTJ implementation for us how much we can expect C to be faster and were told that with fully compiled (not interpreted) Java code, C will be approximately 3 times faster. We have not yet tested with compiled code since we do not have enough Flash memory to compile everything, so we are in the process of profiling and compiling only a portion of the Java code.
I concerned that even with compiled code, our Java program is going to be many many times slower than C. I've searched and found a few numbers thrown around, which was that interpreted Java code is 10-20x slower than C.
Has anyone done any work with this and have a rough idea? I've looked at the code to determine if there is something happening with the Java VM that would cause it to be so much slower. I think pretty much all of the variables used are on the stack. I think the garbage collector only runs when references to objects on the heap are no longer referenced, something that I don't think we are doing. Any ideas on things that could be happening with the JVM to cause such a slowdown, or things to avoid doing? Thanks
Java code
//see http://en.wikipedia.org/wiki/Bilinear_interpolation
public class NewLinear {
public static void main(String[] args) {
//x axis values
float xBegin = 0;
float xIncrement = 1;
int xLength = 10;
//y axis values
float yBegin = 0;
float yIncrement = 1;
int yLength = 10;
//low & high limits of possible random numbers of value matrix
int qLow = 0;
int qHigh = 10000000;
//number of times to run interpolation (random numbers will
//be used for x & y values to interpolate)
int numTimesRun = 10000;
//build x & y arrays according to user input
float[] xArray = build1DArray(xBegin, xIncrement, xLength);
float[] yArray = build1DArray(yBegin, yIncrement, yLength);
//build q array
float [][] qArray = build2DArray(xLength, yLength, qLow, qHigh);
printComplete(qArray, xArray, yArray);
System.out.println("Timer Started");
for ( int j = 0; j < 30; j++ ) {
long startTimeMilli = System.currentTimeMillis();
//prompt user for x values & linearly interpolate y values
for ( int i = 0; i < numTimesRun; i++ ) {
//create random x & y values between the high & low x & y axis values
//make max values less than max x & y axis values
float xMax = ((xIncrement * (xLength-1)) + (xBegin)) - 0.00001F;
float yMax = ((yIncrement * (yLength-1)) + (yBegin)) - 0.00001F;
float xVal = ((float)Math.random() * xMax) - xBegin;
float yVal = ((float)Math.random() * yMax) - yBegin;
//find y value of x value user inputted
float qVal = interpolate(xArray, yArray, qArray,
xVal, yVal,
xLength, yLength,
xIncrement, yIncrement,
xBegin, yBegin);
}
long endTimeMilli = System.currentTimeMillis();
System.out.println("and " + (endTimeMilli - startTimeMilli) + " milliseconds");
System.out.println("for an average of " + (endTimeMilli - startTimeMilli)/(long)numTimesRun + " milliseconds");
}
}
public static float[] build1DArray(float xBegin, float xIncrement, int xLength) {
float[] array = new float[xLength];
float xVal = xBegin;
for (int x = 0; x < array.length; x++){
array[x] = xVal;
xVal = xVal + xIncrement;
}
return array;
}
public static float[][] build2DArray(int xLength, int yLength, float min, float max) {
float[][] array = new float[yLength][xLength];
for (int row = 0; row < array.length; row++){
for(int col = 0; col < array[0].length; col++) {
float n = (float)(max * Math.random()) + min;
array[row][col] = n;
}
}
return array;
}
public static void print2DArray(float[][] array) {
for (int row = 0; row < array.length; row++){
for(int col = 0; col < array[0].length; col++) {
System.out.print(array[row][col] + "\t ");
}
System.out.println();
}
System.out.println();
}
public static void print1DArray(float[] array) {
System.out.print("[ ");
for(int j=0;j<array.length;j++) {
System.out.print(array[j]);
if ( j != array.length-1 ) {
System.out.print("\t");
}
}
System.out.println(" ]\n");
}
public static void printComplete(float[][] qArray, float[] xArray, float[] yArray) {
System.out.println("y");
for (int row = 0; row < qArray.length; row++){
for(int col = 0; col < qArray[0].length; col++) {
if (col == 0) {
System.out.print(yArray[yArray.length-row-1] + "\t ");
}
System.out.print(qArray[row][col] + "\t ");
}
System.out.println();
}
System.out.print("x\t");
for(int j=0;j<xArray.length;j++) {
System.out.print(xArray[j]);
if ( j != xArray.length-1 ) {
System.out.print("\t");
}
}
System.out.println("\n");
}
/**
* A function that uses bilinear interpolation to find an estimated value
* given an x & y value
*
* @param xArray x-axis numbers
* @param yArray y-axis numbers
* @param qArray matrix built relating to x-axis & y-axis numbers
* @param xVal x value of user input
* @param yVal y value of user input
* @param xLength length of x axis
* @param yLength length of y axis
* @param xIncrement value x axis is incremented by
* @param yIncrement value y axis is incremented by
* @param xBegin value x axis begins at
* @param yBegin value y axis begins at
* @return bi-linearly interpolated value
*/
public static float interpolate(
float[] xArray, float[] yArray, float[][] qArray,
float xVal, float yVal,
int xLength, int yLength,
float xIncrement, float yIncrement,
float xBegin, float yBegin) {
//Make sure x & y pair not in table; if it is return corresponding q value
for (int x = 0; x < xArray.length; x++){
if ( xArray[x] == xVal ) {
//now check for y vals
for ( int y = 0; y < yArray.length; y++ ) {
if ( yArray[y] == yVal ) {
System.out.println("x & y pair in table");
return qArray[(yLength-1)-y][x];
}
}
}
}
//Find the index of the table entry just below & above the x val & y val
//then set variables used in formula
int xIndex = (int)((xVal - xBegin) / xIncrement);
int yIndex = (int)((yVal - yBegin) / yIncrement);
float x1 = xArray[xIndex];
float x2 = xArray[xIndex + 1];
float y1 = yArray[yIndex];
float y2 = yArray[yIndex + 1];
float x1y1 = qArray[(yLength-1)-yIndex][xIndex];
float x1y2 = qArray[(yLength-1)-(yIndex+1)][xIndex];
float x2y1 = qArray[(yLength-1)-yIndex][xIndex+1];
float x2y2 = qArray[(yLength-1)-(yIndex+1)][xIndex+1];
//perform bilinear interpolation
float r1 = ( ((x2 - xVal)/xIncrement) * x1y1 ) + (((xVal-x1)/xIncrement) * x2y1);
float r2 = ( ((x2 - xVal)/xIncrement) * x1y2 ) + (((xVal-x1)/xIncrement) * x2y2);
float interp = ( ((y2 - yVal)/yIncrement) * r1 ) + (((yVal-y1)/yIncrement) * r2);
return interp;
}
}
C code
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void build1DArray(float, float, int, float *);
void build2DArray(int, int, float, float, float **);
void printComplete(float**, float*, float*, int, int);
float interpolate(
float* , float*, float**,
float, float,
int, int,
float, float,
float, float);
int main(void) {
float xBegin = 0;
float xIncrement = 1;
int xLength = 10;
int i = 0;
int j = 0;
//y axis values
float yBegin = 0;
float yIncrement = 1;
int yLength = 10;
//low & high limits of possible random numbers of value matrix
int qLow = 0;
int qHigh = 10000000;
//number of times to run interpolation (random numbers will
//be used for x & y values to interpolate)
int numTimesRun = 1000000;
float *xArray;
float *yArray;
float **qArray;
int startTime;
int endTime;
//build x & y arrays according to user input
xArray = malloc(xLength * sizeof (float)); //new float[xLength];
build1DArray(xBegin, xIncrement, xLength, xArray);
yArray = malloc(yLength * sizeof (float)); //new float[yLength];
build1DArray(yBegin, yIncrement, yLength, yArray);
//build q array
qArray = (float **) malloc(yLength*sizeof(float)); //new float* [yLength];
for(i=0;i<yLength;i++)
*(qArray+i) = malloc(xLength*sizeof(float)); //new float[xLength];
build2DArray(xLength, yLength, qLow, qHigh, qArray);
printComplete(qArray, xArray, yArray, xLength, yLength);
for (j = 0; j < 30; j++ ) {
startTime = clock();
//prompt user for x values & linearly interpolate y values
for (i = 0; i < numTimesRun; i++ ) {
//create random x & y values between the high & low x & y axis values
//make max values less than max x & y axis values
float xMax = ((xIncrement * (xLength-1)) + (xBegin)) - 0.00001;
float yMax = ((yIncrement * (yLength-1)) + (yBegin)) - 0.00001;
float xVal = (rand()/((float)(RAND_MAX)+1) * xMax) - xBegin;
float yVal = (rand()/((float)(RAND_MAX)+1) * yMax) - yBegin;
//find y value of x value user inputted
float qVal = interpolate(xArray, yArray, qArray,
xVal, yVal,
xLength, yLength,
xIncrement, yIncrement,
xBegin, yBegin);
}
endTime = clock();
printf("Loop %d: ",j);
printf("Done, took: %f seconds\n", (float)((endTime - startTime)/CLOCKS_PER_SEC));
printf("Done, took: %f milliseconds\n", (float)((endTime - startTime)/CLOCKS_PER_SEC)/(float)numTimesRun*1000.0);
}
free(xArray);
free(yArray);
for(j=0;j<yLength;j++)
free(qArray[j]);
free(qArray);
return 0;
}
void build1DArray(float xBegin, float xIncrement, int xLength, float *array) {
float xVal = xBegin;
int x = 0;
for (x = 0; x < xLength; x++){
array[x] = xVal;
xVal = xVal + xIncrement;
}
return;
}
void build2DArray(int xLength, int yLength, float min, float max, float **array) {
int row = 0;
int col = 0;
for (row = 0; row < yLength; row++){
for(col = 0; col < xLength; col++) {
//fill with random number between yLow and yHigh
float n = (float)(max * rand()/((float)(RAND_MAX)+1)) + min;
array[row][col] = n;
}
}
return;
}
void printComplete(float** qArray, float* xArray, float* yArray, int xLength, int yLength) {
int row = 0;
int col = 0;
int i = 0;
printf("y\n");
for (row = 0; row < yLength; row++){
for(col = 0; col < xLength; col++) {
if (col == 0) {
printf("%.0f\t",yArray[yLength-row-1]);
}
printf("%f \t",qArray[row][col]);
}
printf("\n");
}
printf("x\t");
for(j=0;j<xLength;j++) {
printf("%.0f",xArray[j]);
if ( j != xLength-1 ) {
printf("\t\t");
}
}
printf("\n");
}
float interpolate(
float* xArray, float* yArray, float** qArray,
float xVal, float yVal,
int xLength, int yLength,
float xIncrement, float yIncrement,
float xBegin, float yBegin) {
int x,y;
int xIndex;
int yIndex;
float x1;
float x2;
float y1;
float y2;
float x1y1;
float x1y2;
float x2y1;
float x2y2;
float r1,r2,interp;
//Make sure x & y pair not in table; if it is return corresponding q value
for (x = 0; x < xLength; x++){
if ( xArray[x] == xVal ) {
//now check for y vals
for (y = 0; y < yLength; y++ ) {
if ( yArray[y] == yVal ) {
return qArray[(yLength-1)-y][x];
}
}
}
}
//Find the index of the table entry just below & above the x val & y val
//then set variables used in formula
xIndex = (int)((xVal - xBegin) / xIncrement);
yIndex = (int)((yVal - yBegin) / yIncrement);
x1 = xArray[xIndex];
x2 = xArray[xIndex + 1];
y1 = yArray[yIndex];
y2 = yArray[yIndex + 1];
x1y1 = qArray[(yLength-1)-yIndex][xIndex];
x1y2 = qArray[(yLength-1)-(yIndex+1)][xIndex];
x2y1 = qArray[(yLength-1)-yIndex][xIndex+1];
x2y2 = qArray[(yLength-1)-(yIndex+1)][xIndex+1];
//perform bilinear interpolation
r1 = ( ((x2 - xVal)/xIncrement) * x1y1 ) + (((xVal-x1)/xIncrement) * x2y1);
r2 = ( ((x2 - xVal)/xIncrement) * x1y2 ) + (((xVal-x1)/xIncrement) * x2y2);
interp = ( ((y2 - yVal)/yIncrement) * r1 ) + (((yVal-y1)/yIncrement) * r2);
return interp;
}