Dynamic Buffers

ArrayBufferWriter<T> represents default implementation of dynamically-sized, heap-based and array-backed buffer. Unfortunately, it's not flexible enough in the following aspects:

  • Not possible to use array or memory pooling mechanism. As a result, umnanaged memory cannot be used for such writer.
  • Not compatible with ArraySegment<T>
  • No easy way to obtain stream over written memory
  • Allocation on the heap

With .NEXT, you have this flexibility.

PooledBufferWriter

PooledBufferWriter<T> is similar to ArrayBufferWriter but accepts memory allocator that is used for allocation of internal buffers. Thus, you can use any pooling mechanism from .NET: memory or array pool. If writer detects that capacity exceeded then it rents a new internal buffer and copies written content from previous one.

using DotNext.Buffers;

using var writer = new PooledBufferWriter<byte>(ArrayPool<byte>.Shared.ToAllocator());
Span<byte> span = writer.GetSpan(1024);
new byte[512].AsSpan().CopyTo(span);
span.Advance(512);
var result = writer.WrittenMemory;  //length is 512

In contrast to ArrayBufferWriter, you must not use written memory if Dispose is called. When Dispose method is called, the internal buffer returns to the pool.

PooledArrayBufferWriter

PooledArrayBufferWriter<T> class exposes the similar functionality to PooledBufferWriter class but specialized for working with ArrayPool<T>. As a result, you can make writes or obtain written memory using ArraySegment<T>.

using DotNext.Buffers;
using DotNext.IO;
using System;

using var writer = new PooledArrayBufferWriter<byte>(ArrayPool<byte>.Shared);
ArraySegment<byte> array = writer.GetArray(1024);
array[0] = 42;
array[1] = 43;
span.Advance(2);
ArraySegment<byte> result = writer.WrittenArray;

Additionally, it implements IList<T> interface so you can use it as fully-functional list which rents the memory instead of allocation on the heap.

Sparse Buffer

SparseBufferWriter<T> represents a writer for the buffer represented by a set of non-contiguous memory blocks. Its main advantage over previously described buffer types is a monotonic growth without reallocations. If the buffer has not enough space to place a new portion of data then it just allocates another contiguous buffer from the pool and attaches it to the end of the chain of buffers. Thus, the buffer growth has deterministic performance.

Additionally, sparse buffer allows to import memory blocks without copying them to the rented buffer. For instance, a memory block represented by ReadOnlyMemory<T> can be intermixed with the memory blocks rented by the sparse buffer internally.

using DotNext.Buffers;
using System;

var array = new byte[] { 10, 20, 30 };
using var writer = new SparseBufferWriter<byte>();
writer.Write(array.AsMemory(), false);  // false means that the memory block must be inserted into sparse buffer as-is without copying its content to the internal buffer

Sparse buffer writer also implements IBufferWriter<T> interface as well as other buffer writers mentioned above. However, this interface is implemented explicitly and its methods should be used with care. Major drawback of this buffer type is that it can produce memory holes, i.e. unused memory segments in the middle of the buffer chunks. The holes can be caused by IBufferWriter<T>.GetMemory(int) or IBufferWriter<T>.GetSpan(int) implementations. Therefore these methods are implemented explicitly. All other public methods of SparseBufferWriter<T> class cannot cause memory holes.

Suppose that sparse buffer has rented memory block of size 1024 bytes, and 1000 bytes of them already occupied. If you want to write a block of size 100 bytes represented by ReadOnlySpan<T> then use SparseBufferWriter<T>.Write(ReadOnlySpan<T>) method. It writes the first 24 bytes to the existing memory block and then rents a new segment to store the rest of the input buffer, 76 bytes. Therefore, Write method cannot cause fragmentation of memory blocks. However, if we want to obtain a memory block for writing via GetMemory(int) method then sparse buffer cannot utilize 24 bytes of free memory from the existing chunk because the returned buffer must be at least 100 bytes of contiguous memory. In this case, sparse buffer rents a new chunk with the size of at least 100 bytes and marks 24 bytes from the previous chunk as unused.

