Skip navigation

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 Comment

  1. I keep calling it a swiffer, too! I’ll probably use the swift more than I use the swiffer…don’t tell my mom! Click https://twitter.com/moooker1


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: