Cell lists pair search without "if"

Cell lists pair search without if #

Description #

So far, the speedup demonstrated from the fixed-cutoff cell-lists pair search algorithm is pretty great. One last change we can make to improve things, is to remove any if statements when searching adjacent cells. if’s are undesirable because they introduce branching and harms performance. I’ve found that it can be beneficial to remove if statements, even if it means a bit more computation/assignments are performed.

The below code is the update_pair_list function from the code shown previously, except that the function is modified to remove the if statement used to check whether the two pairs are within the designated cutoff distance.

The if statement is removed by modifying the pair_i and pair_j arrays to start from index 0. No matter what, pair_i and pair_j are updated at the given npairs index. By using the merge Fortran intrinsic function, we only increment npairs when the calculated distance is less than the cutoff. Note that the increment of npairs now occurs after the index assignments.

The speedup observed with -O3 compilation is about 1.2x over the previous version.

Code (Fortran) #

Use the same sort.cpp code as previously and update the update_pair_list function as per the code below. Save the code as cll4.cpp and compile with:

g++ -c sort.cpp
gfortran -o cll4.x cll4.F90 sort.o -lstdc++

   !---------------------------------------------------------------------------
   subroutine update_pair_list(cutoff, jstart, jend, i, x, npairs, pair_i, pair_j)
      ! subroutine to loop over sequential grid cells and check if j point is
      ! within a given i point

      implicit none
      integer, intent(in):: jstart, jend, i
      real(f), intent(in):: cutoff, x(:, :)
      integer, intent(inout):: npairs, pair_i(0:), pair_j(0:)
      integer:: j
      real(f):: r2

      do j = jstart, jend
         r2 = sum((x(:, i) - x(:, j))**2)
         ! if (r2 <= cutoff*cutoff) then
            ! npairs = npairs + 1
            pair_i(npairs) = i
            pair_j(npairs) = j
            npairs = npairs + merge(1, 0, r2 <= cutoff*cutoff)
         ! end if
      end do

   end subroutine update_pair_list