Buffer Allocation Strategies – Explaining the solution

In my previous post, I threw a bunch a code at you, with no explanation, and asked you to discuss it.

Here is the code, with full discussion below.

[ThreadStatic] private static Stack<byte[]>[] _buffersBySize;
    private static byte[] GetBuffer(int requestedSize)
    {
        if(_buffersBySize == null)
            _buffersBySize = new Stack<byte[]>[32];
        var actualSize = PowerOfTwo(requestedSize);
        var pos = MostSignificantBit(actualSize);
        if(_buffersBySize[pos] == null)
            _buffersBySize[pos] = new Stack<byte[]>();
        if(_buffersBySize[pos].Count == 0)
            return new byte[actualSize];
        return _buffersBySize[pos].Pop();
    }
    private static void ReturnBuffer(byte[] buffer)
    {
        var actualSize = PowerOfTwo(buffer.Length);
        if(actualSize != buffer.Length)
            return; // can't put a buffer of strange size here (probably an error)
        if(_buffersBySize == null)
            _buffersBySize = new Stack<byte[]>[32];
        var pos = MostSignificantBit(actualSize);
        if(_buffersBySize[pos] == null)
            _buffersBySize[pos] = new Stack<byte[]>();
        _buffersBySize[pos].Push(buffer);
    }

There are a couple of interesting things going on here. First, we do allocations by power of two number, this reduce the number of different sizes we have to deal with. We store all of that in a small array (using the most significant bit to index into the array based on the requested size) that contains stacks for all the requested sizes.

In practice, most of the time we’ll use a very small number of sizes, typically 4KB – 32KB.  The basic idea is that you’ll pull an array from the pool, and if there is a relevant one, we save allocations. If not, we allocate a new one and return it to the user.

Once we gave the user a buffer, we don’t keep track of it. If they return it to us, this is great, if not, the GC will clean it up. This is important, because otherwise forgetting to call ReturnBuffer creates what is effectively a memory leak.

Another thing to notice is that we aren’t requiring that the same thread will be used for getting and returning the buffer. It is fine to use one thread to get it and another to return it. This means that async code will work well with thread hopping and this buffer pool.  We also use a stack, to try to keep the busy buffer close to the actual CPU cache.

Note that this is notepad code, so there are probably issues with it.

In fact, there is a big issue here that will only show up in particular usage patterns. Can you see it? I’ll talk about it in my next post.