Jump to content
A.M. Hoornweg

Tlist<T> growth strategy is bad.

Recommended Posts

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!

 

Share this post


Link to post

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. 

  • Like 1

Share this post


Link to post

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

  • Like 1

Share this post


Link to post
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. 

Share this post


Link to post
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.

Share this post


Link to post
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 by Fr0sT.Brutal

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×