How to implement simple thread-safe memory management preventing fragmentation?

Question

I need to implement simple thread-safe memory management preventing fragmentation. I've read some articles about that like this and this, but I cannot figure out how to start the implementation in C#.

Important points: 95% of requests for memory allocation will be blocks smaller than 1K!

Could somebody please give me some code to start with?

EDITED I've written a Allocator but how I didn't used pools in Alloc method. How I can change it so it will use pools?

class Allocator
{
       private int _id;

       //TODO: it must be struct!
       class Block
       {
              public int offset;
              public int blockLength;
       }

       private readonly Dictionary<int, Block> idToBlock = new Dictionary<int, Block>();

       private List<byte> rawData;
       private int allocatedBlocksLength;

       // sync
       private readonly object _sync = new object();

       public int Alloc(int count)
       {                  
              rawData.AddRange(new byte[count]);
              idToBlock.Add(_id, new Block { offset = allocatedBlocksLength, blockLength = count });

              var blockId = _id;
              ++_id;
              allocatedBlocksLength += count;

              return blockId;
       }

       public void Free(int id)
       {
              // Search in table
              Block block;
              if (!idToBlock.TryGetValue(id, out block))
                     return;

              // remove object and update all offsets that after our block
              foreach (var kv in idToBlock)
              {
                     if (kv.Key == id)
                           continue;
                     if (kv.Value.offset > block.offset)
                           continue;

                     // changing indexes
                     kv.Value.offset -= block.blockLength;
              }

              // update how much left
              allocatedBlocksLength -= block.blockLength;
       }
}

Answer 1

If you do need a custom memory manager for your .NET application you should not follow tips (or simply translate code) from the unmanaged world (your second link).

Memory allocation in .NET environment is quite different, memory gets fragmented much more (because the default allocator privileges the allocation speed) but it can be compacted (so problems of memory fragmentation isn't really a problem there).

It's not your case, but big objects (these days this threshold is set to 85 KB) will be allocated with a different strategy and they won't be compacted. I think you may need a custom allocator only if you create a lot of short living big objects.

The first link provide a very naive implementation, did you profile it in a multi-threading environment? Are you sure that it performs better than default allocation, in your case? Even if it performs a little bit better are you sure you need it?

To make your memory allocator thread-safe you mayuse a different heap for each thread or simply lock your data structures (for example if you keep the list of free memory blocks inside a LinkedList you may lock the structure when you remove a node from the list). It's not a topic that can be explained in few lines, if you're really interested to these internals you may read the great "CLR via C#" book.

When object allocation is really expansive you may use a mechanism of resurrection for your objects but this adds a lot of complexity that must be evaluated, often the price you'll pay is bigger. You may start with a factory method like:

MyObject obj = ObjectFactory.Allocate();

Instead of the simple:

MyObject obj = new MyObject();

In this way you may switch to something else if you really need it but...
...a small tip: DO NOT PLAY WITH MEMORY ALLOCATION if you're not really sure of what you're doing and after you PROFILED your current memory allocation strategy.

(I'm tempted to use even a bigger font for this message)

This may be one of the worst thing you can do to your application because you'll make it slower and your code will be less readable. 99.999% of application won't need these custom stuff, are you sure your application will need?

EDIT
From the example it's not really clear what you're doing. Your Alloc method returns an ID but how can you get the allocated data? Anyway...
If you really need to do something like that...

• Do not keep a list of bytes, you'll just waste memory.
• Do not provide a Free method, you're in .NET so please rely on GC.
• Keep a list of available blocks (the Block object). In the Allocate method you'll search the list of free blocks for a block of the desired size. If you find it you return that block and you remove it from the list. If you do not find the block you have to allocate it and to simply return it to the caller.
• In the finalizer of the Block object call the GC.ReRegisterForFinalize method and insert the object inside the list of available blocks.

Very simple implementation, consider as an example not a true program:

sealed class Block
{
    internal Block(int size)
    {
        Data = new byte[size];
    }

    ~Block()
    {
        BlockFactory.Free(this);
        GC.ReRegisterForFinalize(this);
    }

    public byte[] Data
    {
        get;
        private set;
    }
}

static class BlockFactory
{
    public static Block Allocate(int size)
    {
        lock (_freeBlocks)
        {
            foreach (Block block in _freeBlocks)
            {
                if (block.Data.Length == size)
                {
                    _freeBlocks.Remove(block);

                    return block;
                }
            }

            return new Block(size);
        }
    }

    internal static void Free(Block block)
    {
        lock (_freeBlocks) _freeBlocks.Add(block);
    }

    private static List<Block> _freeBlocks = new List<Block>();
}

Please note that:

• This implementation is not efficient at all (in this case a better solution could be a ReadWriterLockSlim instead of lock or another more appropriate data structure instead of List<T>).
• The search using enumeration is terrible but here it's just for clarity.
• To add a finalizer to each object may decrease performances.
• The example uses Block as container for the data you need (an array of bytes). Is this what you need?

That said I still think BEFORE you spend any time on this you should check if you need it. Does your application suffers of this issue? Is it the problem? Imagine for example you have a data processing application. Your pipeline is composed of these stages:

• Acquisition (somehow timed to get data at regular intervals).
• Processing (various filters).
• Visualization.

If you allocate a new buffer for each packet you may create a lot of small objects. I do not really think this may be a problem but you may consider to reuse the same (pre-allocated) buffer in the acquisition stage instead of trying to add complexity to all the application.

I hope it's clear what I mean.