For an audio processing application I am sampling audio data into a delay line then convolving or cross-correlating in the time domain. For short delay lines it is possible to use the memmove function without having too great an impact on processor time. However, when the delay length increases to several thousand values the processing time required just to append a new sample can have a major impact on the application. I have a requirement to operate in real-time on delay lines of around 8000 values. Looking at the results below we can see how the append operation time varies with delay line length. The Mirrored Delay Line trades processing time for memory, needing double the memory but reducing the append operation time to a constant amount regardless of delay line length.

This speeds up the delay line append operation for very long delay lines whilst still allowing access to a single contiguous block of memory for convolution and cross-correlation operations.

Much like the Mirrored FIFO this approach was based on the techniques used in “virtual ring buffers” but without mapping virtual memory. For more information see: The Magic Ring Buffer and Circular (ring) buffer plus neat virtual memory mapping trick posts.

[code light=”true”]
$ ./test.exe
MirroredDelayLine example usage

Initialised delay line:
Contents=[0, 0, 0, 0, 0]
Appending.
0 data()-Contents=[0, 0, 0, 0, 0] [i]-Contents=[0, 0, 0, 0, 0]
1 data()-Contents=[0, 0, 0, 0, 1] [i]-Contents=[0, 0, 0, 0, 1]
2 data()-Contents=[0, 0, 0, 1, 2] [i]-Contents=[0, 0, 0, 1, 2]
3 data()-Contents=[0, 0, 1, 2, 3] [i]-Contents=[0, 0, 1, 2, 3]
4 data()-Contents=[0, 1, 2, 3, 4] [i]-Contents=[0, 1, 2, 3, 4]
5 data()-Contents=[1, 2, 3, 4, 5] [i]-Contents=[1, 2, 3, 4, 5]
6 data()-Contents=[2, 3, 4, 5, 6] [i]-Contents=[2, 3, 4, 5, 6]
7 data()-Contents=[3, 4, 5, 6, 7] [i]-Contents=[3, 4, 5, 6, 7]
8 data()-Contents=[4, 5, 6, 7, 8] [i]-Contents=[4, 5, 6, 7, 8]
9 data()-Contents=[5, 6, 7, 8, 9] [i]-Contents=[5, 6, 7, 8, 9]
Clearing.
Contents=[0, 0, 0, 0, 0]
Timing comparisons.
delayLineLength=100
repetitions=100000000
Starting timing comparison: Naive
Starting timing comparison: Memmove
Starting timing comparison: Mirrored Delay Line
Time per delay line append operation.
Naive = 510.44 ns
Memmove = 28.08 ns
Mirrored Delay Line = 10.76 ns
Timing comparisons.
delayLineLength=2000
repetitions=10000000
Starting timing comparison: Naive
Starting timing comparison: Memmove
Starting timing comparison: Mirrored Delay Line
Time per delay line append operation.
Naive = 10141.6 ns
Memmove = 193.5 ns
Mirrored Delay Line = 10.9 ns
Timing comparisons.
delayLineLength=8000
repetitions=10000000
Starting timing comparison: Naive
Starting timing comparison: Memmove
Starting timing comparison: Mirrored Delay Line
Time per delay line append operation.
Naive = 40613.3 ns
Memmove = 631.8 ns
Mirrored Delay Line = 11 ns
[/code]

Sourcecode follows:

[code language=”cpp” collapse=”true” title=”main.cpp”]
//——————————————————————————
// The MIT License (MIT)
//
// Copyright (c) 2015 Benjamin Sherlock
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
//——————————————————————————
//
// main.cpp
//
//——————————————————————————
//
// This has been tested using cygwin and x86_64-w64-mingw32-g++.
//
// Compile: g++ main.cpp -o test.exe -lm -static
// Run: ./test.exe
//
//——————————————————————————

// Includes
#include <ctime>
#include <iostream>
#include "MirroredDelayLine.h"

void doTimingComparisons(size_t delayLineLength, int repetitions);

