Buffers circulares y ring buffers

Qué cubre este capítulo

Una queue que crece sin límite funciona bien hasta que la memoria dice basta. El ring buffer es la solución: fijas la capacidad desde el inicio, acomodas los elementos en círculo, y dejas que la posición de escritura regrese al principio cuando se sale del final. Obtienes una queue FIFO O(1) que nunca vuelve a asignar memoria después de construirse — y un poder nuevo muy útil: la capacidad de sobrescribir el elemento más viejo cuando está llena, que es justo lo que quieres para un log rotativo de los últimos N eventos. Este capítulo construye uno con nada más que un array y dos índices, y demuestra que todo el truco es un solo módulo.

Un poco de historia

El ring buffer no tiene un inventor famoso — es una de esas ideas que salieron del hardware y nunca se fueron. Las primeras máquinas necesitaban mover datos entre componentes que corrían a velocidades distintas, y un buffer circular fijo con un apuntador de lectura persiguiendo a uno de escritura era la forma natural de hacerlo sin asignar memoria que no tenías. Ese patrón se volvió estándar en los años 60 y 70 para buffering de I/O y procesamiento digital de señales, y sigue por todos lados cerca del metal: los pipes de Unix, el driver de la terminal, sistemas de audio como JACK, los rings de las tarjetas de red, el kfifo del kernel de Linux, y los ring buffers lock-free en el corazón de sistemas de trading de alta frecuencia como el LMAX Disruptor. Cuando la latencia tiene que ser predecible y asignar memoria es el enemigo, esta es la estructura.

La intuición

Imagina la carátula de un reloj con ranuras en lugar de horas. Mantienes dos manecillas: una de escritura (el tail) apuntando a la siguiente ranura libre, y una de lectura (el head) apuntando al elemento más viejo. Push escribe donde apunta la manecilla de escritura y la mueve una ranura en sentido horario; pop lee donde apunta la manecilla de lectura y la mueve una ranura en sentido horario. Cuando cualquiera de las dos pasa la última ranura, regresa a la primera — ese es el "ring".

Como las ranuras se reutilizan conforme las manecillas dan vueltas, el buffer nunca crece y nunca asigna memoria. La única pregunta es qué pasa cuando la manecilla de escritura alcanza a la de lectura — cuando el buffer está lleno. Tienes dos opciones honestas: rechazar el push (backpressure — decirle al productor que espere), o sobrescribir el elemento más viejo y arrastrar la manecilla de lectura contigo (quedarte solo con los N más recientes). Las dos son útiles; son herramientas distintas.

Complejidad: cómo escala

Cada operación es una escritura o lectura en un índice conocido más un incremento y un módulo — todo $O(1)$, sin recorrer nada, sin buscar nada, y lo más importante: sin asignar memoria después de construir el buffer. El espacio queda fijo en $O(\text{capacity})$ sin importar cuántos elementos pasen por ahí; un buffer de 1000 ranuras maneja mil millones de pushes en las mismas 1000 ranuras. Aquí no hay recurrencia ni amortización — a diferencia del array dinámico, un ring buffer nunca se redimensiona, así que su O(1) es de peor caso, no un promedio. La gráfica pasa un número grande de pushes por un buffer fijo de tamaño 1000; la línea es recta porque el costo por push es genuinamente constante:

Para qué sirve, y para qué no

Un ring buffer es la herramienta correcta para un stream acotado — una ventana fija sobre datos que no dejan de fluir. Su tamaño fijo es una virtud, no una limitación: sin asignación de memoria no hay pausas del garbage collector ni crecimiento de memoria, y por eso los sistemas de tiempo real y embebidos lo adoran. En esos contextos, el O(1) de peor caso con memoria predecible vale más que el mejor promedio de una estructura más sofisticada.

Sus límites son la otra cara de ese tamaño fijo. Si no conoces la capacidad máxima, o puede dispararse arbitrariamente, un ring buffer va a rechazar datos (modo de rechazo) o a perderlos en silencio (modo de sobrescritura) — y cualquiera de las dos puede ser un bug si elegiste el modo equivocado. Tampoco es de acceso aleatorio ni permite búsquedas; es una queue con wraparound, nada más.

Los datos, o las entradas

