Enter your search text in the box above

Select a result to preview

Use VecDeque for Bounded FIFOs

#resources #resources/programming #resources/programming/rust #resources/programming/performance

Use VecDeque for bounded FIFOs

A bounded FIFO ring buffer built on Vec with remove(0) to drop the oldest entry is an O(n) memmove on every push once it's full. VecDeque does the same job in O(1). This is the most common "looks fine, scales badly" data-structure choice in Rust.

The trap

struct EventLog { cap: usize, items: Vec<Event> }

impl EventLog {
    fn push(&mut self, e: Event) {
        if self.items.len() >= self.cap {
            self.items.remove(0);   // shifts every remaining element left
        }
        self.items.push(e);
    }
}

Vec::remove(0) removes the first element and then shifts all n-1 survivors down one slot to fill the gap. On a full buffer that's an O(n) copy on every single push, forever. For a 1000-entry event log that's a thousand-element memmove per event, doing nothing but churn.

The fix

use std::collections::VecDeque;

struct EventLog { cap: usize, items: VecDeque<Event> }

impl EventLog {
    fn push(&mut self, e: Event) {
        if self.items.len() >= self.cap {
            self.items.pop_front();   // O(1)
        }
        self.items.push_back(e);
    }
    fn snapshot(&self) -> Vec<Event> {
        self.items.iter().cloned().collect()
    }
}

VecDeque is a growable ring buffer. pop_front and push_back are both O(1) amortised because it moves head/tail indices instead of elements. Iteration order is still front-to-back (oldest to newest), so a snapshot() that collects into a Vec preserves the exact ordering the Vec version had. As a free bonus, pop_front() on an empty deque returns None instead of the panic remove(0) would throw, so the degenerate cap == 0 case stops being a landmine.

This was a real one-line-per-method swap in Spotuify's daemon event log, and the existing behaviour test (push five into a cap-two buffer, assert the two newest survive in order) covered it unchanged — the textbook case for Refactor Behind a Behavior Test.

The general rule

The moment you write .remove(0), .insert(0, _), or .drain(0..k) on a Vec in anything that runs repeatedly, reach for VecDeque. Vec is for push/pop at the end. Front operations are what the deque is for. (The same instinct as preferring O(1) bookkeeping over O(n) rescans elsewhere, e.g. Use Stored Length Not strcat.)

See also