Simplify SSSE3 nibble2base function by rhpvorderman · Pull Request #1802 · samtools/htslib

rhpvorderman · 2024-07-08T05:54:44Z

As promised in #1795, here is the simplified version of the SSSE3 routine for nibble2base conversion. @jmarshall suggested that the unpack instructions could be used for a simpler routine and that is what is done here.

jkbonfield · 2024-07-08T11:38:13Z

I like it and it seems like an easy win for complexity and helps on speed as well.

I did consider whether the memory loads were a bottle neck, so tried loading two lanes and processing two lanes, so the second load is essentially pipelined. It looked to work, but not for the reason I though:

# ./test/test_nibbles -c 10000000 -r 5000 -n timings
dev  gcc13 3.99, clang16 3.85                                                   
pr   gcc13 3.07, clang16 3.10                                                   
new  gcc13 2.61, clang16 2.85

My new code was this (with seq_vec_end_ptr adjusted accordingly)

    while (seq_cursor < seq_vec_end_ptr) {
        __m128i encoded[2];
        int i;
        for (i = 0; i < 2; i++) {
            encoded[i] = _mm_lddqu_si128((__m128i *)nibble_cursor);
            nibble_cursor += sizeof(__m128i);
        }

        for (i = 0; i < 2; i++) {
            __m128i enc_upper = _mm_srli_epi64(encoded[i], 4);
            enc_upper = _mm_and_si128(enc_upper, _mm_set1_epi8(15));
            __m128i enc_lower = _mm_and_si128(encoded[i], _mm_set1_epi8(15));
            __m128i nucs_upper = _mm_shuffle_epi8(nuc_lookup_vec, enc_upper);
            __m128i nucs_lower = _mm_shuffle_epi8(nuc_lookup_vec, enc_lower);
            __m128i first_nucs = _mm_unpacklo_epi8(nucs_upper, nucs_lower);
            __m128i second_nucs = _mm_unpackhi_epi8(nucs_upper, nucs_lower);
            _mm_storeu_si128((__m128i *)seq_cursor, first_nucs);
            _mm_storeu_si128((__m128i *)(seq_cursor + sizeof(__m128i)),
                             second_nucs);
            seq_cursor += 2 * sizeof(__m128i);
        }
    }

Ie load encoded[2] worth of data and then process.

It's clearly quicker on this system - 8-15% faster. However it has nothing to do with waiting on memory!

PR (clang);

 Performance counter stats for './test/test_nibbles -c 10000000 -r 5000 -n':

       2994.299226      task-clock (msec)         #    1.000 CPUs utilized          
                 5      context-switches          #    0.002 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
               473      page-faults               #    0.158 K/sec                  
        8901778582      cycles                    #    2.973 GHz                      (83.30%)
         695691208      stalled-cycles-frontend   #    7.82% frontend cycles idle     (83.31%)
         175195991      stalled-cycles-backend    #    1.97% backend cycles idle      (66.60%)
       28838017000      instructions              #    3.24  insn per cycle         
                                                  #    0.02  stalled cycles per insn  (83.30%)
        1686141707      branches                  #  563.117 M/sec                    (83.41%)
          10109044      branch-misses             #    0.60% of all branches          (83.38%)

       2.995203340 seconds time elapsed

encoded[2] array (clang)

 Performance counter stats for './test/test_nibbles -c 10000000 -r 5000 -n':

       2799.450579      task-clock (msec)         #    1.000 CPUs utilized          
                 5      context-switches          #    0.002 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
               472      page-faults               #    0.169 K/sec                  
        8339368809      cycles                    #    2.979 GHz                      (83.29%)
        1408302220      stalled-cycles-frontend   #   16.89% frontend cycles idle     (83.28%)
         179340812      stalled-cycles-backend    #    2.15% backend cycles idle      (66.64%)
       25724737241      instructions              #    3.08  insn per cycle         
                                                  #    0.05  stalled cycles per insn  (83.35%)
         906285051      branches                  #  323.737 M/sec                    (83.43%)
          11540581      branch-misses             #    1.27% of all branches          (83.36%)

       2.800534160 seconds time elapsed

