On Tue, Oct 16, 2012 at 2:52 PM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@gmail.com> wrote:
On Tue, Oct 16, 2012 at 5:00 AM, Klaim - Joël Lamotte <mjklaim@gmail.com
wrote: [...]
Currently, my solution is implemented by using a boost::stable_vector< boost::optional<T>> which seems efficient (to my surprise).
[...]
Sounds basically equivalent to a std::vector<T*> or (better) std::vector< std::unique_ptr<T> >, no? I would expect these explicit pointer-based containers to have a marginally smaller memory footprint than stable_vector< optional<T> >.
No, you get tons of cache misses this way. Because when you try to access to each element in order it's really faster when the element are in contiguous memory. It's not a problem with low count of objects, obviously, or when you don't do it often, but I have to do it around 50 times by seconds and with a count of elements that can be high. If you compare using pointers to using optional (which is NOT a pointer and keep the memory of the element "hot") in a vector, you immediately see the benefit. Stable vector don't guarantee contiguity but it apparently does keep bloc of objects contiguous as much as it can. If you reserve your optionals at first, then a lot of contiguous memory is allocated for your future objects, which is basically a pool. I'd say the main difference with boost::pool for example is that you can't have any input on the memory blocks boost::stable_vector will allocate. I might be wrong on the boost::stable_vector behaviour but my current tests shows that it's a win win scenario in my case. Joel Lamotte