Use FNV1a for string hashing#1806
Merged
Merged
Conversation
Contributor
|
Why does our benchmark only show ~2-fold difference for Numbers, but the linked issue was 1-2 mins vs 15 hours (so ~500x speed difference). Are we sure this fixes the issue as it sounds like something else was going on too. Edit: actually it looks like your "numbers" file was their fix, and not the cause of the problem. They had something akin to base64 encoding originally. |
Member
Author
|
We don't know exactly what values were used in the linked issue, but it's possible to make something similar with this perl 1-liner: Running the benchmark on this gives a much bigger difference (8994 seconds is approx. 2.5 hours):
The probe chart for X31 is fairly spectacular:
while the one for FNV1a is much more well-behaved:
Assuming lookups that are evenly distributed between all the bins, on average you'd need something like 5563 comparisons to find something in an X31 hash table, but only 1.7 in one using FNV1a. That would easily account for the difference in speed seen. |
jkbonfield
reviewed
Jul 17, 2024
Comment on lines
+446
to
+447
| const khint_t offset_basis = 2166136261; | ||
| const khint_t FNV_prime = 16777619; |
Contributor
There was a problem hiding this comment.
Can we get consistent indentation here please? Similarly for __ac_FNV1a_hash_kstring below. That looks like hard tabs for this file, although there's precedence for 4 spaces in the Wang hash.
I don't mind either way except for not switching half way through a function :-)
Member
Author
There was a problem hiding this comment.
Spacing has been made consistent.
The existing X31 hash propagates bits fairly slowly, resulting in a poor distribution of keys if most of the differences in strings are at the end. Fix by using FNV1a instead, which is a similar speed to calculate but distributes keys much more effectively. Includes kh_stats() function in khash which produces a histogram of probe chain lengths and a khash test framework. The test program can also be used to benchmark insertion and lookup times.
Member
Author
|
Marked as "Ready for review" now samtools/samtools#2081 has been merged. Both samtools' and bcftools' |
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
2 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.
Note draft because samtools/samtools#2081 needs to be merged first, to fix a dependency on hash table ordering on some outputs.
The existing X31 hash propagates bits fairly slowly, resulting in a poor distribution of keys if most of the differences in strings are at the end. Fix by using FNV1a instead, which is a similar speed to calculate but distributes keys much more effectively. While this cannot completely solve the problem of certain inputs distributing badly, it hopefully makes it less likely to accidentally find one.
Includes kh_stats() function in khash which produces a histogram of probe chain lengths and a khash test framework. The test program can also be used to benchmark insertion and lookup times.
Some benchmarking results are listed below. The "Numbers" input is the default benchmark, consisting of strings
test0through totest49999999. "Human" is the reference names from GRCh38_full_analysis_set_plus_decoy_hla.fa. "Big" is the reference names from the file with a very large header linked in issue samtools/samtools#1105.So FNV1a performance is much better than X31 on bad cases, a little better for everything on lookups, and only slightly slower for insertions on the "Human" and "Big" tests.
Also for interest, here are probe length charts for the various tests (note log scales on y):
"Numbers", showing a very poor distribution for X31:
"Human":
"Big", in this case the names are long so X31 mixes better and the distributions are similar:
Fixes samtools/samtools#2066