Crate strider

[ringbuffer operations on multiple values at once] (trait.SliceRing.html) with an [efficient implementation] (#performance)

useful for moving a window with variable step through a possibly infinite stream of values [while avoiding unnecessary memory allocations] (#memory)

handy when computing the short-time fourier transform.

to use add strider = "*" to the [dependencies] section of your Cargo.toml and call extern crate strider; in your code.

example

the following program reads a stream of chars from stdin. it moves a window of size 4 (WINDOW_SIZE) through that stream in steps of 2 (STEP_SIZE). it writes the contents of every window to stdout. for the input of ABCDEFGHIJK it produces the output ABCDCDEFEFGHGHIJ. it uses constant memory and does no allocations after the initial ones. you should be able to adapt it to your needs.

use std::io;
use std::io::{Write, Read};

extern crate strider;
use strider::{SliceRing, SliceRingImpl};

fn main() {
    const WINDOW_SIZE: usize = 4;
    const STEP_SIZE: usize = 2;

    let mut ring = SliceRingImpl::<u8>::new();
    let mut input_buffer: &mut [u8] = &mut [0; 20];
    let mut window_buffer: &mut [u8] = &mut [0; WINDOW_SIZE];

    loop {
        let input_count = io::stdin().read(input_buffer).unwrap();
        // leave the loop when we reach end of file
        if input_count == 0 { break; }

        // add elements to the back of the ring
        ring.push_many_back(&input_buffer[..input_count]);
        // read as long as we can read windows of length `WINDOW_SIZE`
        while WINDOW_SIZE <= ring.len() {
            ring.read_many_front(window_buffer);
            io::stdout().write(window_buffer).unwrap();
            // do a step by dropping the first `STEP_SIZE` elements in ring
            ring.drop_many_front(STEP_SIZE);
        }
    }
}

performance

the trait strider::SliceRing is implemented for std::collections::VecDeque (https://doc.rust-lang.org/stable/std/collections/struct.VecDeque.html) and strider::SliceRingImpl.

strider::SliceRingImpl is limited to the functionality in strider::SliceRing but optimized for it and 2 to 6 times faster than the implementation for std::collections::VecDeque.

see the benchmark results and implementation.

windowing the equivalent of 1 minute of 44100 hz audio samples with a window_size of 1024 and step_size of 512 only takes around 5 milliseconds.

memory

the following holds true for both implementations:

strider::SliceRing::read_many_front never allocates memory. it writes into a buffer that you allocate and control.

strider::SliceRing::drop_many_front never allocates memory.

strider::SliceRing::push_many_back reads from a buffer that you allocate and control. it might allocate more capacity when you push values and as a result there are more values in the ring than ever before. if you repeatedly read and drop after each push, as in the example above, the number of values will stay below a certain value and it will never allocate memory after an initial 1 or 2 allocations.

Macros

test_slice_ring

macro containing a test run that is used to test and benchmark different implementations of the SliceRing trait

Structs

SliceRingImpl

readable area starts at first_readable and goes until next_writable. next_writable is one after the last readable and not readable.

Traits

SliceRing

ringbuffer operations on slices