Is there a faster TList implementation?

Question

My application makes heavy use of TList, so I was wondering if there are any alternative implementations that are faster or optimized for particular use case.

I know of RtlVCLOptimize.pas 2.77, which has optimized implementations of several TList methods.

But I'd like to know if there is anything else out there. I also don't require it to be a TList descendant, I just need the TList functionality regardless of how it's implemented.

It's entirely possible, given the rather basic functionality TList provides, that there is not much room for improvement, but would still like to verify that, hence this question.

edit: In my particular use case no lists are sorted. There are lots of lists, with various number of elements in. I did replace TList with my own class in order to log number of Add/Remove calls and count of elements. It reports (toatal for all lists):

ListAdd = 15766012; ListRemove = 10630000; ListCount = 5136012

I could also find out what the highest number of elements in a single list is.

I have no particular issue, I just wonder if there is a way to make it faster all around as with these numbers even small improvement would add up.

Answer 1

One of the biggest bottleneck I know about TList is the Delete/Extract on large list. Removing item[0] is a lot slower than removing Item[Count-1] because of the memory move that follows it.

For exemple, on a list containing 65536 elements:

while list.Count > 0 do List.Delete(0) //Takes 2 mins to complete

for I := List.Count-1 downto 0 do List.Delete(I) //Takes less than 1 sec

So if you have a TList with millions of elements, deleting a low index item can be expensive performance-wise. Also, consider that having a list that isn't sorted makes it very slow to find an element in it. IndexOf is very slow on large list. You might want to consider keeping the list sorted.

Also, considering your item count can be pretty large, you might want to consider using a List of TList to store your elements, which will help reduce the Delete/Extract overhead I already mentioned.