In .Net existiert eine Vielzahl von Klassen zur Auflistung von Objekten oder Strukturen. Ein einfaches und häufig verwendetes Beispiel ist die Array. Die List<T> ist ebenso stark verbreitet. Daneben gibt es eine Vielzahl von Klassen, welche diverse Spezialfälle abbilden. So etwa für parallelen Zugriff mit den Klassen aus dem Namespace System.Collections.Concurrent. Einen Spezialfall hätte ich allerdings schon häufiger vermisst: Den RingBuffer (oder auch Circular Buffer [1]). Ein RingBuffer dient dazu, eine fortlaufende Liste mit einer maximalen Länge abzubilden. Wenn über die maximale Länge hinaus geschrieben wird, so werden einfach die ältesten Elemente überschrieben. Gehen wir von der max. Länge von 100 aus. Wenn das 101. Element hinzugefügt wird, fliegt das erste Element raus. Dieses neue Element ist dann aber nicht der neue Start der Liste. Der Start der Liste ist immer das älteste Element. Wo benötigt man so ein Verhalten? Ein gutes Beispiel dazu habe ich in der 3D-Engine SeeingSharp. Zur Berechnung der durchschnittlichen FPS (Frames per Second bzw. Bilder pro Sekunde) wird der aktuelle FPS Wert je Sekunde berechnet und an einer Liste angehängt. Nachdem diese Liste eine bestimmte Länge erreicht hat, wird mit jedem neuen Wert der älteste Eintrag entfernt. Die durchschnittlichen FPS ergeben sich anschließend mittels des Durchschnittswerts aller Elemente in der Liste. Mit einer List<T> könnte man dieses Verhalten per Add und RemoveAt(0) relativ einfach abbilden, bei einem RingBuffer dagegen steckt dieses Verhalten bereits im Add. Dazu gibt es beim RingBuffer noch weitere Vorteile aus Sicht der Performance, doch dazu im Verlauf dieses Artikels mehr.
Inhaltsverzeichnis
Das Problem bei List<T>
Gehen wir zunächst von einer List<T> aus. Nachfolgender Codeausschnitt zeigt, wie sich das beschriebene Verhalten mit einer List<T> abbilden lassen würde.
var myList = new List<int>(100);
// ...
if(myList.Count > 100){ myList.RemoveAt(0); }
myList.Add(newValue);
Zunächst wird eine List<int> mit einer Kapazität von 100 erzeugt. An einer anderen Stelle im Code werden neue Elemente hinzugefügt und dabei darauf geachtet, dass die Liste nie mehr als 100 Einträge hat. Das RemoveAt(0) entfernt zu diesem Zweck den ältesten Eintrag in der Liste, falls die Liste bereits 100 Einträge umfasst. Soweit, so einfach. Das RemoveAt(0) ist von der technischen Seite allerdings nicht ganz ohne. Unter der Haube ist eine List<T> nämlich als Array implementiert. Wenn nun das erste Element gelöscht wird, müssen alle darauf folgenden Einträge um einen Index verschoben werden (per Copy). Der Folgende Codeausschnitt zeigt die Implementierung von RemoveAt, Quelle ist dabei das coreclr Projekt auf GitHub [2]. In Zeile 12 ist der zugehörige Copy-Befehl. In unserem Fall bedeutet das, dass 99 Einträge um einen Eintrag nach links kopiert werden.
// Removes the element at the given index. The size of the list is
// decreased by one.
public void RemoveAt(int index)
{
if ((uint)index >= (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRange_IndexException();
}
_size--;
if (index < _size)
{
Array.Copy(_items, index + 1, _items, index, _size - index);
}
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
_items[_size] = default!;
}
_version++;
}
Bei einem RingBuffer ist dieses Verhalten dagegen deutlich günstiger. Die Idee hier ist, dass bei einem RingBuffer von vorne herein eine Auflistung mit der maximalen Kapazität des RingBuffers existiert. Der Start-Index ist aber nicht dauerhaft der Index 0, stattdessen verschiebt er sich, sobald das Ende der Auflistung erreicht wird. Im gleichen Zuge werden Add-Aufrufe nach dem Ende der Auflistung wieder an deren Anfang angewendet. Daher auch der Begriff “Ring”. Ähnlich wie ein Ring hat auch der RingBuffer zwar eine feste Länge, aber kein wirkliches Ende. Hat man das Ende erreicht, so befindet man wieder am Anfang.
Implementierung in SeeingSharp
Nachfolgender Codeausschnitt zeigt die Implementierung des RingBuffer in SeeingSharp. Der Code liegt auf GitHub unter [3]. An den Membern in den Zeilen 15 bis 17 lässt sich gut erkennen, dass sich der RingBuffer im Hintergrund zum einen die Array für alle Elemente (in Maximallänge) und den aktuellen Startindex merkt. Der Indexer in Zeile 22 verwendet den aktuellen Startindex, um auf dessen Basis die Position des angefragten Elements zu finden. Wie weiter oben schon beschrieben, verschiebt sich der StartIndex immer dann, wenn nach dem Erreichen der maximalen Länge des RingBuffer weiter geschrieben wird. Die zugehörige Logik dazu befindet sich in der Methode Add ab Zeile 61. StartIndex zeigt somit immer auf das älteste Element. Für denjenigen, der den RingBuffer verwendet, ist das älteste Element immer Index=0.
using System;
using SeeingSharp.Checking;
namespace SeeingSharp.Util
{
/// <summary>
/// This is a simple RingBuffer implementation for SeeingSharp,
/// originally created for the Input event system.
///
/// More info on cyclic buffers: https://en.wikipedia.org/wiki/Circular_buffer
/// </summary>
public class RingBuffer<T>
{
// all buffer properties
private T?[] _buffer;
private int _itemStart;
private int _itemLength;
/// <summary>
/// Gets the object at the specified index.
/// </summary>
public T this[int index]
{
get
{
if (index < 0){ throw new IndexOutOfRangeException(); }
if (index >= _itemLength) { throw new IndexOutOfRangeException(); }
return _buffer[(_itemStart + index) % _buffer.Length]!;
}
}
/// <summary>
/// Gets the total count of items.
/// </summary>
public int Count => _itemLength;
/// <summary>
/// Gets the maximum capacity of the buffer.
/// </summary>
public int MaxCapacity => _buffer.Length;
/// <summary>
/// Initializes a new instance of the <see cref="RingBuffer{T}"/> class.
/// </summary>
/// <param name="maxItemCount">The maximum count of items.</param>
public RingBuffer(int maxItemCount)
{
maxItemCount.EnsureInRange(2, int.MaxValue, nameof(maxItemCount));
_buffer = new T[maxItemCount];
_itemStart = 0;
_itemLength = 0;
}
/// <summary>
/// Adds a new item to the buffer and overrides the oldest item
/// if the count of items reached the maximum.
/// </summary>
/// <param name="newItem">The new item to be added.</param>
public void Add(T newItem)
{
if (_itemLength < _buffer.Length)
{
_buffer[(_itemStart + _itemLength) % _buffer.Length] = newItem;
_itemLength++;
}
else
{
_itemStart = (_itemStart + 1) % _buffer.Length;
var nextIndex = _itemStart - 1;
if (nextIndex < 0) { nextIndex = _buffer.Length - 1; }
_buffer[nextIndex] = newItem;
}
}
// ...
/// <summary>
/// Removes the first entry.
/// </summary>
public void RemoveFirst()
{
if (_itemLength == 0)
{
throw new IndexOutOfRangeException();
}
_itemStart++;
_itemLength--;
if (_itemStart == _buffer.Length)
{
_itemStart = 0;
}
}
/// <summary>
/// Clears this collection.
/// </summary>
public void Clear()
{
_itemLength = 0;
_itemStart = 0;
}
}
}
Vergleich mittels Benchark.Net
Nun stellt sich die Frage, wie viel der RingBuffer tatsächlich bringt (aus Performance-Sicht). Hierzu im nachfolgenden Codeausschnitt ein Benchmark mittels BenchmarkDotNet [4], welcher die Geschwindigkeit bei Add nach Erreichen der maximalen Größe der Auflistung vergleicht. Es wird mit verschiedenen Listengrößen getestet (10, 100, 1.000, 10.000 und 100.000 Elemente).
public class RingBufferBenchmark
{
[Params(10, 100, 1000, 10000, 100000)]
public int BufferSize;
private Random _random;
private RingBuffer<int> _ringBuffer;
private List<int> _list;
[GlobalSetup]
public void Setup()
{
_ringBuffer = new RingBuffer<int>(BufferSize);
_list = new List<int>(BufferSize);
_random = new Random(1000);
for (var loop = 0; loop < BufferSize; loop++)
{
_ringBuffer.Add(_random.Next(0, 1000));
_list.Add(_random.Next(0, 1000));
}
}
[Benchmark]
public void AddToRingBuffer()
{
_ringBuffer.Add(1000);
}
[Benchmark]
public void AddToList()
{
_list.RemoveAt(0);
_list.Add(1000);
}
}
Das Ergebnis im nachfolgenden Screenshot zeigt deutlich, dass der Performance-Gewinn bei längeren Auflistungen größer ist. Hintergrund ist oben angesprochener Array.Copy Aufruf, welcher innerhalb von RemoveAt der List<T> verwendet wird.
Fazit
RingBuffer ist sicher keine Klasse, die im Programmierer-Alltag ständig verwendet wird. Es gibt allerdings schon einige Spezialfälle, bei denen eine Auflistungsklasse mit diesem Verhalten zum einen etwas Coding spart (der RemoveAt), zum anderen auch besser performt. Das hier vorgestellte Beispiel kommt aus der Berechnung der durchschnittlichen FPS, aber auch für andere Messwerte wird der RingBuffer in SeeingSharp verwendet. So etwa für die Berechnung der durchschnittlichen Verarbeitungszeit verschiedener Methoden im Render-Prozess.
Verweise
- Allgemeine Infos zur Funktionsweise eines Circular Buffer
https://en.wikipedia.org/wiki/Circular_buffer - Quellcode der Liste<T>
https://github.com/dotnet/coreclr/blob/master/src/System.Private.CoreLib/shared/System/Collections/Generic/List.cs - Quellcode der eigenen RingBuffer Implementierung aus SeeingSharp
https://github.com/RolandKoenig/SeeingSharp2/blob/master/src/SeeingSharp/Util/_Collections/RingBuffer.cs - Website der populären Bencharking Bibliothek BenchmarkDotNet
https://benchmarkdotnet.org/