Custom Cursor - how to optimize?

help
1

Hello!
I created my own cursor for reading values fro Vec<u8>.
I need to optimize it. How do it? Any ideas?


#[derive(PartialEq, Debug)]
/// The cursor for reading a low-level data
pub struct ReadCursor<'a, 'b> {
    data: &'a Vec<u8>,
    data_types: &'b Vec<DataType>,
    bit_pos: usize,
    byte_pos: usize,
    data_types_index: usize,
    byte_order: ByteOrdering,
}

impl<'a, 'b> ReadCursor<'a, 'b> {
    pub fn new(data: &'a Vec<u8>, data_types: &'b Vec<DataType>, byte_order: ByteOrdering) -> Self {
        ReadCursor {
            data,
            data_types,
            bit_pos: 0,
            byte_pos: 0,
            data_types_index: 0,
            byte_order,
        }
    }

    fn get_bit_lsb0(data: u8, index: usize) -> bool {
        (data >> index & 1) == 1
    }

    fn read_bool(&mut self) -> Option<bool> {
        let data = self.data.get(self.byte_pos)?;
        let bit_value = Self::get_bit_lsb0(*data, self.bit_pos);
        if self.bit_pos == BIT_LAST_INDEX {
            self.bit_pos = BIT_FIRST_INDEX;
            self.byte_pos += 1;
        } else {
            self.bit_pos += 1;
        }
        Some(bit_value)
    }

    fn read_u8(&mut self) -> Option<u8> {
        if self.bit_pos != BIT_FIRST_INDEX {
            self.bit_pos = BIT_FIRST_INDEX;
            self.byte_pos += 1;
        }
        let data = self.data.get(self.byte_pos)?;
        self.byte_pos += 1;
        Some(*data)
    }

    pub fn read_next(&mut self) -> Option<Value> {
        let dt = self.data_types.get(self.data_types_index)?;
        self.data_types_index += 1;

        let value = match dt {
            DataType::BOOL => Value::BOOL(self.read_bool()?),
            DataType::U8 => Value::U8(self.read_u8()?),
            _ => {
                return None;
            }
        };
        Some(value)
    }
}

Full Example: Playground

2

Optimize for what? Performance? Memory usage? Readability? Code-Golf?

5 Likes
3

Without knowing what you're optimizing for, I can only give guesses as to what will make your code more performant.

data: &'a Vec<u8>,
data_types: &'b Vec<DataType>,

You can save on one layer of indirection by replacing these with &'a [u8] and &'b [DataType]. A Vec<u8> contains a pointer to the backing allocation, so you can skip going through the extra pointer.

bit_pos: usize,
byte_pos: usize,

Using a usize for representing our position in a bit is wildly overkill here. I would at least recommend using a u8 for the bit position, or even packing both the bit and byte position into a single usize.

self.data_types_index += 1;

You can be even more clever about how you read out your data types. You can avoid indexing at all by simply using std::slice::Iter.

fn read_u8(&mut self) -> Option<u8> {
    if self.bit_pos != BIT_FIRST_INDEX {
        self.bit_pos = BIT_FIRST_INDEX;
        self.byte_pos += 1;
    }
    let data = self.data.get(self.byte_pos)?;
    self.byte_pos += 1;
    Some(*data)
}

Lastly, you can just use u8::from_be / u8::from_le to efficiently read out the byte.

2 Likes
4

Thanks for your reply. I need to optimize for speed. I used usize because self.data.get() required usize.

5

They are talking about this:

    fn get_bit_lsb0(data: u8, index: usize) -> bool {
        (data >> index & 1) == 1
    }

index can be u8 here, since its value is always in range 0..8. And by extension, ReadCursor::bit_pos can also be u8.

Anyway, I think there are performance optimization opportunities here, but we can only speculate what they are. Do some profiling and find the hot spots. Optimize those first.

2 Likes
6

Can you recommend any tool for profiling?

7
8

flamegraph is unreadable for me.

I would like to use profiling + puffin on Ubuntu Linux.