Re: Searching for stack based containers
On May 3, 4:05 pm, Michael DOUBEZ <michael.dou...@free.fr> wrote:
jimxoch a =E9crit :
Most STL containers are storing their data on the heap. (although some
std::string implementations are notable exceptions) Of course, using
the heap as storage increases flexibility and allows the handling of
much bigger amounts of data. However, there are cases where this turns
out to be inefficient for at least two reasons: A) Allocations and
deallocations on heap are much slower.
Technically speaking, you should define what you mean by an "STL
container". In the current standard, all containers are either
sequences or associative containers, and all containers are
dynamically expansible, which isn't generally possible on the
stack.
The type Boost::array has been adopted by the committee for
inclusion in the next version of the standard, so this will no
longer be true then. And of course, C style arrays can also be
used, and support most of the same operations as boost::array.
(The major difference is that C style arrays aren't copiable nor
assignable, and that they cannot be passed as parameters nor
used as return values. Even today, however, I'll often use them
as class members or static variables---the latter generally in
order to ensure static initiallization.)
Which in the general case is not a problem. And if it becomes one, you
can adapt accordingly after profiling.
B) Memory access on stack is more cache friendly.
Really ? Perhaps in case of stack cache. And supposing your cache is big
enough to hold your container plus part of the stack.
If you have more than one, then if the memory is on the stack,
it is probably contiguous (at least on the usual processors
today), which means better locality. Of course, depending on
the implementation, successive allocations, at least if they are
the same size, are often contiguous as well.
The above facts make me want to try using STL like containers which
are able to store their data on stack. Is anybody familiar with such
container implementations? Any opinions about them?
*STL like* containers are not needed, you can directly use the STL with
a custom allocator. However, IMHO I wouldn't expect a great improovement
since you would have to re-implement a heap-like allocation algotithm.
If the size is known at compile time, then it's possible to
write a container which doesn't use any allocator at all, like
boost::array. If the size is supposed to be a class invariant,
not being able to change it is an advantage. If you're using
some sort of container to implement Point3D, for example,
there's no risk of a programming error resulting in a Point3D
having 2 or 4 dimensions, instead of the desired 3.
And additional benefit is that something like
std::vector< Point3D >( 1000000 ) ;
will only do a single allocation, and not a million of them.
The only exception would be in some specific cases to use a pool/shunk
scheme which is already proposed (see boost for exemple).
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34