Deque Ring Buffers for Sliding Windows

In this lesson, you will learn how to implement a high-throughput sliding window using a VecDeque to efficiently manage streaming data ingestion.

When processing time-series data—such as calculating a moving average—you often need to keep a fixed number of recent elements while discarding the oldest. Using a Vec for this is suboptimal because removing the first element requires shifting all remaining elements in memory, leading to $O(n)$ performance.

A VecDeque (Double-Ended Queue) solves this by acting as a ring buffer. It maintains two pointers (head and tail) and wraps around the underlying memory, allowing you to push new data and pop old data in $O(1)$ constant time.

Implementing a Sliding Window

To create a moving average, you initialize a VecDeque with a fixed capacity. When a new sample arrives, you push it to the back. If the queue exceeds your window size, you pop from the front.

use std::collections::VecDeque;

struct MovingAverage {
    buffer: VecDeque<f64>,
    window_size: usize,
    sum: f64,
}

impl MovingAverage {
    fn new(window_size: usize) -> Self {
        Self {
            buffer: VecDeque::with_capacity(window_size),
            window_size,
            sum: 0.0,
        }
    }

    fn push(&mut self, val: f64) {
        if self.buffer.len() == self.window_size {
            // Remove oldest, subtract from tracking sum
            if let Some(old) = self.buffer.pop_front() {
                self.sum -= old;
            }
        }
        self.buffer.push_back(val);
        self.sum += val;
    }
}

Why this is high-throughput

Because VecDeque uses a circular buffer strategy, it avoids the expensive re-allocation and memory shifting inherent in standard vectors. By pre-allocating the capacity with with_capacity(window_size), you ensure that the internal buffer remains stable, making it an ideal choice for high-frequency streaming applications where memory latency is critical. By tracking your state (like the sum variable) alongside the queue, you avoid iterating over the window every time a new piece of data arrives, keeping your ingestion pipeline running at near-peak hardware speed.

Key Takeaway: Use a VecDeque as a ring buffer to achieve O(1) ingestion and eviction, ensuring your sliding window logic doesn't become a performance bottleneck in streaming pipelines.