Enable possibility to have a linear removeClonesX
As shown in flame graph below, the scaling of removeClonesX is pretty brutal:
Several solutions exist, such as the implementation of the Allen-like clone removal in linear time. However, due to the fact that X seeds coming from a single case are sorted in X, a break condition can be implemented early to only test neighbouring tracks. I am curious as to the effect on Pb-Pb timings.
- On Pb-Pb, timing of the seeding goes from 858780.434 to 427171.004 (51% gain) -> I will look for further improvement;
- Efficiency: on pp, +0.3% ghosts and +0.13% efficiency on Long.
- Efficiency: on Pb-Pb, increases a lot (2%), but ghosts too. Before:
SeedTrackChecker_1b1d5575 INFO **** Seed 1362115 tracks including 1306670 ghosts [95.93 %], Event average 40.99 % ****
SeedTrackChecker_1b1d5575 INFO 01_hasT : 41840 from 95739 [ 43.70 %] 24 clones [ 0.06 %], purity: 97.79 %, hitEff: 93.04 %
SeedTrackChecker_1b1d5575 INFO 02_long : 21243 from 41283 [ 51.46 %] 8 clones [ 0.04 %], purity: 98.23 %, hitEff: 93.87 %
SeedTrackChecker_1b1d5575 INFO 03_long_P>5GeV : 12630 from 23892 [ 52.86 %] 5 clones [ 0.04 %], purity: 98.18 %, hitEff: 94.54 %
SeedTrackChecker_1b1d5575 INFO 06_UT+T_strange : 3807 from 7558 [ 50.37 %] 3 clones [ 0.08 %], purity: 98.07 %, hitEff: 93.22 %
SeedTrackChecker_1b1d5575 INFO 07_UT+T_strange_P>5GeV : 1985 from 3856 [ 51.48 %] 2 clones [ 0.10 %], purity: 97.85 %, hitEff: 93.99 %
SeedTrackChecker_1b1d5575 INFO 08_noVelo+UT+T_strange : 2549 from 5118 [ 49.80 %] 3 clones [ 0.12 %], purity: 98.09 %, hitEff: 93.25 %
SeedTrackChecker_1b1d5575 INFO 09_noVelo+UT+T_strange_P>5GeV : 1409 from 2788 [ 50.54 %] 2 clones [ 0.14 %], purity: 97.88 %, hitEff: 93.94 %
SeedTrackChecker_1b1d5575 INFO 13_hasT_electrons : 6483 from 22378 [ 28.97 %] 5 clones [ 0.08 %], purity: 97.94 %, hitEff: 91.87 %
SeedTrackChecker_1b1d5575 INFO 14_long_electrons : 694 from 1272 [ 54.56 %] 0 clones [ 0.00 %], purity: 98.10 %, hitEff: 91.94 %
SeedTrackChecker_1b1d5575 INFO 16_long_electrons_P>5GeV : 247 from 441 [ 56.01 %] 0 clones [ 0.00 %], purity: 97.59 %, hitEff: 93.78 %After:
SeedTrackChecker_1b1d5575 INFO **** Seed 1966821 tracks including 1908316 ghosts [97.03 %], Event average 41.74 % ****
SeedTrackChecker_1b1d5575 INFO 01_hasT : 44010 from 95739 [ 45.97 %] 78 clones [ 0.18 %], purity: 97.52 %, hitEff: 92.46 %
SeedTrackChecker_1b1d5575 INFO 02_long : 22247 from 41283 [ 53.89 %] 31 clones [ 0.14 %], purity: 98.04 %, hitEff: 93.40 %
SeedTrackChecker_1b1d5575 INFO 03_long_P>5GeV : 13312 from 23892 [ 55.72 %] 17 clones [ 0.13 %], purity: 97.87 %, hitEff: 93.93 %
SeedTrackChecker_1b1d5575 INFO 06_UT+T_strange : 3990 from 7558 [ 52.79 %] 7 clones [ 0.18 %], purity: 97.84 %, hitEff: 92.68 %
SeedTrackChecker_1b1d5575 INFO 07_UT+T_strange_P>5GeV : 2098 from 3856 [ 54.41 %] 5 clones [ 0.24 %], purity: 97.43 %, hitEff: 93.12 %
SeedTrackChecker_1b1d5575 INFO 08_noVelo+UT+T_strange : 2685 from 5118 [ 52.46 %] 7 clones [ 0.26 %], purity: 97.76 %, hitEff: 92.53 %
SeedTrackChecker_1b1d5575 INFO 09_noVelo+UT+T_strange_P>5GeV : 1498 from 2788 [ 53.73 %] 5 clones [ 0.33 %], purity: 97.39 %, hitEff: 92.89 %
SeedTrackChecker_1b1d5575 INFO 13_hasT_electrons : 6838 from 22378 [ 30.56 %] 13 clones [ 0.19 %], purity: 97.72 %, hitEff: 91.29 %
SeedTrackChecker_1b1d5575 INFO 14_long_electrons : 730 from 1272 [ 57.39 %] 0 clones [ 0.00 %], purity: 97.76 %, hitEff: 91.47 %
SeedTrackChecker_1b1d5575 INFO 16_long_electrons_P>5GeV : 257 from 441 [ 58.28 %] 0 clones [ 0.00 %], purity: 97.31 %, hitEff: 93.49 %