Fast access to a (sorted) TList

Question

My project (running on Delphi 6!) requires a list of memory allocations (TMemoryAllocation) which I store within an object that also holds the information about the size of the allocation (FSize) and if the allocation is in use or free (FUsed). I use this basically as a GarbageCollector and a way to keep my application of allocating/deallocating memory all the time (and there are plenty allocations/deallocations needed).

Whenever my project needs an allocation it looks up the list to find a free allocation that fits the required size. To achieve that I use a simple for loop:

for I := 0 to FAllocationList.Count - 1 do
begin
  if MemoryAllocation.FUsed and (MemoryAllocation.FSize = Size) then
...

The longer my application runs this list grows to several thousand items and it slows down considerably as I run it up very frequently (several times per second).

I am trying to find a way to accelerate this solution. I thought about sorting the TList by size of allocation. If I do that I should use some intelligent way of accessing the list for the particular size I need at every call. Is there some easy way to do this?

Another way I was thinking about was to have two TLists. One for the Unused and one of the Used allocations. That would mean though that I would have to Extract TList.Items from one list and add to the other all the time. And I would still need to use a for-loop to go through the (now) smaller list. Would this be the right way?

Other suggestions are VERY welcome as well!

Answer 1

You have several possibilities:

• Of course, use a proven Memory Manager as FastMM4 or some others dedicated to better scale for multi-threaded applications;
• Reinvent the wheel.

If your application is very sensitive to memory allocation, perhaps some feedback about reinventing the wheel:

• Leverage your blocks size e.g. per 16 bytes multiples, then maintain one list per block size - so you can quickly reach the good block "family", and won't have to store each individual block size in memory (if it's own in the 32 bytes list, it is a 32 bytes blocks);
• If you need reallocation, try to guess the best increasing factor to reduce memory copy;
• Sort your blocks per size, then use binary search, which will be much faster than a plain for i := 0 to Count-1 loop;
• Maintain a block of deleted items in the list, in which to lookup when you need a new item (so you won't have to delete the item, just mark it as free - this will speed up a lot if the list is huge);
• Instead of using a list (which will have some speed issues when deleting or inserting sorted items with a huge number of items) use a linked list, for both items and freed items.

It's definitively not so simple, so you may want to look at some existing code before, or just rely on existing libraries. I think you don't have to code this memory allocation in your application, unless FastMM4 is not fast enough for you, which I'll doubt very much, because this is a great piece of code!