seed cleaning in eta-phi bins

[leonardogiannini]

The PR introduces eta-phi bins in the seed cleaning function. The cleaning is done comparing only seeds close-by in eta and phi. The bins are sorted to speed up the navigation. All technical aspects of the code are in mkfit/binnor.h

the PR doesn't change the physics -> MTV comparison at http://uaf-10.t2.ucsd.edu/~legianni/compare-binnedSC/plots-compareMTV/ (see oob and initial, high pt triplet, detached quad and triplet)

the seed cleaning is faster everywhere, as shown by the plot of the speed-up vs n of initial seeds, except for cases with very low number of seeds, where the time spent is comparable.

[srlantz]

@leonardogiannini - It looks like you are plotting t_new/t_orig, whereas speedup is defined as t_orig/t_new? Also I think the trend would be clearer if you plotted speedup vs. number of seeds, rather than the other way around, and the meanings of the colors in the legend are undefined... the point you are making about better timing performance is not lost on me (I hope), but I am just thinking ahead, in case we would ever want to present this in a conference paper or something.

[srlantz]

Also, a combined plot of time vs. number of seeds N for the old way, and for the new binned algorithm, would be interesting. Time must scale like N^2 in the old way; how close is the scaling to N--or perhaps N log(N)--in the new way?

[leonardogiannini]

I am adding plots of the old and new time for seed cleaning (vs #seeds) and the speed-up, as suggested by @srlantz Hopefully, these plots are clearer.

• OLD SC T
• NEW SC T
• SPEED UP

[mmasciov]

For history, let me highlight that speedup of seed cleaning appears to differ for pixel triplet and pixel quadruplet seeds: speedup is larger for triplets. This may be due to combinatorics that makes the density of triplet seeds higher wrt. quadruplets, and this may be affecting the original algorithm more as the looping is not restricted to specific bins (?).

[mmasciov]

Closing, as superseded by cms-sw/cmssw#37122.