The implementation of GetMemory(int) and GetSpan(int) methods are optimized to reduce the number of such memory holes. However, due to nature of sparse buffer data structure, it is not possible in 100% cases. Nevertheless, such overhead can be acceptable because sparse buffer never reallocates the existing memory and may work faster than PooledBufferWriter<T> which requires reallocation when rented memory block is not enough to place a new data.

Additionally, you can use Stream-based API to read from or write to the sparse buffer. StreamSource provides AsStream extension method that can be used to create readable or writable stream over the buffer:

using DotNext.Buffers;
using DotNext.IO;

using var buffer = new SparseBufferWriter<byte>();
using Stream writable = buffer.AsStream(false); // create writable stream
using Stream readable = buffer.AsStream(true);  // create readable stream

Sparse buffer supports various strategies for allocation of the memory chunks:

  1. Default behavior when size of each memory chunk is the same
  2. Linear growth, when the size of each new memory chunk is a multiple of the chunk index
  3. Exponential growth, when each new memory chunk doubles in size

The first strategy is effective when potential max size of the resulting buffer is hundreds of elements and volatility is small. The last two are effective when max size of the result buffer can be potentially large (kilobytes) and volatility is unpredictable.

The following example demonstrates usage of exponential growth strategy with predefined size of initial memory chunk:

using DotNext.Buffers;

using var buffer = new SparseBufferWriter<byte>(256, SparseBufferGrowth.Exponential);

Char Buffer

StringBuilder is a great tool from .NET standard library to construct strings dynamically. However, it uses heap-based allocation of chunks and increases GC workload. The solution is to use pooled memory for growing buffer and release it when no longer needed. This approach is implemented by PooledBufferWriter<T>, PooledArrayBufferWriter<T> and SparseBufferWriter<T> classes as described above. But we need suitable methods for adding portions of data to the builder similar to the methods of StringBuilder. They are provided as extension methods declared in BufferWriter class for all objects implementing IBufferWriter<char> interface:

using DotNext.Buffers;

using var writer = new PooledArrayBufferWriter<char>(ArrayPool<char>.Shared);
writer.Write("Hello,");
writer.Write(' ');
writer.Write("world!");
writer.WriteLine();
writer.Write(2);
writer.Write('+');
writer.Write(2);
writer.Write('=');
writer.Write(4);

string result = writer.BuildString();

TextWriter is a common way to produce text dynamically and recognizable by many third-party libraries. There is a bridge that allow to use TextWriter API over pooled buffer writer with help of extension methods declared in TextStreamExtensions class:

using DotNext.Buffers;
using System.IO;
using static DotNext.IO.TextWriterExtensions;

using var buffer = new PooledArrayBufferWriter<char>(ArrayPool<char>.Shared);
using TextWriter writer = buffer.AsTextWriter();
writer.Write("Hello,");
writer.Write(' ');
writer.Write("world!");
writer.WriteLine();
writer.Write(2);
writer.Write('+');
writer.Write(2);
writer.Write('=');
writer.Write(4);

string result = buffer.BuildString();

BufferWriterSlim

BufferWriterSlim<T> is a lightweight version of PooledBufferWriter<T> class with its own unique features. The instance of writer always allocated on the stack because the type is declared as ref-like value type. Additionally, the writer allows to use stack-allocated memory for placing new elements.

If initial buffer overflows then BufferWriterSlim<T> obtains rented buffer from the pool and copies the initial buffer into it.

using DotNext.Buffers;

using var builder = new BufferWriterSlim<byte>(stackalloc byte[128]); // capacity can be changed at runtime
builder.Write(new byte[] { 1, 2, 3 });
ReadOnlySpan<byte> result = builder.WrittenSpan;

This type has the following limitations:

What to choose?

The following table describes the main differences between various growable buffer types:

Buffer Writer When to use Compatible with async methods Space complexity (write operation)
PooledArrayBufferWriter<T> General applicability when initial capacity is known Yes o(1), O(n)
PooledBufferWriter<T> If custom memory allocator is required. For instance, if you want to use unmanaged memory pool Yes o(1), O(n)
BufferWriterSlim<T> If you have knowledge about optimal size of initial buffer which can be allocated on the stack. In this case the writer allows to avoid renting the buffer and doesn't allocate itself on the managed heap No o(1), O(n)
SparseBufferWriter<T> If optimal size of initial buffer is not known and the length of the written data varies widely Yes o(1), O(1)