Adding generic incur in penalty?
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 119k
- Forks
- 16.1k
- PR merge metrics
- PR metrics pending
Description
i have this function
#[derive(Debug, Error)]
pub enum BitReaderError {
#[error("Overflow")]
Overflow,
}
#[derive(Debug)]
pub struct BitReader<'a> {
data: &'a [u8],
pos: usize,
}
impl<'a> BitReader<'a> {
pub fn new(data: &'a [u8]) -> Self {
Self { data, pos: 0 }
}
pub fn read_bits(&mut self, bits: u8) -> Result<u32, BitReaderError>
{
let min_bytes = (bits / 8) as usize;
let additional_byte = bits % 8 != 0;
let start_byte = self.pos / 8;
let end_byte = self.pos / 8 + min_bytes + (additional_byte as usize);
let slice = self
.data
.get(start_byte..end_byte)
.ok_or(BitReaderError::Overflow)?;
let mut result = u32::default();
let mut bits_to_read = bits;
for &byte in slice {
let bits = if bits_to_read > 8 {
bits_to_read -= 8;
8
} else {
bits_to_read
};
// 4
let current_bits = (self.pos % 8) as u8;
let mask = 0b1111_1111 >> (8 - bits);
// 0
let total_shift = 8 - current_bits - bits;
result <<= bits;
result |= u32::from((byte >> total_shift) & mask);
}
self.pos += bits as usize;
Ok(result)
}
}
my benchmark
fn run_benchmarks(c: &mut Criterion) {
let mut group = c.benchmark_group("bit_reader");
group.sample_size(100);
group.bench_function("read_bits", |bencher| {
bencher.iter(|| {
let slice = [0u8; 1000000];
let mut reader = bit_reader::BitReader::new(&slice);
for _ in 0..500 {
let _: u32 = reader.read_bits(black_box(4)).unwrap();
let _: u32 = reader.read_bits(black_box(32)).unwrap();
let _: u32 = reader.read_bits(black_box(5)).unwrap();
let _: u32 = reader.read_bits(black_box(16)).unwrap();
let _: u32 = reader.read_bits(black_box(1)).unwrap();
let _: u32 = reader.read_bits(black_box(20)).unwrap();
let _: u32 = reader.read_bits(black_box(7)).unwrap();
}
})
});
group.finish();
}
criterion_group!(benches, run_benchmarks);
criterion_main!(benches);
result:
bit_reader/read_bits time: [2.7852 µs 2.8100 µs 2.8390 µs]
change: [+0.6586% +1.7631% +2.7715%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 2 outliers among 100 measurements (2.00%)
2 (2.00%) high mild
but if i add generics (just replace u32 with T)
pub fn read_bits<T>(&mut self, bits: u8) -> Result<T, BitReaderError>
where
T: Default + ops::ShlAssign<u8> + ops::BitOrAssign + From<u8>,
{
let min_bytes = (bits / 8) as usize;
let additional_byte = bits % 8 != 0;
let start_byte = self.pos / 8;
let end_byte = self.pos / 8 + min_bytes + (additional_byte as usize);
let slice = self
.data
.get(start_byte..end_byte)
.ok_or(BitReaderError::Overflow)?;
let mut result = T::default();
let mut bits_to_read = bits;
for &byte in slice {
let bits = if bits_to_read > 8 {
bits_to_read -= 8;
8
} else {
bits_to_read
};
// 4
let current_bits = (self.pos % 8) as u8;
let mask = 0b1111_1111 >> (8 - bits);
// 0
let total_shift = 8 - current_bits - bits;
result <<= bits;
result |= T::from((byte >> total_shift) & mask);
}
self.pos += bits as usize;
Ok(result)
}
performance is waaay worse
bit_reader/read_bits time: [28.764 µs 28.959 µs 29.150 µs]
change: [+920.58% +931.94% +943.93%] (p = 0.00 < 0.05)
Performance has regressed.
Found 40 outliers among 100 measurements (40.00%)
23 (23.00%) low severe
1 (1.00%) low mild
1 (1.00%) high mild
15 (15.00%) high severe
why is this? only change was to replace u32 with T
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the provided BitReader::read_bits implementation and the Criterion run_benchmarks benchmark, reproducing both the u32 and generic T cases. Compare the benchmark behavior and generated results to determine why the generic version is substantially slower; done means explaining the regression and identifying whether it is a Rust compiler issue.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100