C & C++ reverse-complement Jeremy Zerfas
CONTRIBUTE SOURCE CODE
C reverse-complement Jeremy Zerfas
This program uses techniques from the Rust #1, C++ #7, and C++ #2 programs. This program should have a run time around 10% faster than the Rust #1 program, a CPU time around 20% faster than the C++ #2 program, and smaller minified source code size and slightly less memory usage than the Rust #1 and C++ #2 programs. Each of the mentioned programs had a few useful techniques of its own but each one was also missing a few useful techniques from the other programs, this program uses most of the techniques from each of those programs.
-
First like the Rust #1 program, this program uses multiple threads to process chunks of a single sequence in parallel.
-
Like the Rust #1 and C++ #2 programs, this program uses SSE instructions to allow it to reverse complement sixteen characters at a time. I also slightly tweaked a few of the SSE instructions so that it uses one less instruction but this does require SSE 4.1 whereas the Rust #1 and C++ #2 programs only require SSSE3.
-
Like the C++ #7 program, this program starts reverse complementing from the end of the sequence, works its way to the front, and outputs the reverse complemented sequence while doing the reverse complementing. Many of the other programs start at the front and back, work their way to the middle, and then output the reverse complemented sequence after finishing reverse complementing the entire sequence. The C++ #7 program and my program can leave the sequence unmodified (they write just a small portion of the reverse complemented sequence to a separate part of likely cached memory before outputting it) whereas many of the other programs are doing an in-place reverse complement or writing the entire reverse complemented sequence to separate memory. This technique avoids doing a write and read of the entire sequence to main memory. I'm not sure if this counts as a different algorithm, it seemed close enough to the algorithm used by the other programs to me and I figured I would use it since the C++ #7 program (and maybe a few others) was previously accepted. If needed, I can resubmit this program and make it work more like the other programs.
-
Like the C++ #7 program, this program creates and uses a lookup table that allows it to reverse complement two characters at a time (when the span length to be reversed is less than sixteen characters long or the SSE code can't be used because it isn't supported).
-
Like the C++ #2 program, this program does check for an optimal sized sequence that consists entirely of full lines and will use a more streamlined code path to handle those sequences.
One last note is that I originally meant for this program to use OpenMP instead of POSIX threads but it seems like in this case Clang's current OpenMP implementation is resulting in programs using considerably more CPU time than when compiled with GCC. I changed the program to use POSIX threads so that it would perform well on both Clang and GCC but unfortunately this does make the program a bit less portable and also considerably increased the minified source code size.
Attach your source code file
Provide an example build command-line
GCC
gcc -O3 -march=native -static -pthread Reverse-Complement.c -o Reverse-Complement
Clang
clang -O3 -march=native -static -pthread Reverse-Complement.c -o Reverse-Complement