Speed up fai_retrieve() by reading whole lines at once#1799
Merged
Conversation
Contributor
|
I thought about this when doing my trivial edit before, but for some reason was misremembering my code. I used to use code that dealt with the EMBL sequence formats which had blocks of text with spacing in them (eg a white space every 10 chars for human readability when counting) and so discounted whole line reads as too fiddly. However it doesn't take much thinking to realise this isn't compatible with the fai index format and it simply can't work for random access (although it is incorrectly parseable with Thanks for the update. It's a significant speed gain. I don' t know how much this actually impacts on real world pipelines, but I'm sure there are a few pathological cases out there. |
Because fai_retrieve() is given only well-formatted input containing
lines of the same length, it already knows exactly where the base and
non-graphic characters are. So in general the interval to be read will
look like
......ATGCAT (read last six bases and line terminator)
ATGCATGCATGC (read complete line including line terminator)
ATGCATGCATGC (read complete line including line terminator)
ATGC........ (read first four base characters)
and can be read a line at a time instead of a character at a time,
with special handling for the partial first and last lines, and
discarding the terminator characters at the end of each line read.
Member
Author
Hilariously that could work with faidx if the file has Unix line terminators; e.g. If this was indexed as blen 10 len 11, faidx would retrieve the right bases without trouble! I thought this would Just Work, but unfortunately faidx indexing looks for \n and \r specifically rather than |
gpertea
added a commit
to gpertea/htslib
that referenced
this pull request
Mar 17, 2025
Notice: this is the last SAMtools / HTSlib release where CRAM 3.0
will be the default CRAM version. From the next we will change to
CRAM 3.1 unless the version is explicitly specified, for example
using "samtools view -O cram,version=3.0".
Updates
-------
* Extend annot-tsv with several new command line options.
--delim permits use of other delimiters.
--headers for selection of other header formats.
--no-header-idx to suppress column index numbers in header.
Also removed -h as it is now short for --headers. Note --help
still works. (PR samtools#1779)
* Allow annot-tsv -a to rename annotations. (PR samtools#1709)
* Extend annot-tsv --overlap to be able to specify the overlap
fraction separately for source and target. (PR samtools#1811)
* Added new APIs to facilitate low-level CRAM container
manipulations, used by the new "samtools cat" region
filtering code. Functions are:
cram_container_get_coords()
cram_filter_container()
cram_index_extents()
cram_container_num2offset()
cram_container_offset2num()
cram_num_containers()
cram_num_containers_between()
Also improved cram_index_query() to cope with HTS_IDX_NOCOOR
regions. (PR samtools#1771)
* Bgzip now retains file modification and access times when
compressing and decompressing. (PR samtools#1727, fixes samtools#1718.
Requested by Gert Hulselmans.)
* Use FNV1a for string hashing in khash. The old algorithm was
particularly weak with base-64 style strings and lead to a large
number of collisions. (PR samtools#1806. Fixes samtools/samtools#2066,
reported by Hans-Joachim Ruscheweyh)
* Improve the speed of the nibble2base() function on Intel (PR samtools#1667,
PR samtools#1764, PR samtools#1786, PR samtools#1802, thanks to Ruben Vorderman) and ARM
(PR samtools#1795, thanks to John Marshall).
* bgzf_getline() will now warn if it encounters UTF-16 data. (PR
samtools#1487, thanks to John Marshall)
* Speed up bgzf_read(). While this does not reduce CPU
significantly, it does increase the maximum parallelism
available permitting 10-15% faster decoding. (PR samtools#1772, PR
samtools#1800, Issue samtools#1798)
* Speed up faidx by use of better isgraph methods (PR samtools#1797) and
whole-line reading (PR samtools#1799, thanks to John Marshall).
* Speed up kputll() function, speeding up BAM -> SAM conversion by
about 5% and also samtools depth. (PR samtools#1805)
* Added more example code, covering fasta/fastq indexing, tabix
indexing and use of the thread pool. (PR samtools#1666)
Build Changes
-------------
* Code warning fixes for pedantic compilers (PR samtools#1777) and avoid some
undefined behaviour (PR samtools#1810, PR samtools#1816, PR samtools#1828).
* Windows based CI has been migrated from AppVeyor to GitHub Actions.
(PR samtools#1796, PR samtools#1803, PR samtools#1808)
* Miscellaneous minor build infrastructure and code fixes. (PR samtools#1807,
PR samtools#1829, both thanks to John Marshall)
* Updated htscodecs submodule to version 1.6.1 (PR samtools#1828)
* Fixed an awk script in the Makefile that only worked with gawk. (PR
samtools#1831)
Bug fixes
---------
* Fix small OSS-Fuzz reported issues with CRAM encoding and long
CIGARS and/or illegal positions. (PR samtools#1775, PR samtools#1801, PR samtools#1817)
* Fix issues with on-the-fly indexing of VCF/BCF (bcftools
--write-index) when not using multiple threads. (PR samtools#1837.
Fixes samtools/bcftools#2267, reported by Giulio Genovese)
* Stricter limits on POS / MPOS / TLEN in sam_parse1(). This fixes a
signed overflow reported by OSS-Fuzz and should help prevent other
as-yet undetected bugs. (PR samtools#1812)
* Check that the underlying file open worked for preload: URLs.
Fixes a NULL pointer dereference reported by OSS-Fuzz. (PR samtools#1821)
* Fix an infinite loop in hts_itr_query() when given extremely large
positions which cause integer overflow. Also adds hts_bin_maxpos()
and hts_idx_maxpos() functions. (PR samtools#1774, thanks to John Marshall
and reported by Jesus Alberto Munoz Mesa)
* Fix an out of bounds read in hts_itr_multi_next() when switching
chromosomes. This bug is present in releases 1.11 to 1.20. (PR
samtools#1788. Fixes samtools/samtools#2063, reported by acorvelo)
* Work around parsing problems with colons in CHROM names. Fixes
samtools/bcftools#2139. (PR samtools#1781, John Marshall / James Bonfield)
* Correct the CPU detection for Mac OS X 10.7. cpuid is used by
htscodecs (see samtools/htscodecs#116), and the corresponding
changes in htslib are PR samtools#1785. Reported by Ryan Carsten Schmidt.
* Make BAM zero-length intervals work the same as CRAM; permitted
and returning overlapping records. (PR samtools#1787. Fixes
samtools/samtools#2060, reported by acorvelo)
* Replace assert() with abort() in BCF synced reader. This is not an
ideal solution, but it gives consistent behaviour when compiling
with or without NDEBUG. (PR samtools#1791, thanks to Martin Pollard)
* Fixed failure to change the write block size on compressed SAM or
VCF files due to an internal type confusion. (PR samtools#1826)
* Fixed an out-of-bounds read in cram_codec_iter_next() (PR samtools#1832)
diekhans
added a commit
to diekhans/htslib
that referenced
this pull request
May 27, 2025
htslib release 1.21:
The primary user-visible changes in this release are updates to
the annot-tsv tool and some speed improvements. Full details of
other changes and bugs fixed are below.
Notice: this is the last SAMtools / HTSlib release where CRAM 3.0
will be the default CRAM version. From the next we will change to
CRAM 3.1 unless the version is explicitly specified, for example
using "samtools view -O cram,version=3.0".
Updates
-------
* Extend annot-tsv with several new command line options.
--delim permits use of other delimiters.
--headers for selection of other header formats.
--no-header-idx to suppress column index numbers in header.
Also removed -h as it is now short for --headers. Note --help
still works. (PR samtools#1779)
* Allow annot-tsv -a to rename annotations. (PR samtools#1709)
* Extend annot-tsv --overlap to be able to specify the overlap
fraction separately for source and target. (PR samtools#1811)
* Added new APIs to facilitate low-level CRAM container
manipulations, used by the new "samtools cat" region
filtering code. Functions are:
cram_container_get_coords()
cram_filter_container()
cram_index_extents()
cram_container_num2offset()
cram_container_offset2num()
cram_num_containers()
cram_num_containers_between()
Also improved cram_index_query() to cope with HTS_IDX_NOCOOR
regions. (PR samtools#1771)
* Bgzip now retains file modification and access times when
compressing and decompressing. (PR samtools#1727, fixes samtools#1718.
Requested by Gert Hulselmans.)
* Use FNV1a for string hashing in khash. The old algorithm was
particularly weak with base-64 style strings and lead to a large
number of collisions. (PR samtools#1806. Fixes samtools/samtools#2066,
reported by Hans-Joachim Ruscheweyh)
* Improve the speed of the nibble2base() function on Intel (PR samtools#1667,
PR samtools#1764, PR samtools#1786, PR samtools#1802, thanks to Ruben Vorderman) and ARM
(PR samtools#1795, thanks to John Marshall).
* bgzf_getline() will now warn if it encounters UTF-16 data. (PR
samtools#1487, thanks to John Marshall)
* Speed up bgzf_read(). While this does not reduce CPU
significantly, it does increase the maximum parallelism
available permitting 10-15% faster decoding. (PR samtools#1772, PR
samtools#1800, Issue samtools#1798)
* Speed up faidx by use of better isgraph methods (PR samtools#1797) and
whole-line reading (PR samtools#1799, thanks to John Marshall).
* Speed up kputll() function, speeding up BAM -> SAM conversion by
about 5% and also samtools depth. (PR samtools#1805)
* Added more example code, covering fasta/fastq indexing, tabix
indexing and use of the thread pool. (PR samtools#1666)
Build Changes
-------------
* Code warning fixes for pedantic compilers (PR samtools#1777) and avoid some
undefined behaviour (PR samtools#1810, PR samtools#1816, PR samtools#1828).
* Windows based CI has been migrated from AppVeyor to GitHub Actions.
(PR samtools#1796, PR samtools#1803, PR samtools#1808)
* Miscellaneous minor build infrastructure and code fixes. (PR samtools#1807,
PR samtools#1829, both thanks to John Marshall)
* Updated htscodecs submodule to version 1.6.1 (PR samtools#1828)
* Fixed an awk script in the Makefile that only worked with gawk. (PR
samtools#1831)
Bug fixes
---------
* Fix small OSS-Fuzz reported issues with CRAM encoding and long
CIGARS and/or illegal positions. (PR samtools#1775, PR samtools#1801, PR samtools#1817)
* Fix issues with on-the-fly indexing of VCF/BCF (bcftools
--write-index) when not using multiple threads. (PR samtools#1837.
Fixes samtools/bcftools#2267, reported by Giulio Genovese)
* Stricter limits on POS / MPOS / TLEN in sam_parse1(). This fixes a
signed overflow reported by OSS-Fuzz and should help prevent other
as-yet undetected bugs. (PR samtools#1812)
* Check that the underlying file open worked for preload: URLs.
Fixes a NULL pointer dereference reported by OSS-Fuzz. (PR samtools#1821)
* Fix an infinite loop in hts_itr_query() when given extremely large
positions which cause integer overflow. Also adds hts_bin_maxpos()
and hts_idx_maxpos() functions. (PR samtools#1774, thanks to John Marshall
and reported by Jesus Alberto Munoz Mesa)
* Fix an out of bounds read in hts_itr_multi_next() when switching
chromosomes. This bug is present in releases 1.11 to 1.20. (PR
samtools#1788. Fixes samtools/samtools#2063, reported by acorvelo)
* Work around parsing problems with colons in CHROM names. Fixes
samtools/bcftools#2139. (PR samtools#1781, John Marshall / James Bonfield)
* Correct the CPU detection for Mac OS X 10.7. cpuid is used by
htscodecs (see samtools/htscodecs#116), and the corresponding
changes in htslib are PR samtools#1785. Reported by Ryan Carsten Schmidt.
* Make BAM zero-length intervals work the same as CRAM; permitted
and returning overlapping records. (PR samtools#1787. Fixes
samtools/samtools#2060, reported by acorvelo)
* Replace assert() with abort() in BCF synced reader. This is not an
ideal solution, but it gives consistent behaviour when compiling
with or without NDEBUG. (PR samtools#1791, thanks to Martin Pollard)
* Fixed failure to change the write block size on compressed SAM or
VCF files due to an internal type confusion. (PR samtools#1826)
* Fixed an out-of-bounds read in cram_codec_iter_next() (PR samtools#1832)
# -----BEGIN PGP SIGNATURE-----
#
# iQJJBAABCgAzFiEEaGn1wQ1nqxSLDC2XHsvluhXGTMwFAmbjBlMVHHJtZCtnaXRA
# c2FuZ2VyLmFjLnVrAAoJEB7L5boVxkzMgb0P/3AAxkJNLGK8Q1pBBo+in7KzwBOc
# /nRfvReki47r4+i1ev98abEF/+XZoYSS8ZkiJH8JMkLCclb1ch2fDQTIL/sjJwrU
# MfhYx6oHhzLUOjpG24m390wlvlkEsg5S69jbgImWxLQ1n4ZcSuZGumiwPx5274w5
# 3R/K9vIXtuSF9DTD/jrTgoZeBiN+B4XefAJqHLSo4/XzDo7DNMSZryNGFpHdyKcB
# oEfEXX45vJLgzA3Fxo3LqNpC8UTDO5C9u9Uup+hCLN7RTBjV5Fu0UxcwWTSPqfiC
# Jroi2FhxNPlDkRL3jraI8LrB3Cqb0G/31OU+cryasrqYnfJrl0e/MyXiRSa0sg25
# uHHWVyyC4JR7uBfUCppTVf76iajbkIVpHgHLZS1heGwM4PCL+AalvsIgGcvLXcBs
# g/AwZLoXzao+pbzg8hzN1JuLB5hHcrHp6TsQ6JbTTrWaLeAL3s/+eQ4+d+Np2iUn
# v8TMg6onu1HiNgVMQcFXSLC2Q51rB+lD6AA3eusKjcQsaxyk+U7SLCx3OhbvxGsd
# SjxQWP1W+WW//e9nm5f4CTSSf1PHoDMyR/kVEc3qwEWJslri68RyB69HrDIVzrWT
# 3gKAKJYafi5ssFHsKTsCngESpDsTg3aQV1AGOQPLN/TIjyYDTUOL+/HylRs3k9XN
# KOGO5yggx+yqeL3w
# =lHVl
# -----END PGP SIGNATURE-----
# gpg: Signature made Thu 12 Sep 2024 08:18:43 AM PDT
# gpg: using RSA key 6869F5C10D67AB148B0C2D971ECBE5BA15C64CCC
# gpg: issuer "rmd+git@sanger.ac.uk"
# gpg: Can't check signature: No public key
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
While looking around for functions that could benefit from SIMD techniques a few weeks ago, I looked at
fai_retrieve()'s search for (uncommon) non-graphic characters. However I soon realised that it already knows exactly where these characters are, so doesn't need to search or check for them at all!Because
fai_retrieve()is given only well-formatted input containing lines of the same length, it already knows exactly where the base and non-graphic characters are. So in general the interval to be read will look likeand can be read a line at a time instead of a character at a time, with special handling for the partial first and last lines, and discarding the terminator characters at the end of each line read.
Timings in seconds for queries for regions of various lengths, with the iteration counts chosen so that develop took about a minute on each “repeatedly querying the same locus” test:
Opened as a draft PR because this will cause test failures until #1798 is fixed.