samtools / htslib

C library for high-throughput sequencing data formats
Other
789 stars 447 forks source link

Make reg2bins, reg2intervals faster on whole-chromosome queries #1596

Closed daviesrob closed 1 year ago

daviesrob commented 1 year ago

It's faster to iterate through the index hash table when requesting whole chromosomes, compared to the old behaviour of iterating through all the bins that could exist and looking them up in the hash table to see if they're present. The latter method works better for narrow ranges though, so we choose which to use based on the number of bins covering the range compared to the number in the index.

The speed-up is most notable on CSI-indexed BED files, which since #1506 have used eight-level indexes. Iterating through all the unused bins took around 0.2s in my testing. With this fix applied, the same query can be done in a few milliseconds.