This special kind of biomimetics is also being researched elsewhere, for example at the Max-Planck-Institute in Stuttgart, Germany. An insightful article can be downloaded from here.
1) Record in the virtual machine/JIT every time a vector gets resized.
2) Based on the pattern of resizing, speculatively allocate for new vectors/resizes as much memory as they'll ever need, or at least as much as they'll need any time soon.
3) When you guess wrong about a speculative allocation, adjust your speculation.
Very true, indeed. The only thing that is missing in this analysis is this: why can all this not be done with a static compiler when you design your class such as to record usage patterns and resize based on previous resizes?
Well, the answer is: it can. You can design a class Vector<T> in C++ which behaves exactly the way you describe. The Holy Standard doesn't even demand allocation in powers of two. What you describe may even be the internal implementation of a perfectly valid std::vector<T>. If it hasn't been done already it is most likely because it is too clever. A simpler allocation in powers of two is extremely robust to worst cases caused by weird usage patterns.
Slashdot Mirror
This special kind of biomimetics is also being researched elsewhere, for example at the Max-Planck-Institute in Stuttgart, Germany. An insightful article can be downloaded from here.
1) Record in the virtual machine/JIT every time a vector gets resized.
2) Based on the pattern of resizing, speculatively allocate for new vectors/resizes as much memory as they'll ever need, or at least as much as they'll need any time soon.
3) When you guess wrong about a speculative allocation, adjust your speculation.
Very true, indeed. The only thing that is missing in this analysis is this: why can all this not be done with a static compiler when you design your class such as to record usage patterns and resize based on previous resizes?
Well, the answer is: it can. You can design a class Vector<T> in C++ which behaves exactly the way you describe. The Holy Standard doesn't even demand allocation in powers of two. What you describe may even be the internal implementation of a perfectly valid std::vector<T>. If it hasn't been done already it is most likely because it is too clever. A simpler allocation in powers of two is extremely robust to worst cases caused by weird usage patterns.