Pure C++ CircularBuffer

[CrushedPixel]

Since JUCE, for whatever reason, still does not have a circular buffer, which is something that pretty much any audio project needs, I’ll donate this one. It can only do sizes that are a power of 2, but this comes with the benefit of great performance.

The JUCE team is hereby allowed to add this to their framework, and anyone else can use it as a starting point (or drop-in solution!)

#pragma once

#include <vector>
#include <cassert>
#include "Math.h"

template<typename T>
class CircularBuffer {
public:
	/**
	 * Creates a circular buffer of size n.
	 * @param n The buffer size. Must be a power of 2.
	 * @param value The value to fill the buffer with.
	 */
	explicit CircularBuffer<T>(size_t n, T value = T()) :
			size(n), data(n, value), i(0) {
		// ensure the buffer size is a power of 2
		assert(n == nextPowerOf2(n));
	}

	/**
	 * Returns a reference to the buffer element at the given index.
	 * @param x the index
	 * @return a reference to a buffer element
	 */
	T &operator()(size_t x) {
		assert(x >= 0 && x < size);
		return data[mask(i + x)];
	}

	/**
	 * Returns a copy of the buffer element at the given index.
	 * @param x the index
	 * @return a copy of a buffer element
	 */
	T operator()(size_t x) const {
		assert(x >= 0 && x < size);
		return data[mask(i + x)];
	}

	/**
	 * Returns a reference to the buffer element at the given index,
	 * starting from the end of the buffer.
	 * @param x the index
	 * @return a reference to a buffer element
	 */
	T &operator[](size_t x) {
		return operator()(size - x - 1);
	}

	/**
	 * Returns a copy of the buffer element at the given index,
	 * starting from the end of the buffer.
	 * @param x the index
	 * @return a copy of a buffer element
	 */
	T operator[](size_t x) const {
		return operator()(size - x - 1);
	}

	/**
	 * Inserts an element at the front of the buffer,
	 * shifting out the last element.
	 * @param element the element to push into the buffer
	 * @return The element that was shifted out of the buffer.
	 */
	T shift(T element) {
		auto pushed = operator()(0);
		push(element);
		return pushed;
	}

	/**
	 * Inserts an element at the front of the buffer,
	 * shifting out the last element.
	 * @param element the element to push into the buffer
	 */
	void push(T element) {
		data[mask(i++)] = element;
	}

	/**
	 * Replaces every element in the buffer with the type's default value.
	 */
	void clear() {
		fill(T());
	}

	/**
	 * Replaces every element in the buffer with the given value.
	 * @param value The value to fill.
	 */
	void fill(T value) {
		std::fill(data.begin(), data.end(), value);
	}

	/**
	 * The size of the buffer.
	 */
	const size_t size;

private:
	/**
	 * Vector containing the underlying data.
	 */
	std::vector<T> data;

	/**
	 * index of the current first element of the circular buffer.
	 */
	size_t i;

	size_t mask(size_t val) const {
		return val & (size - 1);
	}
};

[reFX]

https://docs.juce.com/master/classAbstractFifo.html

[refusesoftware]

This one might actually be closer, and it also requires sizes that are powers of two:

[JUCE: SingleThreadedAbstractFifo Class Reference]

[Qfactor]

@reFX

JUCE: AbstractFifo Class Reference

If you need to write and read to it in a thread safe way, that is the best class to use but to the OP’s defense this is less efficient.

[daniel]