El face-off pasa un número grande de pushes por un buffer fijo de 1000 ranuras en modo de sobrescritura — la carga de trabajo de "quédate con los 1000 más recientes" — para que lo que se mida sea justamente el comportamiento de tiempo constante y memoria constante. La animación usa un buffer diminuto de seis ranuras y un guion escrito a mano, porque lo que de verdad hay que ver es el tail dando la vuelta de la última ranura a la primera, y la sobrescritura cuando se llena.

Constrúyelo, una función a la vez

Push es donde vive el wraparound. Escribe en el tail, avanza el tail con un módulo para que dé la vuelta, y — si el buffer está lleno — o rechaza, o descarta el más viejo avanzando el head:

def push(self, value):
    """O(1): write at the tail, then advance the tail — wrapping to 0 when it
    runs off the end. If the buffer is full, either refuse or drop the oldest
    item (advancing the head) to make room."""
    if self._count == self._cap:
        if not self._overwrite:
            raise IndexError("push to a full ring buffer")
        self._head = (self._head + 1) % self._cap   # forget the oldest
        self._count -= 1
    self._buf[self._tail] = value
    self._tail = (self._tail + 1) % self._cap       # the wraparound
    self._count += 1

Pop es el espejo: lee en el head, limpia la ranura, avanza el head con el mismo wraparound. Siempre devuelve el elemento más viejo, porque un ring buffer sigue siendo una queue FIFO por debajo:

def pop(self):
    """O(1): read at the head, clear the slot, advance the head with the same
    wraparound. Returns the oldest item — this is still a FIFO queue."""
    if self._count == 0:
        raise IndexError("pop from an empty ring buffer")
    value = self._buf[self._head]
    self._buf[self._head] = None
    self._head = (self._head + 1) % self._cap
    self._count -= 1
    return value

Esa es toda la estructura. Dos índices, un array, y % capacity haciendo todo el trabajo de que un array finito se comporte como un círculo infinito.

Míralo trabajar

Aquí hay un buffer de seis ranuras en modo de sobrescritura. Las ranuras están fijas en su lugar — la ranura 0 a la ranura 5 nunca se mueven — y son las posiciones las que viajan alrededor de ellas. El verde es el elemento más viejo (el siguiente en salir con pop); las ranuras azules están ocupadas; las oscuras están libres. Avanza paso a paso y mira cómo el tail llena las ranuras de izquierda a derecha, luego regresa a la ranura 0 cuando se sale del final, y finalmente sobrescribe el elemento más viejo una vez que el buffer se llena. Los datos se mueven en círculo aunque el array sea una línea recta:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña from-scratch es nuestro RingBuffer, dos índices y un módulo. La pestaña de librería es collections.deque(maxlen=N): dale un maxlen a un deque y se convierte en un ring buffer acotado que sobrescribe lo más viejo, sin aritmética de índices que escribir tú mismo.

"""A ring buffer — a fixed-size queue that reuses its space by wrapping around.

A normal queue grows without bound. A ring buffer fixes the capacity up front and
lays the elements out in a circle: when the write position runs off the end of the
array, it wraps back to the start. That makes it O(1) with zero allocation after
construction, and gives it a useful trick — when it's full, it can overwrite the
oldest item, which is exactly what you want for a "last N events" log.
"""


class RingBuffer:
    def __init__(self, capacity, overwrite=False):
        self._cap = capacity
        self._buf = [None] * capacity   # the fixed backing array, never resized
        self._head = 0                  # index of the oldest item (next to pop)
        self._tail = 0                  # index of the next free slot (next write)
        self._count = 0
        self._overwrite = overwrite     # when full: drop the oldest vs. refuse

    # region: push
    def push(self, value):
        """O(1): write at the tail, then advance the tail — wrapping to 0 when it
        runs off the end. If the buffer is full, either refuse or drop the oldest
        item (advancing the head) to make room."""
        if self._count == self._cap:
            if not self._overwrite:
                raise IndexError("push to a full ring buffer")
            self._head = (self._head + 1) % self._cap   # forget the oldest
            self._count -= 1
        self._buf[self._tail] = value
        self._tail = (self._tail + 1) % self._cap       # the wraparound
        self._count += 1
    # endregion

    # region: pop
    def pop(self):
        """O(1): read at the head, clear the slot, advance the head with the same
        wraparound. Returns the oldest item — this is still a FIFO queue."""
        if self._count == 0:
            raise IndexError("pop from an empty ring buffer")
        value = self._buf[self._head]
        self._buf[self._head] = None
        self._head = (self._head + 1) % self._cap
        self._count -= 1
        return value
    # endregion

    def is_full(self):
        return self._count == self._cap

    def __len__(self):
        return self._count

    def to_list(self):
        """Oldest to newest — walk `count` slots forward from the head."""
        return [self._buf[(self._head + i) % self._cap] for i in range(self._count)]

    def raw(self):
        """Backing array + head/tail/count, for the animation."""
        return list(self._buf), self._head, self._tail, self._count

