Tlist<T> growth strategy is bad.

[A.M. Hoornweg 144]

Hello World,

 

I notice that tList<T> has a terrible growth strategy, it basically does "TListHelper.InternalGrow(count + 1)" whenever an item is appended, there is no granularity and in very large collections the overhead can become undesirable. 

 

It is not possible to use the OnNotify event to check and increase the capacity before the insert, because TListHelper "forgets" to send the the notification cnAdding before it inserts. That value exists but is never used.

Instead, it sends cnAdded after the fact.  Sure it's still possible to check and increase the capacity at that point, but it's not optimal. In my opinion, it would be better if tListHelper would simply send a cnAdding notification before inserting.

 

I can still inherit from tList<T> and override/reintroduce the Add method by a new one that takes granularity into account, but in my opinion it's kinda un-elegant because the base class already has a notification feature that could be used to achieve the same thing.

 

I'd love to hear the opinion of the Delphi community on this!

 

[A.M. Hoornweg 144]

Please ignore my previous post.

 

It appears I was incorrect about my assumption that the size of the list is always increased by one, it uses "GrowCollection" from unit Sysutils which is a more clever strategy. 

[Fr0sT.Brutal 900]

Anyway FastMM internally uses pre-reserve strategy for deallocations making +1 growth not so terrible

[David Heffernan 2345]

20 hours ago, Fr0sT.Brutal said:

Anyway FastMM internally uses pre-reserve strategy for deallocations making +1 growth not so terrible

Even so, you'd still be spending time in the heap allocator which would be undesirable. 

[Fr0sT.Brutal 900]

On 1/21/2023 at 10:24 AM, David Heffernan said:

Even so, you'd still be spending time in the heap allocator which would be undesirable. 

You mean entering locked list of allocated blocks? Probably this will only make difference in multithread apps and FastMM4 as FastMM5 have been optimized for multithreading. Anyway I made benchmarks for stringbuilder that preallocates larger parts and dumb s:=s+'a' some time ago and saw no significant speedup. But again, this was just a single-thread app.

[Fr0sT.Brutal 900]

On 1/20/2023 at 2:10 PM, Fr0sT.Brutal said:

uses pre-reserve strategy for deallocations

Damn, the typo that breaks all meaning. Reallocations of course.

Edited January 23, 2023 by Fr0sT.Brutal