Is there a boost equivalent of eastl::fixed_vector?
In EASTL http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.htmlthere is something like SSO (Small String Optimization) applied to std::vector (and other STL containers) [begin quote] "Fixed containers are fixed-size containers with their memory stored right within the container itself. Fixed containers allocate no dynamic memory and their memory tends to be cache-friendly due to its contiguity and proximity to the container's housekeeping data. The user declares the max container size as a template parameter, and can also specify that if the container overflows that an auxiliary dynamic allocator is used. template <typename T, size_t nodeCount, bool enableOverflow = true, typename Allocator overflowAllocator = EASTLAllocator> class fixed_vector { ... }; [end quote] I have tried a similar approach using some sort of fixed_buffer_with_overflow allocator, with no success. I'm not sure SSO is even possible just using an allocator with the standard containers, because I always end up with stateful allocators. So my question is if there is something similar already in boost. TIA
On Sep 24, 2008, at 11:32 AM, dariomt@gmail.com wrote:
In EASTL http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html there is something like SSO (Small String Optimization) applied to std::vector (and other STL containers)
[begin quote] "Fixed containers are fixed-size containers with their memory stored right within the container itself. Fixed containers allocate no dynamic memory and their memory tends to be cache-friendly due to its contiguity and proximity to the container's housekeeping data. The user declares the max container size as a template parameter, and can also specify that if the container overflows that an auxiliary dynamic allocator is used.
template <typename T, size_t nodeCount, bool enableOverflow = true, typename Allocator overflowAllocator = EASTLAllocator> class fixed_vector
{ ... }; [end quote]
I have tried a similar approach using some sort of fixed_buffer_with_overflow allocator, with no success. I'm not sure SSO is even possible just using an allocator with the standard containers, because I always end up with stateful allocators.
So my question is if there is something similar already in boost.
A small vector with fixed capacity has been proposed a few years ago by Synge Todo. In discussions about initial interest it was said though that people would prefer a full-featured policy-based vector instead. Synge's code is thus not in Boost, but is available under the Boost license as part of the ALPS project at http://alps.comp-phys.org/ Matthias
Matthias Troyer <troyer <at> phys.ethz.ch> writes:
On Sep 24, 2008, at 11:32 AM, dariomt <at> gmail.com wrote: In EASTL http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html
{ ...};[end quote]I have tried a similar approach using some sort of fixed_buffer_with_overflow allocator, with no success. I'm not sure SSO is even
there is something like SSO (Small String Optimization) applied to std::vector (and other STL containers)[begin quote]"Fixed containers are fixed-size containers with their memory stored right within the container itself. Fixed containers allocate no dynamic memory and their memory tends to be cache-friendly due to its contiguity and proximity to the container's housekeeping data. The user declares the max container size as a template parameter, and can also specify that if the container overflows that an auxiliary dynamic allocator is used.template <typename T, size_t nodeCount, bool enableOverflow = true, typename Allocator overflowAllocator = EASTLAllocator>class fixed_vector possible just using an allocator with the standard containers, because I always end up with stateful allocators.So my question is if there is something similar already in boost.
A small vector with fixed capacity has been proposed a few years ago by Synge
Todo. In discussions about initial interest it was said though that people would prefer a full-featured policy-based vector instead. Synge's code is thus not in Boost, but is available under the Boost license as part of the ALPS project at http://alps.comp-phys.org/
Matthias
Will look into it. Thanks.
dariomt@gmail.com wrote:
In EASTL http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html there is something like SSO (Small String Optimization) applied to std::vector (and other STL containers)
[begin quote] "Fixed containers are fixed-size containers with their memory stored right within the container itself. Fixed containers allocate no dynamic memory and their memory tends to be cache-friendly due to its contiguity and proximity to the container's housekeeping data. The user declares the max container size as a template parameter, and can also specify that if the container overflows that an auxiliary dynamic allocator is used.
template <typename T, size_t nodeCount, bool enableOverflow = true, typename Allocator overflowAllocator = EASTLAllocator> class fixed_vector { ... };
[end quote]
I have tried a similar approach using some sort of fixed_buffer_with_overflow allocator, with no success. I'm not sure SSO is even possible just using an allocator with the standard containers, because I always end up with stateful allocators.
So my question is if there is something similar already in boost.
Doesn't std::vector::reserve already give the "overflow" behavior - albeit without the small string optimization? For non-"overflow" ability there's boost::array. Jeff
hello, well if you are using words like "fixed-size" and "allocate no dynamic memory" then boost::array<T,N> is your candidate, isn't it? personally i miss the stored count of objects so i can push_back until some capacity. so i modified the source slightly for these purposes. regards, mojmir * dariomt@gmail.com <dariomt@gmail.com> [2008-09-24 11:32:45 +0200]:
In EASTL http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.htmlthere is something like SSO (Small String Optimization) applied to std::vector (and other STL containers)
[begin quote] "Fixed containers are fixed-size containers with their memory stored right within the container itself. Fixed containers allocate no dynamic memory and their memory tends to be cache-friendly due to its contiguity and proximity to the container's housekeeping data. The user declares the max container size as a template parameter, and can also specify that if the container overflows that an auxiliary dynamic allocator is used.
template <typename T, size_t nodeCount, bool enableOverflow = true, typename Allocator overflowAllocator = EASTLAllocator> class fixed_vector { ... };
[end quote]
I have tried a similar approach using some sort of fixed_buffer_with_overflow allocator, with no success. I'm not sure SSO is even possible just using an allocator with the standard containers, because I always end up with stateful allocators.
So my question is if there is something similar already in boost.
TIA
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
well if you are using words like "fixed-size" and "allocate no dynamic memory" then boost::array<T,N> is your candidate, isn't it?
personally i miss the stored count of objects so i can push_back until some capacity. so i modified the source slightly for these purposes.
That's what I meant with SSO, in this case I would call it SCO (Small Container Optimization): The container has 'within the container itself' a buffer (in the stack) with space for N objects, so as long as size() <= N no dynamic allocation is needed. When size() > N, a policy can decide to throw an exception or to switch to dynamic allocation 'as usual'. Some STL implementations (e.g. the one shipped with MS VC++) use this SSO in std::basic_string with a 'small' non-tunable N (e.g. 16), so 'small' strings don't use dynamic memory. The situation I am trying to improve is where 'many' 'small' vectors (or other containers) are constructed/copied/assigned/destructed, and allocation/deallocation seems to be a significant overhead. I cannot switch the vectors to boost::array because I need variable size (but guaranteed to be 'small'). It seems ublas::vector has the possibility to specify a 'bounded vector' (stack buffer) as the underlying storage, but I think it lacks fallback to dynamic allocation and a std::vector compatible interface. I'll take a look to the implementation to get some ideas. I was looking for a general solution based on allocators, to be able to apply it to other containers as well. ¿Any ideas for this approach?
* dariomt <at> gmail.com <dariomt <at> gmail.com> [2008-09-24 11:32:45 +0200]:
In EASTL http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.htmlthere is something like SSO (Small String Optimization) applied to std::vector (and other STL containers)
[begin quote] "Fixed containers are fixed-size containers with their memory stored right within the container itself. Fixed containers allocate no dynamic memory and their memory tends to be cache-friendly due to its contiguity and proximity to the container's housekeeping data. The user declares the max container size as a template parameter, and can also specify that if the container overflows that an auxiliary dynamic allocator is used.
template <typename T, size_t nodeCount, bool enableOverflow = true, typename Allocator overflowAllocator = EASTLAllocator> class fixed_vector { ... };
[end quote]
I have tried a similar approach using some sort of fixed_buffer_with_overflow allocator, with no success. I'm not sure SSO is even possible just using an allocator with the standard containers, because I always end up with stateful allocators.
So my question is if there is something similar already in boost.
TIA
_______________________________________________ Boost-users mailing list Boost-users <at> lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (5)
-
dariomt -
dariomt＠gmail.com
-
Jeff Flinn -
Matthias Troyer -
Mojmir Svoboda