Transitioning base91 to Iterator and optimising

Hi all,

I have been looking at transitioning the base91 crate into using an Iterator implementation.

I have managed to implement the Iterator with the following code.

const ENTAB: [u8; 91] = [
    b'A', b'B', b'C', b'D', b'E', b'F', b'G', b'H', b'I', b'J', b'K', b'L', b'M',
    b'N', b'O', b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W', b'X', b'Y', b'Z',
    b'a', b'b', b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j', b'k', b'l', b'm',
    b'n', b'o', b'p', b'q', b'r', b's', b't', b'u', b'v', b'w', b'x', b'y', b'z',
    b'0', b'1', b'2', b'3', b'4', b'5', b'6', b'7', b'8', b'9', b'!', b'#', b'$',
    b'%', b'&', b'(', b')', b'*', b'+', b',', b'.', b'/', b':', b';', b'<', b'=',
    b'>', b'?', b'@', b'[', b']', b'^', b'_', b'`', b'{', b'|', b'}', b'~', b'"'
];

pub struct Encoder<I> {
    data: I,
    secondary: Option<u8>,
    rem: u32,
    shift: u32,
}

impl<I> Iterator for Encoder<I>
where
    I: Iterator<Item = u8>,
{
    type Item = u8;

    #[inline(always)]
    fn next(&mut self) -> Option<u8> {
        let mut x = self;
        if x.secondary.is_some() {
            return x.secondary.take();
        }

        while let Some(b) = x.data.next() {
            x.rem |= (b as u32) << x.shift;
            x.shift += 8;

            if x.shift > 13 {
                let mut key = x.rem & 8191;
                if key > 88 {
                    x.rem >>= 13;
                    x.shift -= 13;
                } else {
                    key = x.rem & 16383;
                    x.rem >>= 14;
                    x.shift -= 14;
                }

                x.secondary = Some(ENTAB[(key / 91) as usize]);
                return Some(ENTAB[(key % 91) as usize]);
            }
        }

        if x.shift > 0 {
            let r = Some(ENTAB[(x.rem % 91) as usize]);
            if x.shift > 7 || x.rem > 90 {
                x.secondary = Some(ENTAB[(x.rem / 91) as usize]);
            }
            x.shift = 0;
            r
        } else {
            None
        }
    }
}

When benchmarked, this code performs within 20% of the original implementation.

For pedagogical reasons, I am wondering:

  1. When implementing an iterator with this style of encoding (where an iteration might not return anything, then on the next iteration return two things), is this a good way to achieve it (with the secondary option)?
  2. Is there a more idiomatic ways of implementing this?
  3. Can the encoding be further optimised but still preserve an Iterator interface?

I’m not that familiar with base91 specifically, but that seems like an extremely normal Iterator implementation to me. It’s definitely normal for next() calls to do variable amounts of work (e.g. str::chars()), and normal for the iterator to contain whatever state would make the next next() call easier.

Whether you should cache the “secondary” in the iterator itself or re-derive it on the fly is largely a performance question. In other words, start with whichever’s simpler, and if you need more speed then benchmark the other.

The only thing that seems odd to me in that code sample is that “Encoder” doesn’t sound like the name of an iterator type.

Is there an optimisation you’re interested in that seems incompatible with Iterator? (asking because that could be a sign of an XY problem, where Iterator is simply the wrong interface)

1 Like

Thanks for the reply.

I agree, the name is mostly a placeholder while I am playing around.

No specific optimisations, any obvious changes that could help. I have been looking into SIMD as well (possibly through faster) but I don't think it would work with the stateful nature of the algorithm.

I am not well versed in these kinds of micro optimisations, so it is more of a learning experience for me.