search

iqbal-lab-org / gramtools

Genome inference from a population reference graph
MIT License
92 stars 15 forks source link

`left_markers_search` instruction bottleneck #141

Closed bricoletc closed 5 years ago

bricoletc commented 5 years ago

From profiling the cache instruction calls of quasimap in a7db53abc75b4ceb2d347337b1d3b6ec52ebe2a8 we see the following:

callgrind_a7db53

>50% of all instructions are spent in single function left_markers_search

Profiling using valgrind callgrind.

bricoletc commented 5 years ago

Here is the callgraph with %of all instructions for the same dataset (TB simulated dataset), having modified left_markers_search:

perf_left_markers_tbdataset_callgrind

We go down from a total of 1.94 trillion instructions to a total of 0.94 trillion instructions. This speeds up backward search, affecting both build and quasimap.

The speedup was independently confirmed by quasimap of some plasmodium reads against the pf3k/DBLMSP1+2 prg.

iqbal-lab commented 5 years ago

Awesome