- Loki Astari (C)2016
- 27 May 2016
The last two articles examined the "C Socket" interface that is provided by OS. In this article I wrap this functionality in a very simple C++ class to provide guaranteed closing and apply a consistenRead More
So I never really considered why the resize of vector used a constant expansion of 1.5 or 2 (in some popular implementations). That was until I did my previous article Xseries "Vector" where I concentrated a lot on resource management and did a section on resizing the vector. Originally in the code I tried to be clever, a mistake. I used a resize value of 1.62 (an approximation of
Phi), because I vaguely remembered reading an article that this was the optimum resize factor. When I put this out for code review it was pointed out to me that this value was too large, the optimum value must be less than or equal to
Phi (1.6180339887) and that exceeding this limit actually made things a lot worse.
So I had to know why....
So the theory goes: You have a memory resource of size
B. If you resize this resource by a constant factor
r by re-allocating a new block then releasing the old block. Then if the value of
r is smaller than or equal to
Phi you will eventually be able to reuse memory that has previously been released; otherwise the new block of memory being allocated will always be larger than the previously released memory.
So I thought lets try that:
r > Phi:
B=10 r=2.0 Sum Memory Memory Memory Needed Difference Released Allocated Next Iteration Start 0 10 20 20 Resize 1 10 20 40 30 Resize 2 30 40 80 50 Resize 3 70 80 160 90 Resize 4 150 160 320 170
OK. That seems to be holding (at least in the short term). Lo lets try a smaller value.
r < Phi:
B=10 r=1.5 Sum Memory Memory Memory Needed Difference Released Allocated Next Iteration Start 0 10 15 15 Resize 1 10 15 22 12 Resize 2 25 22 33 8 Resize 3 47 33 48 1 Resize 4 80 48 72 -8 // Reuse released memory next iteration
OK. That also seems to be holding. But can we show that holds for all values of B? Also this is a bit anecdotal can we actually show this relationship actually hold? Time to break out some maths (not math as my American cousins seem to insist on for the shortening of mathematics).
So the size
S of any block after
n resize operations will be:
Thus the size of
Released Memory can be expressed as:
Also the size of the next block will be:
So if the amount of
Released Memory >= the amount required for the next block, then we can reuse the
This is were my maths broke down. So after talking to some smart people. They noticed that:
We find that the first root of the equation is 1. The second root of the equation depends on
n tends to
infinity the other root tends towards
Phi. From this we can infer the following:
r remains in the above range then the above theory holds.