cms-sw/cmssw — pull request #772 by makortel (2013-09-11 06:35:40+00:00)
Title: Performance improvement in KDTreeLinkerAlgo<T> 

The improvements come mainly from
* Reorganized data structure of KDTreeLinkerAlgo (more compact in Structure-of-Arrays style)
* The interface of KDTreeLinkerAlgo::search() had to be modified slightly, and now only the data items are returned (returning of coordinates was dropped)
* Decreased amount of branching and recursive function calls in KDTreeLinkerAlgo::recSearch()
* Use of std::nth_element() instead of hand-written Wirth algorithm in the kdtree building

The physics results of seeding should stay the same (tested in 612_SLHC6). Timing improvement in a standalone test of KDTreeLinkerAlgo::recSearch() was roughly 40 %. In CMSSW at very high pileup (140) the timing of seeding (SeedGeneratorFromRegionHitsEDProducer::produce()) improved by roughly 3 %.