CODEWITHSUNDEEP
javaperformanceloops
Mark.zxx
Mark.zxx

Reputation: 31

Loop twice but cost same time in JAVA

I have a loop like this:

  double[][] ED = new double[n][m];
  for(int k = 0; k < 20000; k++)
   for (int i = 0; i < 200; i++) 
    for (int j = 0; j < 200; j++)
     ED[i][j] = dis(qx[k][i], qy[k][i], dx[k][j], dy[k][j]);

"dis" is a function to calculate the distance between (x1,y1) and (x2,y2). Don't mind it. The problem is when I add another boolean assignment in the loop just like this:

  double[][] ED = new double[n][m];
  boolean[][] bool = new boolean[n][m];
   for(int k = 0; k < 20000; k++)
   for (int i = 0; i < 200; i++) 
    for (int j = 0; j < 200; j++)
     {
       ED[i][j] = dis(qx[k][i], qy[k][i], dx[k][j], dy[k][j]);
       bool[i][j] = ED[i][j] > 5000;
     }

The new loop cost 1.5 time over the first one. I think it cost too much. For testing, I break 2 assignment into 2 loop.The strange thing happens, two cost of time are same. Sometimes, code 3 cost less time than code 2

    double[][] ED = new double[n][m];
    boolean[][] bool = new boolean[n][m];
    for(int k = 0; k < 20000; k++)
    {
      for (int i = 0; i < 200; i++) 
       for (int j = 0; j < 200; j++)
        {
         ED[i][j] = dis(qx[k][i], qy[k][i], dx[k][j], dy[k][j]);
        }
      for (int i = 0; i < 200; i++) 
       for (int j = 0; j < 200; j++)
        {
         bool[i][j] = ED[i][j] > 5000;
        }
    }

My aim is use as less time too calculate bool[i][j], how should I do.

Upvotes: 2

Views: 188

Answers (1)

Bartosz Bilicki
Bartosz Bilicki

Reputation: 13235

Introducing new, big array bool[][] may have more impact than it seems. When only single arrayED[i][j] is used, you put less stress on L1 processor cache. With second array, you have twice as much data, therefore cache will be invalidated more often.

Could you try, instead of using two arrays (bool and arrayED) use single array that holds both double and boolean? There will be significant overhead for array of Objects, but (maybe) compiler will be smart enough to destructure the Object.

With single array, you will have better data locality.

Also, as suggested in comments make sure you do your microbenchmarking properly. Use http://openjdk.java.net/projects/code-tools/jmh/ and read its documentation how to use it correctly.

Another soltution that would help on multicore system is to use parallel processing. You may create ThreadPoolExecutor (with pool size equal to number of cores you have) then submit each opearation as task to the executor. Operation may be inner-most loop (with counter j) or even two inner-most loops (with counters i and j). There will be some overhead for coordinating the work but execution time should be much faster if you have 4 or 8 cores.

Yet another idea is to change input data structure. Instead of operating on 4 two-dimensional arrays (qx,qy,dx,dy) could you have single array? it may make dis function faster.

Upvotes: 1

Related Questions