The Wiert Corner – irregular stream of stuff

Jeroen W. Pluimers on .NET, C#, Delphi, databases, and personal interests

  • My badges

  • Twitter Updates

  • My Flickr Stream

  • Pages

  • All categories

  • Enter your email address to subscribe to this blog and receive notifications of new posts by email.

    Join 2,912 other followers

On List growth strategies and memory managers

Posted by jpluimers on 2017/08/03

Interesting for anybody working on list growth strategies.

In this case with some Delphi background information and in depth coverage of FastMM memory (re)allocation strategies.

[WayBack] Stefan Glienke (of [WayBack] Spring4D fame) needed some help with allocation strategies and observed the difference between:

  • TList.Grow (and TStringList.Grow) growing like this: 4, 8, 12, 28, 44, 60, 76, 95, 118, 147, 183, 228, 285, 356, 445, 556, 695, 868, 1085
  • Generic TList<T> growing  the same way as the .NET List<T>: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024

There is this nice [WayBackDynamic array – Growth factor – Wikipedia, the free encyclopedia mentioning this table:

Implementation Growth factor (a)
Java ArrayList[1] 1.5 (3/2)
Python PyListObject[7] 1.125 (9/8)
Microsoft Visual C++ 2013[8] 1.5 (3/2)
G++ 5.2.0[5] 2
Clang 3.6[5] 2
Facebook folly/FBVector[9] 1.5 (3/2)

[WayBack] Javier Hernández mentioned he doesn’t think exponential is better than n^2.

[WayBack] Eric Grange (of [WayBackDWS and [ fame) mentions he tends to use 1.5, it is about as good as 2 for small lists, but reduces waste for large ones. He also uses a constant delta to accelerate growth early on, so something like:

n := n + (n div 2) + 8

Since allocation strategies highly depend on the memory allocator as well, I was glad [WayBackPrimož Gabrijelčič (of [WayBackOnmiThreadLibrary and [WayBackSmart Mobile Studio fame) elaborated on FastMM:

  • FastMM small block allocator sizes (size includes the leading header) are: 8, 16, 24, 32, … 160 (in +8 steps), 176, 192, … 320 (+16), 352, 384 … 480 (+32), 528, 576, … 672 (+48), 736, 800, 880, 960, 1056, 1152, 1264, 1376, 1504, 1648, 1808 , 1984, 2176, 2384. [FastMM4.pas, SmallBlockTypes global var]
  • While the size of reallocated region fits inside a small block (with a different size than a previous block), the data is moved around (new block is allocated from a new suballocator). If it is too big (>2384 bytes), it gets allocated from the medium block allocator (which handles all block sizes up to 264752 bytes; larger blocks come directly from VirtualAlloc).
  • When small blocks are reallocated (to a larger size), allocator always allocates at least 100% + 32 bytes larger block, even if less is requested by the RTL (example: 8 bytes will grow to 2*8 + 32 = 48 bytes). When medium blocks are reallocated, allocator always allocates at least 125% of the old size. This boosts the performance when blocks are enlarged by small values as they can be enlarged “in place” (no data moved around, just the header is adjusted).

Stefan Glienke and Primož Gabrijelčič then concluded that:

  • Resizing an array from say 4 elements (pointer size) to 1000 (in multiple steps) will for sure move several times when jumping from one region into the next larger one.
  • Changing to a growth factor of 1.5 vs 2 won’t change anything in terms of memory fragmentation in FastMM4.

Source: [WayBack] I was just looking at TList.Grow (and TStringList.Grow) and I realized that the…

Edit 20181127

Delphi 10.3 Rio makes this configurable in a global way for all threads at the same time (#facepalm! as it is the 1980s Turbo Pascal ExitProc mess all over again): [WayBack] Delphi RTL Improvements in 10.3 Rio via [WayBack] +Marco Cantù is unstoppable. I can’t keep up LOL  – Clement Doss – Google+

The SetGrowCollectionFunc is of course not documented in the RTL, only in the [WayBack] What’s New – RAD Studio 10.3 Rio: [WayBack] Search results for “SetGrowCollectionFunc” – RAD Studio 10.3 Rio.

Stefan Glienke commented in that G+ thread:

I recently experimented with different grow factors and while the memory fragmentation can only mitigated for medium and large blocks (where it actually matters imo) it might be beneficial to only grow by 1.5 at that point. But that has yet to be tested.
What I liked so far is the grow strategy that Go uses (2x until 1024, 1.25x after that) – see

Since you usually set the size upfront if you add many elements at once (well, if you know how many beforehand) the grow strategy only matters in the long run. You want to balance speed (too many realloc might slow things down unnecessarily), memory overhead (if you are overallocating much you risk wasting too much memory) and memory fragmentation (which might happen with a grow factor bigger than the golden ratio)


7 Responses to “On List growth strategies and memory managers”

  1. rvelthuis said

    I have done some research on this too. It seems that 1.5, or the golden ration, are indeed optimal and avoid memory fragmentation much better than a factor of 2. I forgot where I read that, though, but multiple sources seemed to agree on this.

  2. thaddy said

    Actually 1.5 is just a rough approximation of the golden ratio which is mathematically proven to be optimal for lists. (you could therefor also use the fibonacci sequence ;) )

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: