Searching for stack based containers

[jimxoch]

Hi list,

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. B) Memory access on stack is
more cache friendly.

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?

Thanks in advance,
Jim Xochellis

 

[Victor Bazarov]

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. B) Memory access on stack is
more cache friendly.

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?

Plenty of fixed-size vectors (like for K-dimensional geometry) must
use inline arrays for their storage. I have no real opinion about
those, and I can't think of any other containers that would actually
have their storage "stack based".

If you would like to experiment, I'd speculate that any container
with your custom allocator that preallocates a certain amount of
room "on stack" and then lets you reuse that memory should be a good
enough model.

V

 

[Michael DOUBEZ]

jimxoch a écrit :

Hi list,

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.

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.

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.

The only exception would be in some specific cases to use a pool/shunk
scheme which is already proposed (see boost for exemple).


Michael

 

[Pete Becker]

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?

TR1 provides an array template which puts its contents on the stack. It
holds a fixed-size array, which is really the only sort of thing you can
do on the stack.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Alf P. Steinbach]

* Pete Becker:

TR1 provides an array template which puts its contents on the stack. It
holds a fixed-size array, which is really the only sort of thing you can
do on the stack.

C99 manages variable length arrays on the stack just fine. I think you
meant "in current C++".

 

[Alf P. Steinbach]

* Alf P. Steinbach:

* Pete Becker:

C99 manages variable length arrays on the stack just fine. I think you
meant "in current C++".

And of course, I meant dynamic length.

 

[Alf P. Steinbach]

* Alf P. Steinbach:

* Alf P. Steinbach:

And of course, I meant dynamic length.

Grr, terminology. C99 uses the term "variable". I'm going out for a beer.

 

[Pete Becker]

* Pete Becker:

C99 manages variable length arrays on the stack just fine. I think you
meant "in current C++".

Since this is a C++ newsgroup, there's no need to say that.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[jimxoch]

Hi list,

Thank you very much for responding. After reading your responses, I am
now convinced that a custom allocator is sufficient enough for my
needs. I am going to try it asap.

Best regards
Jim Xochellis

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

* Pete Becker:

C99 manages variable length arrays on the stack just fine. I think you
meant "in current C++".

Correct me if I'm wrong but are they not only of dynamic length up to
the point where they were declared so to speak, meaning that you can do
something like this:

void foo(int n) {
int arr[n];
}

And after that the number of elements of arr is fixed to n (for whatever
n happened to be when foo() was called). While this is more that you can
currently do in C++ it's still not what I'd like to call dynamic since
it can't grow in size on demand (which no stackbased datastructure can
do unless you allocate lots of unused space to grow in).

 

[Alf P. Steinbach]

* Erik Wikström:

* Pete Becker:

C99 manages variable length arrays on the stack just fine. I think
you meant "in current C++".

Correct me if I'm wrong but are they not only of dynamic length up to
the point where they were declared so to speak, meaning that you can do
something like this:

void foo(int n) {
int arr[n];
}

And after that the number of elements of arr is fixed to n (for whatever
n happened to be when foo() was called).
yes


While this is more that you can
currently do in C++ it's still not what I'd like to call dynamic since
it can't grow in size on demand (which no stackbased datastructure can
do unless you allocate lots of unused space to grow in).

it's enough to be very useful, e.g. for string conversion. currently
language extensions such as _alloca are used instead. the point being
that there's no inherent technical constraint that makes this
impossible; it is in fact a very common language extension.

 

[James Kanze]

jimxoch a écrit :

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.

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.

*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