The Wiert Corner – irregular stream of stuff

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

  • My work

  • 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 1,811 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.

Stefan Glienke (of 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 Dynamic 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)

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

Eric Grange (of DWS 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 Primož Gabrijelčič (of OnmiThreadLibrary and Smart 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: I was just looking at TList.Grow (and TStringList.Grow) and I realized that the…


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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: