gak/gravit — Issue #47: frame-ot performance improvements
Author: FrMo
Created: 2012-01-25 16:25:48+00:00
State: open
Labels: feature

frame-ot.c (oct-tree "barnes-hutt" particle interaction calculations) is currently disabled, because the direct particle-particle implementation (frame-pp.c) is faster in many cases.

The implementation could be optimized in several places:

* while building the tree, otBranchNodeCorner calls otGetParticleInBox for each new node. otGetParticleInBox scans all particles to find the ones that are inside the box. ==> O(n log(n)) * O(n) --> O(n^2 log(n))
The tree construction could be optimized by introducing a function that takes a single particle, and inserts it into the tree (adjusting all "upper level" nodes).

* Try to speed up some operations using vectors (SSE).

* Force computation could make better use of the tree hierarchy.
(need to compare our approach to the original barnes-hutt treecode)