For block wise operating circular buffers I call the bitmask “trick” a premature optimisation. The free choice of buffer sizes might have a bigger impact than the modulo (and I don’t use modulo either but simply:

pos += numUsed;
if (pos >= bufferSize) pos -= bufferSize;

certainly cheaper and free choice

[xenakios]

The Juce AbstractFifo also isn’t an actually working implementation, additional code needs to be written around it.

[CrushedPixel]

My tuning algorithm processed the input sample by sample, I didn’t do block processing, and for this purpose this was a more than necessary optimization.

[Rincewind]

I second this! It at least shows, that the class isn’t as is always useful as the abstract concept of a circular buffer.
Moreover, you seem to relay on a lot of compiler optimization to erase useless copies that might not be trivial. So it clearly isnt the one and only truth

[kerfuffle]

As always It Depends™ but I’d add that the bit mask trick requires the masking operation to be performed on every sample, while the pos -= bufferSize only happens only every so often.

True, there is a branch from the if-statement, but most of the time the CPU’s branch prediction will correctly predict that we can skip it, making the branch effectively free (except once every so often it will be wrong when when we need to do the wrapround).

It depends on how large the circular buffer is and how many steps it takes before you need to wrap around, and how good the branch prediction is. A while ago I did some tests and under some circumstances the bit mask trick is faster, and under other circumstances the branch is faster.

[Qfactor]

This thread has inspired me to rewrite my circular buffer methods so I can easily swap both approaches to check for performance gains. Feel free to comment if you find something that can still be optimized! Here’s my last version with two classes: CircularAudioBuffer and P2CircularAudioBuffer with the mask trick which may give it a little edge when getting samples individually. Use the methods push/pushBuffer to add samples and get/getBuffer to get them.

// Author: Qfactor (2023). Released with the MIT license. 
// If you change something please add a note here.

/**
Circular buffer where you can push samples and get the last samples written 
individually or in blocks
*/
template<class Type = float>
class CircularAudioBuffer : public AudioBuffer<Type> 
{

protected:
	int ptr; // writing position
	int lastPosition; // numOfSamples-1

public:
	CircularAudioBuffer(int numChannels, int numOfSamples)
		:AudioBuffer<Type>(numChannels, numOfSamples)
		, ptr(0)
		, lastPosition(numOfSamples-1)
	{
	}

	virtual void setSize(int newNumChannels,
		int numOfSamples,
		bool keepExistingContent = false,
		bool clearExtraSpace = false,
		bool avoidReallocating = true)
	{
		ptr=0;
		lastPosition = numOfSamples - 1;
		AudioBuffer<Type>::setSize(newNumChannels, numOfSamples, keepExistingContent, clearExtraSpace, avoidReallocating);
	}

	virtual void push(const Type source)
	{
		jassert(AudioBuffer<Type>::getNumChannels() == 1);
		
		AudioBuffer<Type>::setSample(0, ptr, source);

		if (ptr==lastPosition)
			ptr=0;
		else
			ptr++;
	}

	virtual void push(const Type sourceLeft, const Type sourceRight)
	{
		jassert(AudioBuffer<Type>::getNumChannels() == 2);

		AudioBuffer<Type>::setSample(0, ptr, sourceLeft);
		AudioBuffer<Type>::setSample(1, ptr, sourceRight);

		if (ptr==lastPosition)
			ptr=0;
		else
			ptr++;
	}

	template<class SourceType>
	void pushBuffer(const SourceType* sourceBuffer, const int sourceStartSample, const int numSamples)
	{
		jassert(numSamples < AudioBuffer<Type>::getNumSamples());
		jassert(sourceStartSample >= 0);
		jassert(AudioBuffer<Type>::getNumChannels() == 1);

		sourceBuffer+=sourceStartSample;

		int ptrFinal = ptr + numSamples;
		if (ptrFinal<AudioBuffer<Type>::getNumSamples())
		{
			AudioBuffer<Type>::copyFrom(0,ptr,sourceBuffer,numSamples);
		}
		else
		{
			ptrFinal-=AudioBuffer<Type>::getNumSamples();
			const auto samplesToEnd=AudioBuffer<Type>::getNumSamples()-ptr;
			AudioBuffer<Type>::copyFrom(0,ptr,sourceBuffer,samplesToEnd);
			AudioBuffer<Type>::copyFrom(0,0,sourceBuffer+samplesToEnd,ptrFinal);
		}
		ptr=ptrFinal;
	}

	template<class SourceType>
	void pushBuffer(SourceType* sourceBufferLeft, SourceType* sourceBufferRight, const int sourceStartSample, const int numSamples)
	{
		jassert(numSamples < AudioBuffer<Type>::getNumSamples());
		jassert(sourceStartSample >= 0);
		jassert(AudioBuffer<Type>::getNumChannels() == 2);

		sourceBufferLeft+=sourceStartSample;
		sourceBufferRight+=sourceStartSample;

		int ptrFinal = ptr + numSamples;
		if (ptrFinal<AudioBuffer<Type>::getNumSamples())
		{
			AudioBuffer<Type>::copyFrom(0,ptr,sourceBufferLeft,numSamples);
			AudioBuffer<Type>::copyFrom(1,ptr,sourceBufferRight,numSamples);
		}
		else
		{
			ptrFinal-=AudioBuffer<Type>::getNumSamples();
			const auto samplesToEnd=AudioBuffer<Type>::getNumSamples()-ptr;
			AudioBuffer<Type>::copyFrom(0,ptr,sourceBufferLeft,samplesToEnd);
			AudioBuffer<Type>::copyFrom(1,ptr,sourceBufferRight,samplesToEnd);
			AudioBuffer<Type>::copyFrom(0,0,sourceBufferLeft+samplesToEnd,ptrFinal);
			AudioBuffer<Type>::copyFrom(1,0,sourceBufferRight+samplesToEnd,ptrFinal);
		}
		ptr=ptrFinal;
	}

	template<class SourceType>
	void pushBuffer(AudioBuffer<SourceType> &source, const int numChannels, const int sourceStartSample, const int numSamples)
	{
		jassert(numChannels <= source.getNumChannels()
			&& numChannels <= AudioBuffer<Type>::getNumChannels());
		jassert(sourceStartSample < source.getNumSamples());
		jassert(sourceStartSample + numSamples <= source.getNumSamples()
			&& numSamples <= AudioBuffer<Type>::getNumSamples());

		switch (AudioBuffer<Type>::getNumChannels()) {
		case 1: {
			jassert(source.getNumChannels()==1);
			pushBuffer(source.getReadPointer(0), sourceStartSample, numSamples);
			break;
		}
		case 2: {
			jassert(source.getNumChannels()<=2);
			pushBuffer(source.getReadPointer(0), source.getReadPointer(jmin(1, numChannels - 1)), sourceStartSample, numSamples);
			break;
		}
		default: {
			jassertfalse; //only mono and stereo signals are supported
			break;
		}
		}
	}

	template<class SourceType>
	void pushBuffer(AudioBuffer<SourceType> &source)
	{
		pushBuffer<SourceType>(source, source.getNumChannels(), 0, source.getNumSamples());
	}

	template<class SourceType>
	void pushBuffer(AudioBuffer<SourceType> &source,const int sourceStartSample, const int numSamples)
	{
		pushBuffer<SourceType>(source, source.getNumChannels(), sourceStartSample, numSamples);
	}

	virtual Type get(int channel, int delay) const 
	{
		jassert(delay<AudioBuffer<Type>::getNumSamples());
		jassert(channel<AudioBuffer<Type>::getNumChannels());
		int pos=ptr - delay - 1;
		if (pos<0) pos+=AudioBuffer<Type>::getNumSamples();
		return AudioBuffer<Type>::getSample(channel,pos);
	}

	virtual Type get(int delay) const 
	{
		jassert(AudioBuffer<Type>::getNumChannels() == 1);
		return get(0, delay);
	}

    // extract numSamples with a certain delay from the CircularBuffer
	// and start writing them at destinationStartSample
	template<class DestinationType>
	void getBuffer(int delay, AudioBuffer<DestinationType> &destination, int destinationStartSample, int numSamples)
	{
		jassert(destinationStartSample+numSamples<=destination.getNumSamples());
		jassert(destination.getNumSamples()<=AudioBuffer<Type>::getNumSamples());
		jassert(delay+numSamples<=AudioBuffer<Type>::getNumSamples());

		int endPtr=ptr-delay;
		if (delay && endPtr<0)
			endPtr+=AudioBuffer<Type>::getNumSamples();

		int ptrFinal = endPtr - numSamples;
		if (ptrFinal >= 0)
		{
			destination.copyFrom(0,destinationStartSample,*this,0,ptrFinal,numSamples);
			if (destination.getNumChannels() > 1)
			{
				destination.copyFrom(1,destinationStartSample,*this,jmin(1,AudioBuffer<Type>::getNumChannels()-1),ptrFinal,numSamples);
			}
		}
		else
		{
			ptrFinal += AudioBuffer<Type>::getNumSamples();

			// samples from ptrFinal to the end of the circular buffer
			numSamples-=endPtr;
			destination.copyFrom(0,destinationStartSample,*this,0,ptrFinal,numSamples);
			if (destination.getNumChannels() > 1)
			{
				destination.copyFrom(1,destinationStartSample,*this,jmin(1,AudioBuffer<Type>::getNumChannels()-1),ptrFinal,numSamples);
			}

			// samples continuing at the start of the circular buffer until endPtr
			destinationStartSample+=numSamples;
			destination.copyFrom(0,destinationStartSample,*this,0,0,endPtr);
			if (destination.getNumChannels() > 1)
			{
				destination.copyFrom(1,destinationStartSample,*this,jmin(1,AudioBuffer<Type>::getNumChannels()-1),0,endPtr);
			} 
		}
	}

	// extract the last destination.getNumSamples() of the CircularBuffer
	template<class DestinationType>
	void getBuffer(AudioBuffer<DestinationType> &destination)
	{
		getBuffer(0,destination,0,destination.getNumSamples());
	}

	// extract destination.getNumSamples() with a certain delay from the CircularBuffer
	template<class DestinationType>
	void getBuffer(int delay, AudioBuffer<DestinationType> &destination)
	{
		getBuffer(delay,destination,0,destination.getNumSamples());
	}
};

/**
Circular buffer optimized to push samples and get the last pushed samples    
*individually* (it is created with a power of 2 size bigger than numOfSamples 
to be able to use a binary mask for the modulo).
It supports numOfSamples < 2^30 = 1073741824.
*/
template<class Type = float>
class P2CircularAudioBuffer : public CircularAudioBuffer<Type> {
	// we can use lastPosition = nextPowerOfTwo(numOfSamples) - 1 as the mask to do the modulo
public:
	P2CircularAudioBuffer(int numChannels, int numOfSamples)
		:CircularAudioBuffer<Type>(numChannels, nextPowerOfTwo(numOfSamples))
	{
		// nextPowerOfTwo supports numOfSamples < 2^30 = 1073741824
		jassert(numOfSamples <= 1073741824);
	}

	void setSize(int newNumChannels,
		int numOfSamples,
		bool keepExistingContent = false,
		bool clearExtraSpace = false,
		bool avoidReallocating = true) override
	{
		const auto binaryNumOfSamples = nextPowerOfTwo(numOfSamples);
		// nextPowerOfTwo supports numOfSamples < 2^30 = 1073741824
		jassert(numOfSamples < 1073741824);
		CircularAudioBuffer<Type>::setSize(newNumChannels, binaryNumOfSamples, keepExistingContent, clearExtraSpace, avoidReallocating);
	}
	
	void push(const Type source) override
	{
		jassert(AudioBuffer<Type>::getNumChannels() == 1);

		AudioBuffer<Type>::setSample(0,  CircularAudioBuffer<Type>::ptr, source);
		CircularAudioBuffer<Type>::ptr=CircularAudioBuffer<Type>::lastPosition & ++CircularAudioBuffer<Type>::ptr;
	}

	void push(const Type sourceLeft, const Type sourceRight) override
	{
		jassert(AudioBuffer<Type>::getNumChannels() == 2);

		AudioBuffer<Type>::setSample(0, CircularAudioBuffer<Type>::lastPosition & CircularAudioBuffer<Type>::ptr, sourceLeft);
		AudioBuffer<Type>::setSample(1, CircularAudioBuffer<Type>::lastPosition & CircularAudioBuffer<Type>::ptr, sourceRight);
		CircularAudioBuffer<Type>::ptr=CircularAudioBuffer<Type>::lastPosition & ++CircularAudioBuffer<Type>::ptr;
	}

	Type get(int channel, int delay) const override 
	{
		jassert(channel<AudioBuffer<Type>::getNumChannels());
		return AudioBuffer<Type>::getSample(channel, (CircularAudioBuffer<Type>::ptr - delay - 1) & CircularAudioBuffer<Type>::lastPosition);
	}

	Type get(int delay) const override 
	{
		jassert(AudioBuffer<Type>::getNumChannels() == 1);
		return get(0, delay);
	}
};

[Prelinquisite]

That’s super cool of you to donate your circular buffer code, especially since JUCE lacks this feature. Using sizes that are powers of 2 for performance is a smart move. I’m sure lots of folks will find it super useful.

[CrushedPixel]

Did you do any benchmarking/comparison of the approaches for different use cases yet? I’m curious about the results…

[Qfactor]

I didn’t have time to do so, I have other priorities at the moment. If somebody does it, I’d also be curious about the results!