new Hough cluster search for the UV (stereo) hits in the SciFi Hybrid Seeding
This merge request includes several improvements to the SciFi hybrid seeding algorithm, particularly the step where UV (stereo) hits are added to the xz track candidates.
The new Hough cluster search is implemented in a generic template class. For each track candidate in the x-z projection, the y-z slopes corresponding to the hits from each of the 6 UV layers are collected in 6 separate histograms implemented as fixed-size arrays. The histograms are added together to form clusters. The largest clusters are promoted to candidate hits for the full track.
The code has also been reorganized, templating some methods and classes to avoid code repetition without affecting the performance.
The new algorithm was tested on a Monte Carlo sample (upgrade_DC19_01_Bd2KsteeMU) of 35k events with Moore. The physics performance are equivalent to the previous algorithm (see tables below with efficiency and ghost rates).
The code was also tested with the callgrind profiler. The new hybrid seeding algorithm results in -15% instruction fetch counts, with the Hough cluster search counting -40% instruction fetch.
Efficiency from master
SeedTrackChecker INFO Results SeedTrackChecker INFO **** Seed 3785456 tracks including 240976 ghosts [ 6.37 %], Event average 5.73 % **** SeedTrackChecker INFO 01_hasT : 2509335 from 3020640 [ 83.07 %] 366 clones [ 0.01 %], purity: 99.50 %, hitEff: 97.94 % SeedTrackChecker INFO 02_long : 1839150 from 1977324 [ 93.01 %] 159 clones [ 0.01 %], purity: 99.65 %, hitEff: 98.53 % SeedTrackChecker INFO 03_long>5GeV : 1313194 from 1368948 [ 95.93 %] 92 clones [ 0.01 %], purity: 99.65 %, hitEff: 99.09 % SeedTrackChecker INFO 04_long_fromB : 101294 from 107958 [ 93.83 %] 5 clones [ 0.00 %], purity: 99.71 %, hitEff: 98.81 % SeedTrackChecker INFO 05_long_fromB>5GeV : 78402 from 81750 [ 95.90 %] 4 clones [ 0.01 %], purity: 99.71 %, hitEff: 99.21 % SeedTrackChecker INFO 06_noVelo+UT+T : 269373 from 299637 [ 89.90 %] 34 clones [ 0.01 %], purity: 99.63 %, hitEff: 97.66 % SeedTrackChecker INFO 07_noVelo+UT+T>5GeV : 127490 from 133142 [ 95.75 %] 7 clones [ 0.01 %], purity: 99.64 %, hitEff: 98.91 % SeedTrackChecker INFO 08_noVelo+UT+T_strange : 98458 from 107262 [ 91.79 %] 10 clones [ 0.01 %], purity: 99.65 %, hitEff: 98.16 % SeedTrackChecker INFO 09_noVelo+UT+T_strange>5GeV : 58136 from 60598 [ 95.94 %] 2 clones [ 0.00 %], purity: 99.66 %, hitEff: 99.02 % SeedTrackChecker INFO 10_noVelo+noUT+T : 400812 from 743679 [ 53.90 %] 173 clones [ 0.04 %], purity: 98.74 %, hitEff: 95.39 % SeedTrackChecker INFO 11_noVelo+noUT+T>5GeV : 188883 from 239284 [ 78.94 %] 105 clones [ 0.06 %], purity: 98.50 %, hitEff: 96.51 % SeedTrackChecker INFO 12_noVelo+noUT+T_strange : 49208 from 63493 [ 77.50 %] 10 clones [ 0.02 %], purity: 99.24 %, hitEff: 97.29 % SeedTrackChecker INFO 13_noVelo+noUT+T>5GeV_strange : 33143 from 36646 [ 90.44 %] 6 clones [ 0.02 %], purity: 99.23 %, hitEff: 98.10 % SeedTrackChecker INFO 14_long_electrons : 187546 from 215333 [ 87.10 %] 17 clones [ 0.01 %], purity: 99.72 %, hitEff: 97.92 % SeedTrackChecker INFO 15_noVelo+UT+T_electrons : 209189 from 246648 [ 84.81 %] 33 clones [ 0.02 %], purity: 99.69 %, hitEff: 97.36 % SeedTrackChecker INFO 16_noVelo+noUT+T_electrons : 149147 from 533945 [ 27.93 %] 65 clones [ 0.04 %], purity: 99.24 %, hitEff: 96.48 %
Efficiency with new algorithm
SeedTrackChecker INFO Results SeedTrackChecker INFO **** Seed 3767476 tracks including 195001 ghosts [ 5.18 %], Event average 4.76 % **** SeedTrackChecker INFO 01_hasT : 2529299 from 3020640 [ 83.73 %] 101 clones [ 0.00 %], purity: 99.49 %, hitEff: 97.80 % SeedTrackChecker INFO 02_long : 1838689 from 1977324 [ 92.99 %] 41 clones [ 0.00 %], purity: 99.62 %, hitEff: 98.36 % SeedTrackChecker INFO 03_long>5GeV : 1311833 from 1368948 [ 95.83 %] 35 clones [ 0.00 %], purity: 99.61 %, hitEff: 98.92 % SeedTrackChecker INFO 04_long_fromB : 101372 from 107958 [ 93.90 %] 2 clones [ 0.00 %], purity: 99.68 %, hitEff: 98.63 % SeedTrackChecker INFO 05_long_fromB>5GeV : 78404 from 81750 [ 95.91 %] 1 clones [ 0.00 %], purity: 99.67 %, hitEff: 99.05 % SeedTrackChecker INFO 06_noVelo+UT+T : 270212 from 299637 [ 90.18 %] 12 clones [ 0.00 %], purity: 99.63 %, hitEff: 97.55 % SeedTrackChecker INFO 07_noVelo+UT+T>5GeV : 127746 from 133142 [ 95.95 %] 3 clones [ 0.00 %], purity: 99.63 %, hitEff: 98.82 % SeedTrackChecker INFO 08_noVelo+UT+T_strange : 98445 from 107262 [ 91.78 %] 3 clones [ 0.00 %], purity: 99.63 %, hitEff: 98.01 % SeedTrackChecker INFO 09_noVelo+UT+T_strange>5GeV : 58099 from 60598 [ 95.88 %] 1 clones [ 0.00 %], purity: 99.62 %, hitEff: 98.87 % SeedTrackChecker INFO 10_noVelo+noUT+T : 420398 from 743679 [ 56.53 %] 48 clones [ 0.01 %], purity: 98.83 %, hitEff: 95.49 % SeedTrackChecker INFO 11_noVelo+noUT+T>5GeV : 197584 from 239284 [ 82.57 %] 35 clones [ 0.02 %], purity: 98.64 %, hitEff: 96.83 % SeedTrackChecker INFO 12_noVelo+noUT+T_strange : 50021 from 63493 [ 78.78 %] 5 clones [ 0.01 %], purity: 99.25 %, hitEff: 97.25 % SeedTrackChecker INFO 13_noVelo+noUT+T>5GeV_strange : 33502 from 36646 [ 91.42 %] 3 clones [ 0.01 %], purity: 99.23 %, hitEff: 98.09 % SeedTrackChecker INFO 14_long_electrons : 187248 from 215333 [ 86.96 %] 3 clones [ 0.00 %], purity: 99.70 %, hitEff: 97.78 % SeedTrackChecker INFO 15_noVelo+UT+T_electrons : 208831 from 246648 [ 84.67 %] 10 clones [ 0.00 %], purity: 99.67 %, hitEff: 97.21 % SeedTrackChecker INFO 16_noVelo+noUT+T_electrons : 148969 from 533945 [ 27.90 %] 12 clones [ 0.01 %], purity: 99.28 %, hitEff: 96.42 %
I attach also the callgrind graphs for master and for the new algorithm, obatined running Moore on 100 events from the same MC sample.
Callgrind for master: total Ir = 1,776,909,692
Callgrind for new algorithm: total Ir = 1,513,821,530 (-15% compared to master)
