A Quite Simple Memory Pool in C#
Published: 2020-12-28 08:45:04

This article shows a quite simple memory pool to make a thread-unsafe library thread-safe without performance degradation in single-threaded programs. Same as [the previous article](https://dev.to/fujieda/nan-boxing-in-c-to-realize-a-fast-json-parser-3am8), this article is about DynaJson.

Thread-safety requires overhead to allocate an instance by each invocation to isolate data being altered. Unless thread-safety is required, we can use a static class or a singleton to eliminate any additional allocation.

When I made DynaJson thread-safe, I adopted a memory pool to avoid the allocations in single-threaded programs. When a program start, DynaJson allocates one instance in the memory pool. In single-threaded programs, DynaJson repeatedly rents and returns the instance from/to the pool. In multi-threaded programs, DynaJson allocates additional instances only when more than one thread uses DynaJson at the same time because the memory pool gets empty.

As for a memory pool, there is an implementation on the .NET platform, that is, [`MemoryPool<T>`](https://docs.microsoft.com/en-us/dotnet/api/system.buffers.memorypool-1?view=net-5.0). But .NET Standard 2.0, an API set that DynaJson uses, doesn't have the class. So I originally implemented a memory pool.

In implementing a memory pool, we need to care how the speed of the operations gets much faster than the allocations. We mainly use locks to implement thread-safe data structures. But locks are slower than the allocations, so we must implement a memory pool in a lock-free way.

In C#, most implementations of lock-free data structures use [`Interlocked.CompareExchange`](https://docs.microsoft.com/en-us/dotnet/api/system.threading.interlocked.compareexchange?view=net-5.0). [This article](https://secondboyet.com/Articles/LockfreeStack.html) shows a lock-free stack implemented with the method. I implemented a quite simple memory pool referring to this stack as follows.

```csharp
internal class BufferPool<T>
{
    private class Node
    {
        public Node Next;
        public T Item;
    }

    private readonly Node _head = new Node();

    public void Return(T item)
    {
        var node = new Node {Item = item};
        do
        {
            node.Next = _head.Next;
        } while (Interlocked.CompareExchange(ref _head.Next, node, node.Next) != node.Next);
    }

    public T Rent()
    {
        Node node;
        do
        {
            node = _head.Next;
            if (node == null)
                return default;
        } while (Interlocked.CompareExchange(ref _head.Next, node.Next, node) != node);
        return node.Item;
    }
}
```

I have to say this is a poor implementation because it causes another allocation whenever an application returns an instance. Nevertheless, the size of the allocated instance is only 16 bytes, so that this memory pool can reduce the overall cost of the allocations in DynaJson.

The following chart compares the times to parse a simple JSON `{"X":1234.5,"Y":5.6789,"Name":"Sakura"}` without and with the memory pool. The memory pool reduces the processing time by 203 ns.

![benchmark-memory-pool](https://dev-to-uploads.s3.amazonaws.com/i/08wcbbykmuyuoz89ebnm.png)