So the reduction is in instructions and correspondingly cycles. Same with gcc and clang. It turns out to be simply due to loop unrolling the code and then having the main while loop iterator checked less often. Surprising it's that significant!

However it's icing on the cake and frankly all of these are fast enough now. It's using 4% of the total CPU for a test_view from uncompressed BAM to SAM, which is hardly a problem.

rhpvorderman · 2024-07-08T11:52:47Z

So the reduction is in instructions and correspondingly cycles. Same with gcc and clang. It turns out to be simply due to loop unrolling the code and then having the main while loop iterator checked less often. Surprising it's that significant!

That's kinda surprising indeed. If you look at the assembly it maps to very few instructions, so it is not that odd that the iterator check is significant. Kinda mind-boggling though that this decoding algorithm is so blazing-fast that iteration is a major component of the compute time.

I like it and it seems like an easy win for complexity and helps on speed as well.

The help on speed is because this compiles to very simple assembly (I checked on godbolt). The previous algorithm was more complex, as a result the compiler ran out of registers and issued a lot more load instructions to load stored registers from the stack.

jkbonfield · 2024-07-08T12:56:14Z

Thanks for the PR.

Yes I checked the assembly from gcc and also found it surprisingly succint. It's not always that clear with some SIMD instructions as they can map to a variable number, especially things like the set instructions.

jkbonfield · 2024-07-08T13:16:02Z

Also, why isn't there an _mm_srli_epi8? As always it appears with Intel intrinsics, there are baffling holes in the instruction set. I was thinking the AND instruction wouldn't be needed, but never mind.

rhpvorderman · 2024-07-08T13:26:49Z

There are probably electronic constraints. They have integrated 16-bit, 32-bit and 64-bit shifts, and integrating 8-bit shifts would require extra wiring and logic gates. There are physical constraints in microchip design, so that is probably why.

They could add _mm_srli_epi8 as a sequence of instructions though, but then the performance would noticably differ from the other _mm_srli_epixx instructions.

It is not that big of a deal though, adding another bitwise AND instruction with a throughput of 1/3 of a cycle. I suspect the gains of an epi8 shift would be minimal.

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)

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

rhpvorderman force-pushed the simplernibblessse3 branch 3 times, most recently from e6e42b4 to 2a33e6a Compare July 8, 2024 06:13

Simplify SSSE3 nibble2base function

0bcfc72

rhpvorderman force-pushed the simplernibblessse3 branch from 2a33e6a to 0bcfc72 Compare July 8, 2024 06:15

jkbonfield merged commit 6012472 into samtools:develop Jul 8, 2024

rhpvorderman deleted the simplernibblessse3 branch July 8, 2024 13:11

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Simplify SSSE3 nibble2base function#1802

Simplify SSSE3 nibble2base function#1802
jkbonfield merged 1 commit into
samtools:developfrom
rhpvorderman:simplernibblessse3

rhpvorderman commented Jul 8, 2024

Uh oh!

jkbonfield commented Jul 8, 2024

Uh oh!

rhpvorderman commented Jul 8, 2024

Uh oh!

jkbonfield commented Jul 8, 2024

Uh oh!

jkbonfield commented Jul 8, 2024

Uh oh!

rhpvorderman commented Jul 8, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Uh oh!

Conversation

rhpvorderman commented Jul 8, 2024

Uh oh!

jkbonfield commented Jul 8, 2024

Uh oh!

rhpvorderman commented Jul 8, 2024

Uh oh!

jkbonfield commented Jul 8, 2024

Uh oh!

jkbonfield commented Jul 8, 2024

Uh oh!

rhpvorderman commented Jul 8, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants