how to avoid objects allocations? how to reuse objects instead of allocating them?

Question

My financical software processes constantly almost the same objects. For example I have such data online:

HP 100 1
HP 100 2
HP 100.1 1
etc.

I've about 1000 updates every second.

Each update is stored in object - but i do not want to allocate these objects on the fly to improve latency. I use objects only in short period of time - i recive them, apply and free. Once object is free it actually can be reused for another pack of data.

So I need some storage (likely ring-buffer) that allocates required number of objects once and them allow to "obtain" and "free" them. What is the best way to do that in c#?

Each object has id and i assign id's sequentially and free them sequentially too. For example i receive id's 1 2 and 3, then I free 1, 2, 3. So any FIFO collection would work, but i'm looking for some library class that cover's required functionality.

I.e. I need FIFO collection that do not allocates objects, but reuse them and allows to reconfigure them.

upd

I've added my implementation of what I want. This is not tested code and probably has bugs. Idea is simple. Writer should call Obtain Commit methods. Reader should call TryGet method. Reader and writer can access this structure from different threads:

public sealed class ArrayPool<T> where T : class
{
    readonly T[] array;
    private readonly uint MASK;

    private volatile uint curWriteNum;
    private volatile uint curReadNum;

    public ArrayPool(uint length = 1024) // length must be power of 2
    {
        if (length <= 0) throw new ArgumentOutOfRangeException("length");
        array = new T[length];
        MASK = length - 1;
    }

    /// <summary>
    /// TryGet() itself is not thread safe and should be called from one thread.
    /// However TryGet() and Obtain/Commit can be called from different threads
    /// </summary>
    /// <returns></returns>
    public T TryGet()
    {
        if (curReadNum == curWriteNum)
        {
            return null;
        }
        T result = array[curReadNum & MASK];
        curReadNum++;
        return result;
    }

    public T Obtain()
    {
        return array[curWriteNum & MASK];
    }

    public void Commit()
    {
        curWriteNum++;
    }

}

Comments about my implementation are welcome and probably some library method can replace this simple class?

Answer 1

I don't think you should leap at this, as per my comments on the question - however, a simple approach would be something like:

public sealed class MicroPool<T> where T : class
{
    readonly T[] array;
    public MicroPool(int length = 10)
    {
        if (length <= 0) throw new ArgumentOutOfRangeException("length");
        array = new T[length];
    }
    public T TryGet()
    {
        T item;
        for (int i = 0; i < array.Length; i++)
        {
            if ((item = Interlocked.Exchange(ref array[i], null)) != null)
                return item;
        }
        return null;
    }
    public void Recycle(T item)
    {
        if(item == null) return;
        for (int i = 0; i < array.Length; i++)
        {
            if (Interlocked.CompareExchange(ref array[i], item, null) == null)
                return;
        }
        using (item as IDisposable) { } // cleaup if needed
    }
}

Answer 2

If the loads come in burst, you may be able to use the GC's latency modes to offset the overhead by delaying collects. This is not a silver bullet, but in some cases it can be very helpful.

Answer 3

I am not sure, if this is what you need, but you could always make a pool of objects that are going to be used. Initialize a List of the object type. Then when you need to use an object remove it from the list and add it back when you are done with it.

http://www.codeproject.com/Articles/20848/C-Object-Pooling Is a good start.

Hope I've helped even if a little :)

Answer 4

If you are just worried about the time taken for the GC to run, then don't be - it can't be beaten by anything you can do yourself.

However, if your objects' constructors do some work it might be quicker to cache them.

A fairly straightforward way to do this is to use a ConcurrentBag

Essentially what you do is to pre-populate it with a set of objects using ConcurrentBag.Add() (that is if you want - or you can start with it empty and let it grow).

Then when you need a new object you use ConcurrentBag.TryTake() to grab an object.

If TryTake() fails then you just create a new object and use that instead.

Regardless of whether you grabbed an object from the bag or created a new one, once you're done with it you just put that object back into the bag using ConcurrentBag.Add()

Generally your bag will get to a certain size but no larger (but you might want to instrument things just to check it).

In any case, I would always do some timings to see if changes like this actually make any difference. Unless the object constructors are doing a fair bit of work, chances are it won't make much difference.