A problem what I stumbled over is if you have millions of entries in your list – you would then need more than double of the current size even if you just need one more entry. For my graphhopper project I just created a segmented array which entirely avoids copying and has a maximum amount of wasted capacity (==segment size). It has still the disadvantage of a bit slower access as you need some modulo operations to access the 2d array, but with bit operations you can get a bit faster. I didn’t study the performance as memory requirements forced me to introduce it but nevertheless I would be interested if you could add this to your benchmarks + add one more for access time? https://github.com/graphhopper/graphhopper/blob/master/src/main/java/com/graphhopper/storage/RAMDataAccess.java
Note that the Windows implementation of the STL is using a grow factor or 3/2, unlike the GCC implementation.
Also on reallocation, std::vector is not simply moving the data to the new memory block using for example memcpy, for rather it supports non-POD types and either call the move constructor or the move assignment operator for each element, one by one. Doing the same with c++11 disabled could be even more expansive.
It could be interesting to be able to specify which grow factor to use depending on one large the array already is, and also to set a flag telling the vector that we are storing Plain Old Data and that constructors needs not be called, instead enabling block copy.
To Peter:
The problem with segmented arrays is that since their memory is not allocated as one continuous block, they lose cache coherence. Reading one such array from beginning to end would jump though memory between each segments, forcing the cpu to fetch the data from the main memory instead of hitting the cpu cache.
For my tests, I did not use the STL vector template. So the numbers I give use memcpy. I did benchmark with vector and it was indeed slower, probably for the reason you gave. I did not try STL with C++11 enabled.
As for segmented arrays… intuitively, if the segments are large enough, it should not create much harm if you are scanning all of the vector from the beginning till the end.
Amit Kumarsays:
Comparison with C++ deque would be interesting as it does not reallocate.
Amit Kumarsays:
One thing I noticed in the source code is that the access pattern used might favor the static array as the same block might be used by the OS to allocate and deallocate the static array.
A problem what I stumbled over is if you have millions of entries in your list – you would then need more than double of the current size even if you just need one more entry. For my graphhopper project I just created a segmented array which entirely avoids copying and has a maximum amount of wasted capacity (==segment size). It has still the disadvantage of a bit slower access as you need some modulo operations to access the 2d array, but with bit operations you can get a bit faster. I didn’t study the performance as memory requirements forced me to introduce it but nevertheless I would be interested if you could add this to your benchmarks + add one more for access time? https://github.com/graphhopper/graphhopper/blob/master/src/main/java/com/graphhopper/storage/RAMDataAccess.java
One more benefit of the segmented (double-array) solution is that you can grow the number of entries over 2^32 or 2^31 in case of Java.
@Peter
Thanks Peter. When I revisit this problem, I’ll be sure to have a look at your solution.
For the record, the Go dynamic array (“slice”) implementation doubles the size until 1024 elements; after then the ratio is 5/4.
http://golang.org/src/pkg/runtime/slice.c#L131
Thank you for that article, I enjoyed reading it.
Note that the Windows implementation of the STL is using a grow factor or 3/2, unlike the GCC implementation.
Also on reallocation, std::vector is not simply moving the data to the new memory block using for example memcpy, for rather it supports non-POD types and either call the move constructor or the move assignment operator for each element, one by one. Doing the same with c++11 disabled could be even more expansive.
It could be interesting to be able to specify which grow factor to use depending on one large the array already is, and also to set a flag telling the vector that we are storing Plain Old Data and that constructors needs not be called, instead enabling block copy.
To Peter:
The problem with segmented arrays is that since their memory is not allocated as one continuous block, they lose cache coherence. Reading one such array from beginning to end would jump though memory between each segments, forcing the cpu to fetch the data from the main memory instead of hitting the cpu cache.
@ Valrandir
For my tests, I did not use the STL vector template. So the numbers I give use memcpy. I did benchmark with vector and it was indeed slower, probably for the reason you gave. I did not try STL with C++11 enabled.
As for segmented arrays… intuitively, if the segments are large enough, it should not create much harm if you are scanning all of the vector from the beginning till the end.
Comparison with C++ deque would be interesting as it does not reallocate.
One thing I noticed in the source code is that the access pattern used might favor the static array as the same block might be used by the OS to allocate and deallocate the static array.