New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
reverse_complement: Do line wrapping and reverse complement in one step #55
Conversation
77e473d
to
d0625cc
Compare
Pushed some minor stylistic fixes. |
As an extra bonus, the sequence of operations in this version more closely resembles the C program, for anyone who wants to do side-by-side comparisons of the two. |
84e26be
to
4ce4f91
Compare
src/reverse_complement.rs
Outdated
/// Compute the reverse complement with the sequence split into two equal-sized slices. | ||
fn reverse_complement_left_right(left: &mut [u16], right: &mut [u16], tables: &Tables) { | ||
/// Compute the reverse complement for two contiguous chunks without line breaks. | ||
fn reverse_complement_chunk(left: &mut [u8], right: &mut [u8], tables: &Tables) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
We could reintroduce the u16
-based lookup inside this function... I'll try this and see what impact it has.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I tried this and it did not change performance at all. The code is at mbrubeck@e133026.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I like it.
I think I can write a comment with Ascii art to explain the loop, that would help the understanding. I'll try to write it today.
This is brilliant, I'd love to see it merged! |
I can't find a better explaination that what is already done. As Isaac closed the previous submission, do you prefer I submit or you submit? And maybe we should wait some days on a bench without update before submitting it. That's too much update of the same bench for Isaac ;-) |
src/reverse_complement.rs
Outdated
for (x, y) in left.iter_mut().zip(right.iter_mut().rev()) { | ||
let tmp = tables.cpl8(*x); | ||
*x = tables.cpl8(*y); | ||
*y = tmp; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
FWIW, I think you could write this as *y = tables.cpl8(mem::replace(x, tables.cpl8(*y)))
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Done.
src/reverse_complement.rs
Outdated
const SEQUENTIAL_SIZE: usize = 1024; | ||
/// Length of a normal line including the terminating \n. | ||
const LINE_LEN: usize = 61; | ||
const SEQUENTIAL_SIZE: usize = 2048; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Do you think it'd be worth making this some multiple of 61?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Do you think it'd be worth making this some multiple of 61?
I don't think it would make any noticeable difference.
src/reverse_complement.rs
Outdated
@@ -10,12 +10,11 @@ extern crate rayon; | |||
extern crate memchr; | |||
|
|||
use std::io::{Read, Write}; | |||
use std::{io, ptr, slice}; | |||
use std::{cmp, io, mem}; | |||
use std::fs::File; | |||
|
|||
struct Tables { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
What do you think about removing this struct
and just having a table: &[u8; 256]
passed around and a
fn build_table() -> [u8; 256] {
let mut table = [0u8; 256];
for (i, v) in table8.iter_mut().enumerate() {
*v = match i as u8 {
b'A' | b'a' => b'T',
b'C' | b'c' => b'G',
b'G' | b'g' => b'C',
b'T' | b't' => b'A',
b'U' | b'u' => b'A',
b'M' | b'm' => b'K',
b'R' | b'r' => b'Y',
b'W' | b'w' => b'W',
b'S' | b's' => b'S',
b'Y' | b'y' => b'R',
b'K' | b'k' => b'M',
b'V' | b'v' => b'B',
b'H' | b'h' => b'D',
b'D' | b'd' => b'H',
b'B' | b'b' => b'V',
b'N' | b'n' => b'N',
i => i,
};
}
}
called once in main
. Or we could even go one better and do what C does:
const TABLE: &'static [u8] =
b" \
TVGH CD M KN YSAABW R TVGH CD M KN YSAABW R";
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The last one must generate bound check, so better having a [u8; 256]
to elide bound checks.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
That's true: you could fill it up all the way to 256 and do const TABLE: &[u8; 256]
it's only 4 lines 64 chars. But yeah it's a bit silly.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I used the fn build_table() -> [u8; 256]
approach, because I found it the most readable.
4ce4f91
to
0ce7d17
Compare
I'll create a new submission for this after it's stabilized for at least a couple of days. |
I haven't come up with any new improvements and am no longer actively working on this benchmark, so I'll submit it later today if there are no other comments or changes posted. |
OK for me, I'll merge when you provide the link to the submission. |
0ce7d17
to
1135a92
Compare
Pushed my final version, which contains comment edits and a few minor style changes since the previous push. |
This combines newline handling and the main "reverse complement" step into a single loop. The downside of this is that it can no longer treat the input as u16 in order to transform two bytes with one table lookup. The advantages are faster speed from making a single pass over the data, and no more unsafe code!
This runs about 18% faster than the master branch on my computer.