Friday, May 8, 2009

Overhead of using Multi-dimensional arrays in Java

As discussed many times in the related literature, the Java multidimensional arrays introduce a good amount of overhead because of the way they are stored in the memory. The purpose of this post is to quantify this performance overhead.

Let's first look at the matrix multiplication implementation that uses the multidimensional arrays (the 2D version).



Now let's look at the same code but implemented using single dimension array. Basically the two dimensional array is mapped onto the single dimension array (the 1D version).



Now put some performance results:

 
aamir@barq:~/tmp> java MultidimMatrix
time => 19.821604495
aamir@barq:~/tmp> java Matrix
time -> 11.928243662


The 1D code is 1.66 times faster than the 2D code.

1 comment:

  1. this's my code in MPJ with matrix 1D

    import mpi.MPI;


    public class MatrixMul
    {
    public static final int N = 8;

    public static void main (String args[])
    {
    int mc;
    int []a = new int [N*N];
    int []b = new int [N*N];
    int []c = new int [N*N];

    MPI.Init(args);
    int rank = MPI.COMM_WORLD.Rank();
    int size = MPI.COMM_WORLD.Size();

    if(rank == 0)
    {
    for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
    {
    //a[i*N+j] = i*N+j;
    a[i*N+j] = 1;
    //b[i*N+j] = (i==j)?1:0;
    b[i*N+j] = 1;
    }

    System.out.println("Matrix A");
    for(int i=0;i<N;i++)
    {
    for(int j=0;j<N;j++)
    System.out.print(a[i*N+j]+" ");
    System.out.println("");
    }

    System.out.println("Matrix B");
    for(int i=0;i<N;i++)
    {
    for(int j=0;j<N;j++)
    System.out.print(b[i*N+j]+" ");
    System.out.println("");
    }
    }

    mc=N/size;
    int[] ai=new int[mc*N];
    int[] bi=new int[N*N];
    int[] ci=new int[mc*N];
    //send matrix a from main process to other process
    if(rank==0)
    {
    for(int i = 0; i < mc; i++)
    for(int j = 0; j < N; j++)
    {
    ai[i*N+j]=a[i*N+j];
    }
    for(int i=1;i<size;i++)
    {
    MPI.COMM_WORLD.Send(a, i*mc*N, mc*N, MPI.INT, i, i);
    }
    }
    else
    {
    MPI.COMM_WORLD.Recv(ai, 0, mc*N, MPI.INT, 0, rank);
    }
    //send matrix b from main process to other process
    if(rank==0)
    {
    for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
    {
    bi[i*N+j]=b[i*N+j];
    }
    for(int i=1;i<size;i++)
    {
    MPI.COMM_WORLD.Send(b, 0, N*N, MPI.INT, i, i);
    }
    }
    else
    {
    MPI.COMM_WORLD.Recv(bi, 0, N*N, MPI.INT, 0, rank);
    }
    //calculator
    for (int i = 0 ; i < mc ; i++ )
    for (int j = 0 ; j < N ; j++ )
    {
    ci[i*N+j]=0;
    for(int k=0;k<N;k++)
    {
    ci[i*N+j]+=ai[i*N+k]*bi[k*N+j];
    }
    }
    //send result from other process to main process
    if(rank!=0)
    {
    MPI.COMM_WORLD.Send(ci, 0, mc*N, MPI.INT, 0, rank);
    }
    else
    {
    for(int i = 0; i < mc; i++)
    for(int j = 0; j < N; j++)
    c[i*N+j]=ci[i*N+j];
    for(int i=1;i<size;i++)
    MPI.COMM_WORLD.Recv(c, i*mc*N, mc*N, MPI.INT, i, i);
    }
    //show result
    if(rank==0)
    {
    System.out.println("Ma tran C:");
    for(int i=0;i<N;i++)
    {
    for(int j=0;j<N;j++)
    System.out.print(c[i*N+j]+" ");
    System.out.println("");
    }
    }
    MPI.Finalize() ;
    }
    }

    ReplyDelete