Java Loop Unrolling.

While refactoring code for a Java Barnes-hut simulation, i came across an explicit unrolling of loops. At a high level, the bodies are stored in an Oct-tree and so each cluster would have eight neighbors for each of the subspace in three dimensions. Once the tree has been constructed, the nodes are compacted. This means, since the neighbors for the Oct-tree are stored in an array, that any non-existent neighbors are removed so a pass over all the neighbors can break on first non-existent neighbor. In order to compute the force acting on each body, we recursively iterate over the tree. This means at each node of the Oct-tree, we have to iterate over all the neighbors, and that means going up to 8 nodes. The simplest way would be to have a loop go over all the bodies and breaking on the first non-existent neighbor. Hence, something like :

GNode child = null;
for(int i=0;i<8;i++){
   child = octree.getNeighbor(nn, i, MethodFlag.NONE);
   if(child==null)
      break;
   RecurseForce(leaf, child, dsq, epssq);
}

  The other change made was to encapsulate all the coordinate referencing code into a point class. So, there are four variants :

  1. Original (without point3, and with explicit loop unrolling)
  2. Point3 ( with point3 class, with explicit loop unrolling)
  3. For (without point3 class, without explicit loop unrolling)
  4. Naive (with point3 class, without explicit loop unrolling)

As a developer, you would write the Naive version. So, comparing the performance of the four variants, here is what we get.

Barnes-Hut variants plot

BH Runtimes.

Advertisements

One thought on “Java Loop Unrolling.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s