//! Main Function
int main(int argc, char** argv)
{
std::cout << "MirroredDelayLine example usage" << std::endl << std::endl;

size_t delayLineLength = 5;

std::vector<int> values(delayLineLength*2);
for( size_t i = 0; i < values.size(); i++ )
{
values[i] = i;
}

// Create a MirroredDelayLine
MirroredDelayLine<int> intDelayLine(delayLineLength, 0);

std::cout << "Initialised delay line: " << std::endl;
std::cout << "Contents=";
intDelayLine.debug_printContents();

std::cout << "Appending." << std::endl;
for( size_t i = 0; i < values.size(); i++ )
{
intDelayLine.append( values[i] );
std::cout << i << " data()-Contents=[";
for(size_t index = 0; index < intDelayLine.length(); index++ )
{
std::cout << intDelayLine.data()[index];
if( index < (intDelayLine.length()-1) )
{
std::cout << ", ";
}
}
std::cout << "]";

std::cout << " [i]-Contents=[";
for(size_t index = 0; index < intDelayLine.length(); index++ )
{
std::cout << intDelayLine[index];
if( index < (intDelayLine.length()-1) )
{
std::cout << ", ";
}
}
std::cout << "]" << std::endl;

}

std::cout << "Clearing." << std::endl;
intDelayLine.clear(0);
std::cout << "Contents=";
intDelayLine.debug_printContents();

// Timing Comparisons with naive for(i=0 to length) move, memmove and mirrored delay line.
//size_t delayLineLength;
int repetitions;

delayLineLength = 100;
repetitions = 100000000;
doTimingComparisons(delayLineLength, repetitions);

delayLineLength = 2000;
repetitions = 10000000;
doTimingComparisons(delayLineLength, repetitions);

delayLineLength = 8000;
repetitions = 10000000;
doTimingComparisons(delayLineLength, repetitions);

return 0;
}

void doTimingComparisons(size_t delayLineLength, int repetitions)
{
//size_t delayLineLength = 2000;
//int repetitions = 10000000;
double repetitionsDouble = (double)repetitions;

// Create the structures
std::vector<int> intVector(delayLineLength, 0);
MirroredDelayLine<int> intDelayLine(delayLineLength, 0);

// The times
std::clock_t startTime;
std::clock_t endTime;

double naiveTimeNs;
double memmoveTimeNs;
double mirrorTimeNs;

std::cout << "Timing comparisons." << std::endl;
std::cout << "delayLineLength=" << delayLineLength << std::endl;
std::cout << "repetitions=" << repetitions << std::endl;

std::cout << "Starting timing comparison: Naive" << std::endl;

//
// Naive
//
// Start the time
startTime = std::clock();

for( int r = 0; r < repetitions; r++ )
{
// Append r
for(size_t i = 0; i < delayLineLength-1; i++)
{
intVector[i] = intVector[i+1];
}
intVector[delayLineLength-1] = r;
}

// Stop the time
endTime = std::clock();
// Duration
naiveTimeNs = (1000000000.0 * (double)(endTime – startTime) / (double)CLOCKS_PER_SEC) / repetitionsDouble;

std::cout << "Starting timing comparison: Memmove" << std::endl;

//
// Memmove
//
// Start the time
startTime = std::clock();

for( int r = 0; r < repetitions; r++ )
{
// Append r
memmove(&intVector[0], &intVector[1], delayLineLength-1);
intVector[delayLineLength-1] = r;
}

// Stop the time
endTime = std::clock();
// Duration
memmoveTimeNs = (1000000000.0 * (double)(endTime – startTime) / (double)CLOCKS_PER_SEC) / repetitionsDouble;

std::cout << "Starting timing comparison: Mirrored Delay Line" << std::endl;

//
// Mirrored Delay Line
//
// Start the time
startTime = std::clock();

for( int r = 0; r < repetitions; r++ )
{
// Append r
intDelayLine.append(r);
}

// Stop the time
endTime = std::clock();
// Duration
mirrorTimeNs = (1000000000.0 * (double)(endTime – startTime) / (double)CLOCKS_PER_SEC) / repetitionsDouble;

std::cout << "Time per delay line append operation. " << std::endl;
std::cout << "Naive = " << naiveTimeNs << " ns" << std::endl;
std::cout << "Memmove = " << memmoveTimeNs << " ns" << std::endl;
std::cout << "Mirrored Delay Line = " << mirrorTimeNs << " ns" << std::endl;

return;
}
[/code]

