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(andTStringList.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 .NETList<T>: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024
There is this nice [WayBack] 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)
[WayBack] Javier Hernández mentioned he doesn’t think exponential is better than n^2.
[WayBack] Eric Grange (of [WayBack] DWS and [WayBack] beginend.net 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 [WayBack] Primož Gabrijelčič (of [WayBack] OnmiThreadLibrary and [WayBack] 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: [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 https://golang.org/src/runtime/slice.go#L115Since 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)
–jeroen
The Wiert Corner - irregular stream of stuff 
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.
thaddyThaddy de Koning said
Remember “optimal” is the space (incl. fragmentation) vs time trade off and in pure mathematics doesn’t take into account hardware limitations like blocksize.
It was actually empirically shown by one of the D compiler team in an old usenet post (forgot the name)
The mathematical proof is to be found e.g. here: https://crntaylor.wordpress.com/2011/07/15/optimal-memory-reallocation-and-the-golden-ratio/ but I also found it myself, since it is so easy: mere substitution. In practise it means that a fibonacci table can be used for growth.
thaddy said
Note the application of a fibonacci table seems an original idea, I can’t find anything about it. Such a table is actually very small in size: due to its exponential nature, boundaries of physical memory are reached sooner than later.
jpluimers said
Thanks. I’ve saved that page in the WayBack machine:
https://web.archive.org/web/20170808090051/https://crntaylor.wordpress.com/2011/07/15/optimal-memory-reallocation-and-the-golden-ratio/
rvelthuis said
IME, a growth rate of 1.5 is far easier to do than a fibonacci series, and probably doesn’t do much worse WRT fragmentation either.
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 ;) )
jpluimers said
Thanks. That’s something cool to know: https://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence