C/C++ Program illustrating Spatial Locality

  Spatial locality is the expectation of a Computer System that a particular program will use data from neighboring locations of already used data. C programming language uses a row major ordering to allocate array data. That means the data is stored row wise in contiguous memory locations. So spatial locality tells us to access data in a row wise order.  

Consider the two loops given below.

// LOOP 1
   for(i =0; i < 700; i++)
   {
      for(j=0; j< 700; j++)
      {
            a[ i ][ j ]=1;     // Here elements are accessed row wise.
       }
    }

// LOOP 2
   for(i =0; i < 700; i++)
  {
      for(j=0; j< 700; j++)
      {
            a[ j ][ i ]=1;     // Here elements are accessed row wise.
       }
    }

 Which loop will take more time to execute? Even though both the loops sets exactly 490000 locations to 1, the first loop is much more faster than the second loop. Reason is spatial locality and row major ordering of C programs. If you were executing the same algorithm in MATLAB the second loop will execute faster since MATLAB follows a column major ordering for storing array data.

The Figure Given Below Shows the Output of the C Program

Click here to download the C Program illustrating the principle of Spatial Locality. 

Click here to download the C++ Program illustrating the principle of Spatial Locality.