TreeSplicer is a Java source to source transformation framework to enhance temporal locality for repeated tree traversals.

It utilizes two novel concepts:

TreeSplicer is a transformation framework, which can automatically apply point blocking, traversal splicing or both combined, and use autotuning techniques to choose good transformation parameters (e.g., block size, splice depth). It can automatically transform tree traversal programs to deliver speedups of up to 9x, just from better locality!

TreeSplicer was built on top of JastAdd. We provide our customized JastAdd grammar files, and JastAdd generated AST files which implement TreeSplicer. The JastAdd framework itself is available from the JastAdd site. We provide 5 benchmarks to demonstrate the efficacy of TreeSplicer. The benchmarks are:

  • Barnes-Hut
  • Point Correlation
  • Nearest Neighbor
  • k-Nearest Neighbor
  • Ball Tree

The ball tree benchmark is adapted from the WEKA data mining software, and the other benchmarks are adapted from the Lonestar benchmark suite.

If you find this software useful in academic work, please cite the following publications:

Last updated: June 12, 2013