Speed up NAM merging a bit

[marcelm]

merge_hits_into_nams() has two nested for loops that iterate over a single vector that contains both forward and reverse hits. In the inner loop, there’s a check to ensure that forward and reverse hits are never merged into NAMs.

We can instead keep forward and reverse hits in two different hash tables and work on them separately. This reduces the number of comparisons done in the inner loop. Interestingly, that change by itself doesn’t really reduce runtime. But what does reduce runtime is the subsequent commit that makes the Hit struct smaller by removing its is_rc attribute, which we no longer need.

Measurements on 100 bp single-end reads:

Reference	speedup
drosophila	~2%
maize	~9%
CHM13	~7%
rye	~1%

I’ll post how accuracy changes tomorrow (so far, it looks as if there’s nearly no change).

[ksahlin]

Wow, neat. I guess removing the additional bool from the otherwise nicely packed 4x32-bit Hit struct could lead to better memory alignment.

[marcelm]

Here’s how accuracy changes on single-end reads.

dataset	f6b6208	91f2223	difference
drosophila-50	82.5118	82.5175	+0.0057
drosophila-75	87.9944	87.9797	-0.0147
drosophila-100	89.2585	89.2626	+0.0041
drosophila-150	90.9438	90.937	-0.0068
drosophila-200	91.9501	91.9463	-0.0038
drosophila-300	93.2169	93.2153	-0.0016
drosophila-500	94.5768	94.5722	-0.0046
maize-50	47.4174	47.4622	+0.0448
maize-75	61.9111	61.8938	-0.0173
maize-100	70.5	70.5148	+0.0148
maize-150	81.1708	81.1606	-0.0102
maize-200	86.701	86.7001	-0.0009
maize-300	91.8729	91.8516	-0.0213
maize-500	95.4025	95.3796	-0.0229
CHM13-50	81.691	81.7231	+0.0321
CHM13-75	88.922	88.9376	+0.0156
CHM13-100	90.6392	90.6468	+0.0076
CHM13-150	92.399	92.4066	+0.0076
CHM13-200	93.2258	93.221	-0.0048
CHM13-300	94.1503	94.1508	+0.0005
CHM13-500	95.0598	95.0531	-0.0067
rye-50	44.6869	44.7328	+0.0459
rye-75	60.221	60.236	+0.0150
rye-100	69.3358	69.3509	+0.0151
rye-150	80.4388	80.4219	-0.0169
rye-200	85.9181	85.9117	-0.0064
rye-300	90.523	90.5181	-0.0049
rye-500	93.507	93.5172	+0.0102

Average difference: +0.0027

Wow, neat. I guess removing the additional bool from the otherwise nicely packed 4x32-bit Hit struct could lead to better memory alignment.

Without the bool, the struct fits into two 64-bit registers, which could be one reason for the speedup (more registers available for other things). And the cache can also hold more Hits.

Memory alignment is maybe not quite the right term for this as "unaligned access" has a somewhat different meaning. It refers to reading from a memory location that is not a multiple of the word size (for example, reading a 64 bit value from address 0x003 or so). Some CPUs don’t support this at all and would crash; Intel CPUs support this, but are slower at it.

Structs in C are laid out in memory such that there is no unaligned memory access. Here, although the bool only needs one byte, the struct is padded with three extra (unused bytes) so that it takes up 20 bytes. Removing the bool attribute thus saves 4 bytes.

Sorry if the above was clear already.

[ksahlin]

Great that that accuracy seems to be stable (or even improve a bit), although it is unclear to me why accuracy would change at all with your changes. Is it something 'random' like changed traversal order or the NAMs? Or is it something more systematic?

Do you see similar speed improvements for other read lengths?

Sorry if the above was clear already.

No, it was a good explanation. 'Structure padding to avoid unaligned access' might be a better explanation then, if I understood you correctly..

[marcelm]

Great that that accuracy seems to be stable (or even improve a bit), although it is unclear to me why accuracy would change at all with your changes. Is it something 'random' like changed traversal order or the NAMs? Or is it something more systematic?

It’s the order of the produced NAMs. I get similar variations in accuracy when I shuffle the vector of NAMs (using std::random_shuffle) before returning it from the function.

Do you see similar speed improvements for other read lengths?

I tested 500 bp reads over night and there was also a speedup, but not as large (more like 1-3%).

Sorry if the above was clear already.

No, it was a good explanation. 'Structure padding to avoid unaligned access' might be a better explanation then, if I understood you correctly..

Yes!

[ksahlin]

I see. So I guess this PR is ready to merge then? Approved on my end.

[marcelm]

Yes, it’s ready!