zhenganyi
Reputation: 179
Different running time results with different method invocation order
I have written a program in Java; it uses two methods to solve a system of linear equations, and I want to calculate the running time of each method.
I have found that I get the different running time result when I change the running order of the two methods.
Why is that?
/*using direct_method and Jacobi_method to resolve the linear equation,and compare each running time*/
public class Jacobi_iterat {
/*Jacobi part*/
/*find lower triangular matrix*/
private static float[][] find_lower(float data[][],int k){
int length=data.length;
float data2[][]=new float[length][length];
if(k>=0){
for(int i=0;i<=length-k-1;i++){
for(int j=0;j<=i+k;j++){
data2[i][j]=data[i][j];
}
}
for(int i=length-k;i<length;i++){
for(int j=0;j<length;j++){
data2[i][j]=data[i][j];
}
}
}
else{
for(int i=-k;i<length;i++){
for(int j=0;j<=i+k;j++){
data2[i][j]=data[i][j];
}
}
}
return data2;
}
/*negative of the matrix*/
private static float[][] opposite_matrix(float[][] data){
int M=data.length;
int N=data[0].length;
float data_temp[][]=new float[M][N];
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
data_temp[i][j]=-data[i][j];
}
}
return data_temp;
}
/*inverse matrix of the diagnal matrix*/
private static float[][] inv_diagnal(float[][] data){
int M=data.length;
int N=data[0].length;
float[][] data2=new float[M][N];
float fenzi=1;
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if(i==j){
data2[i][j]=fenzi/data[i][j];
}
}
}
return data2;
}
/*upper triangular matrix*/
private static float[][] find_upper(float[][] data,int k){
int length=data.length;
int M=length-k;
float[][] data2=new float[length][length];
if(k>=0){
for(int i=0;i<M;i++){
for(int j=k;j<length;j++){
data2[i][j]=data[i][j];
}
k+=1;
}
}
else {
for(int i=0;i<-k;i++){
for(int j=0;j<length;j++){
data2[i][j]=data[i][j];
}
}
for(int i=-k;i<length;i++){
for(int j=i+k;j<length;j++){
data2[i][j]=data[i][j];
}
}
}
return data2;
}
/*add two matrix*/
private static float[][] matrix_add(float[][] data1,float[][] data2){
int M=data1.length;
int N=data1[0].length;
float data[][]=new float[M][N];
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
data[i][j]=data1[i][j]+data2[i][j];
}
}
return data;
}
private static float[] matrix_add2(float[] data1,float[] data2){
int M=data1.length;
float data[]=new float[M];
for(int i=0;i<M;i++){
data[i]=data1[i]+data2[i];
}
return data;
}
/*multiply two matrix*/
private static float[][] multiply(float[][] data1,float[][] data2){
int M=data1.length;
int N=data1[0].length;
int K=data2[0].length;
float[][] data3=new float[M][K];
for(int i=0;i<M;i++){
for(int j=0;j<K;j++){
for(int k=0;k<N;k++){
data3[i][j]+=data1[i][k]*data2[k][j];
}
}
}
return data3;
}
private static float[] multiply2(float[][] data1,float[] data2){
int M=data1.length;
int N=data1[0].length;
float[] data3=new float[M];
for(int k=0;k<M;k++){
for(int j=0;j<N;j++){
data3[k]+=data1[k][j]*data2[j];
}
}
return data3;
}
/*calculate the diagnal matrix */
private static float[][] find_diagnal(float A[][]) {
int m = A.length;
int n = A[0].length;
float B[][] = new float[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
B[i][j] = A[i][j];
}
}
}
return B;
}
/*Jacobi_method*/
private static float[] Jacobi_method(float[][] A,float[] B,float[] X){
float[][] D=find_diagnal(A);
float[][] inv_D=inv_diagnal(D);
float[][] opposite_D=opposite_matrix(inv_D);
float[][] L=find_lower(A, -1);
float[][] U=find_upper(A, 1);
float[][] Bo=multiply(opposite_D,matrix_add(L, U));
float[] F=multiply2(inv_D, B);
return matrix_add2(multiply2(Bo, X),F);
}
/*calculate the two norm between two vector*/
private static double cal_error(float[] X1,float[] X2){
int M=X1.length;
double temp=0;
for(int i=0;i<M;i++){
temp+=Math.pow((X1[i]-X2[i]),2);
}
temp=Math.sqrt(temp);
return temp;
}
/*end of Jacobi part*/
/*direct method part*/
private static float[] cal_direct(float[][] A,float[] B){
int M=A[0].length;
float X[]=new float[M];
float[][] inv_A=inv(A);
X=multiply2(inv_A, B);
return X;
}
/*transpose of the matrix*/
private static float [][]trans(float[][] data){
int i=data.length;
int j=data[0].length;
float[][] data2=new float[j][i];
for(int k2=0;k2<j;k2++){
for(int k1=0;k1<i;k1++){
data2[k2][k1]=data[k1][k2];
}
}
return data2;
}
/*calculate the ajoint matrix of the matrix*/
private static float[][] ajoint(float[][] data) {
int M=data.length;
int N=data[0].length;
float data2[][]=new float[M][N];
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if((i+j)%2==0){
data2[i][j]=cal_det(get_complement(data, i, j));
}
else{
data2[i][j]=-cal_det(get_complement(data, i, j));
}
}
}
return trans(data2);
}
/*inverse of the matrix*/
private static float[][] inv(float [][] data){
int M=data.length;
int N=data[0].length;
float data2[][]=new float[M][N];
float det_val=cal_det(data);
data2=ajoint(data);
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
data2[i][j]=data2[i][j]/det_val;
}
}
return data2;
}
/* calculate the determinant of the matrix*/
private static float cal_det(float[][] data) {
float ans=0;
if(data[0].length==2){
ans=data[0][0]*data[1][1]-data[0][1]*data[1][0];
}
else{
for(int i=0;i<data[0].length;i++){
float[][] data_temp=get_complement(data, 0, i);
if(i%2==0){
ans=ans+data[0][i]*cal_det(data_temp);
}
else{
ans=ans-data[0][i]*cal_det(data_temp);
}
}
}
return ans;
}
private static float[][] get_complement(float[][] data, int i, int j) {
int x = data.length;
int y = data[0].length;
float data2[][] = new float[x - 1][y - 1];
for (int k = 0; k < x - 1; k++) {
if (k < i) {
for (int kk = 0; kk < y - 1; kk++) {
if (kk < j) {
data2[k][kk] = data[k][kk];
} else {
data2[k][kk] = data[k][kk + 1];
}
}
} else {
for (int kk = 0; kk < y - 1; kk++) {
if (kk < j) {
data2[k][kk] = data[k + 1][kk];
} else {
data2[k][kk] = data[k + 1][kk + 1];
}
}
}
}
return data2;
}
/*end of direct method part*/
public static void main(String args[]){
System.out.println("input the dimensions of the coefficient square：");
Scanner scan=new Scanner(System.in);
int M=scan.nextInt();
System.out.println("input the dimensions of the equation value vector：");
int K=scan.nextInt();
if(M!=K){
System.out.println("the number of equations and unknowns are not equal!");
System.exit(0);
}
System.out.println("input coefficient matrix：");
float[][] A=new float[M][M];
for(int i=0;i<M;i++){
for(int j=0;j<M;j++){
A[i][j]=scan.nextFloat();
}
}
System.out.println("input the value vector");
float[] B=new float[M];
for(int i=0;i<M;i++){
B[i]=scan.nextFloat();
}
System.out.println("input the initial iteration vector：");
float[] X=new float[M];
for(int i=0;i<M;i++){
X[i]=scan.nextFloat();
}
System.out.println("input the bound of error：");
float er=scan.nextFloat();
float temp[]=new float[M];
/*calculate the running time of two method,but I get the different running time result when I exchange the running order of two method, why?*/
/*calculate the running time of Jacobi_method*/
long startTime=System.nanoTime();
while(cal_error((temp=Jacobi_method(A, B, X)), X)>=er){
X=temp;
}
X=temp;
long endTime=System.nanoTime();
System.out.println("the solution vector of Jacobi_method is：");
for(int i=0;i<M;i++){
System.out.println(X[i]);
}
System.out.println("the running time of Jacobi_method is：");
System.out.println(endTime-startTime+"ns");
/*calculate the running time of direct_method*/
long startTime2=System.nanoTime();
X=cal_direct(A, B);
long endTime2=System.nanoTime();
System.out.println("the solution vector of direct_method is：");
for(int i=0;i<M;i++){
System.out.println(X[i]);
}
System.out.println("the running time of direct_method is：");
System.out.println(endTime2-startTime2+"ns");
}
}
Upvotes: 1
Views: 78
Answers (2)
Jonatan Cloutier
Reputation: 929
There is many reason, but the more plausible for me is that you encounter java hotspot runtime optimisation. In short, java application optimize them selves to be faster on code path occurring often. So when you invert both method the optimization isn't done exactly in the same way.
One way of testing (and only testing) your time after optimization was done is to run your code twice in a same application run, the only time to take into account is the second.
eg:
call method1
call method2
time call method1
time call method2
Upvotes: 0
eckes
Reputation: 10433
There can be a number of reasons. It is not completely clear which functions you tried to run how often, so I will give you just a few possible reasons:
one function might call a method more often and lead to its inlining. Then the second function can start with a inlined code.
one function could produce more garbage than the other, the second function will be delayed by GC.
some inlined code has a different branch prediction stats, which affects the other method
when running the test method only a small time without warming up, the measurement drowns in the noise.
Those (and other) reasons can be avoided with using a benchmarking framework which does isolation of the tests. Check out for example JMH.
Upvotes: 1
Related Questions
- Two methods implement same algorithm one is taking running time more than other in java
- Why does the first method call always take the longest?
- Performance difference in two equal methods
- Strange method invocation optimization issue
- Why do two consecutive calls to the same method yield different times for execution?
- Why does the execution timing of certain functions vary greatly?
- Considerable difference in Running time of thse two java codes
- Why is the performance for this Java code so inconsistent?
- Wrong time of method execution
- Java performance issue