[code language=”cpp” collapse=”true” title=”MirroredDelayLine.h”]
//——————————————————————————
// The MIT License (MIT)
//
// Copyright (c) 2015 Benjamin Sherlock
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
//——————————————————————————
//
// MirroredDelayLine.h
//
//——————————————————————————
//
// It uses a variation on the "virtual ring buffer" technique, though instead of
// mapped memory it is a direct copy in contiguous memory. This allows block reads
// from contiguous memory.
// http://atastypixel.com/blog/circular-ring-buffer-plus-neat-virtual-memory-mapping-trick/
// https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/
//
//——————————————————————————

#ifndef MIRROREDDELAYLINE_H
#define MIRROREDDELAYLINE_H

#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>

template <typename DataType>
class MirroredDelayLine
{
public:

//! Constructor
//! delayLineLength = the length of the delay line
MirroredDelayLine(size_t delayLineLength);

//! Constructor
//! delayLineLength = the length of the delay line.
//! clearValue = the value to initialise the contents to.
MirroredDelayLine(size_t delayLineLength, const DataType& clearValue);

//! Destructor
virtual ~MirroredDelayLine();

//! Clear the delay line
//! clearValue = the value to initialise the contents to.
void clear(const DataType& clearValue);

//! Get the length of the delay line
size_t length();

//! Get a pointer to the current head of the delay line
const DataType * const data();

//! Append data to end of delay line (and lose the first item)
void append(const DataType &data);

//! Array Subscript Operator Overload
const DataType& operator[](size_t index);

//! Debug: Print the contents to std::cout
void debug_printContents();

protected:

private:
//! Usable Delay Line Length
size_t m_delayLineLength;

//! Total Storage Length
size_t m_totalStorageLength;

//! Storage Vector
std::vector<DataType> m_storage;

//! Index
size_t m_index;

}; // class MirroredDelayLine

//! Constructor
template <typename DataType>
MirroredDelayLine<DataType>::MirroredDelayLine(size_t delayLineLength)
: m_delayLineLength(delayLineLength), m_totalStorageLength(2*m_delayLineLength),
m_storage(m_totalStorageLength), m_index(0)
{
}

//! Constructor
//! delayLineLength = the length of the delay line.
//! clearValue = the value to initialise the contents to.
template <typename DataType>
MirroredDelayLine<DataType>::MirroredDelayLine(size_t delayLineLength, const DataType& clearValue)
: m_delayLineLength(delayLineLength), m_totalStorageLength(2*m_delayLineLength),
m_storage(m_totalStorageLength, clearValue), m_index(0)
{
}

//! Destructor
template <typename DataType>
MirroredDelayLine<DataType>::~MirroredDelayLine()
{
}

//! Clear the delay line
//! clearValue = the value to initialise the contents to.
template <typename DataType>
void MirroredDelayLine<DataType>::clear(const DataType& clearValue)
{
m_index = 0;
memset(&m_storage[0], clearValue, m_totalStorageLength*sizeof(DataType));
}

//! Get the length of the delay line
template <typename DataType>
size_t MirroredDelayLine<DataType>::length()
{
return m_delayLineLength;
}

//! Get a pointer to the current head of the delay line
template <typename DataType>
const DataType * const MirroredDelayLine<DataType>::data()
{
return &m_storage[m_index];
}

//! Append data to end of delay line (and lose the first item)
template <typename DataType>
void MirroredDelayLine<DataType>::append(const DataType &data)
{
m_storage[m_index] = data;
m_storage[m_index+m_delayLineLength] = data;

m_index++;
if( m_index == m_delayLineLength )
{
// Wrap around
m_index = 0;
}
}

//! Array Subscript Operator Overload – read only
template <typename DataType>
const DataType& MirroredDelayLine<DataType>::operator[](size_t index)
{
return m_storage[index + m_index];
}

//! Debug: Print the contents to std::cout
template <typename DataType>
void MirroredDelayLine<DataType>::debug_printContents()
{
std::cout << "[";

for( size_t i = 0; i < m_delayLineLength; i++ )
{
std::cout << m_storage[m_index+i];

if( i < (m_delayLineLength-1) )
{
std::cout << ", ";
}
}

std::cout << "]" << std::endl;
}

#endif // MIRROREDSHIFTBLOCK_H
[/code]