Fast access to a (sorted) TList?

Up vote 2 down vote favorite share g+ share fb share tw.

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! Delphi delphi-6 link|improve this question edited Sep 23 '11 at 11:08Bruce McGee10.1k32444 asked Sep 23 '11 at 8:49Fotis Mouratidis6810.

From your description, it looks like FastMM does about the same. I think FastMM actually uses several lists of Allocations for different sizes: a list for small ( 1024 bytes). – Otherside Sep 23 '11 at 9:02 1 Have you considered using FastMM?

– TOndrej Sep 23 '11 at 9:02 1 You need the GarbageCollector so is your application multithread? – GJ. Sep 23 '11 at 9:24 1 FastMM would be a big step up from BorlandMM.

On the down side it struggles under severe thread contention but that may not be an issue. First step though is to try FastMM. – David Heffernan Sep 23 '11 at 9:36 Thanks for the tip about FastMM!

I will try that out. @GJ: Yes, my application is multithreaded. It's not exactly a GarbageCollector, but only similar.

I keep the memory allocations for reuse within my list. Only large memory allocation >1KiB are deallocated by the GC-function. – Fotis Mouratidis Sep 23 '11 at 10:07.

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!

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.