"""collections.deque(maxlen=N) is a ring buffer in disguise. Give a deque a
maxlen and it becomes bounded: once it's full, every append silently drops the
item at the opposite end — exactly the overwrite-oldest behaviour of our ring
buffer, implemented in C with no Python-level index arithmetic.

So the face-off is our RingBuffer against `deque(maxlen=N)`, the standard-library
way to keep "the most recent N" of something.
"""
from collections import deque


# region: bounded_deque
def make_bounded(capacity):
    """A bounded deque: appends past `capacity` drop the oldest (leftmost)."""
    return deque(maxlen=capacity)
# endregion


# region: run_ops
def run_ops_deque(ops, capacity):
    """Drive ('push', x) / ('pop',) on a bounded deque, overwrite-on-full."""
    dq = deque(maxlen=capacity)
    popped = []
    for op in ops:
        if op[0] == "push":
            dq.append(op[1])       # drops the oldest automatically when full
        elif dq:
            popped.append(dq.popleft())
    return popped, list(dq)
# endregion

Scratch vs librería

Los dos son O(1) por push, así que las líneas son rectas y la brecha es un factor constante. Pasar 800000 pushes por un buffer de tamaño 1000 le tomó a nuestro RingBuffer unos 85 ms contra los 8.8 ms de deque(maxlen) — más o menos diez veces más lento:

Diez veces es una constante grande, y es honesta sobre lo que cuesta Python: nuestro push hace un módulo explícito, dos búsquedas de atributos y una asignación por índice por cada elemento, todo en bytecode interpretado, mientras que deque hace todo el append acotado en C. Las asintóticas son idénticas — ambas líneas planas — así que en una carga de trabajo donde el buffer es el cuello de botella usarías el deque. El ring buffer lo construyes para entender qué está haciendo maxlen, y porque en un lenguaje de más bajo nivel, donde nadie te regala un deque, este array de dos índices es lo que escribirías.

Dónde te lo vas a encontrar

Los ring buffers viven donde los datos pasan en stream por una ventana fija. Los pipelines de audio y video los usan para conectar al productor (el micrófono, la red) con el consumidor (la bocina, el decodificador) sin caer en asignación de memoria en la ruta de tiempo real. Las tarjetas de red le entregan paquetes al sistema operativo mediante descriptor rings. Los sistemas de logging guardan las últimas N líneas en un ring para que un crash dump tenga contexto reciente sin memoria ilimitada. dmesg, el log del kernel de Linux, es un ring buffer. Y cada vez que has escrito deque(maxlen=100) para mantener una ventana rotativa de valores recientes, usaste uno — este capítulo es lo que ese maxlen hace por debajo.

Conclusiones

Un ring buffer es un array fijo más dos índices que dan la vuelta: push en el tail, pop en el head, y % capacity dobla las posiciones que avanzan sin parar de vuelta a las mismas ranuras para siempre. Es $O(1)$ en el peor caso y sin asignación de memoria, lo que lo convierte en la queue por defecto cuando la memoria está acotada y la latencia debe ser predecible — y su modo de sobrescribir-cuando-está-lleno es la forma natural de conservar "los N más recientes" de un stream.

Con esto cerramos las estructuras lineales. Arrays, listas ligadas, stacks, queues y ring buffers son los contenedores a los que recurres por defecto, cada uno una respuesta distinta a "¿en qué extremo trabajo, y el tamaño crece?". El siguiente nivel cambia la pregunta por completo: en lugar de ordenar elementos en una línea, el hashing los dispersa por su contenido para que puedas encontrar cualquiera en tiempo constante — empezando con la hash table.