C++ STL in embedded systems

[Alex Vinokur]

Are there any restrictions/problems for use of C++ STL in development
in embedded systems?
In particular:
* Does STL require too much space/memory?
* Is 'implementation of STL algorithms/methods' reenterable/reentrant?
* What is the cost to provide continuity of vectors in memory?
Any other problems?

--
Alex Vinokur
email: alex DOT vinokur AT gmail DOT com
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

[Mike Wahler]

"Alex Vinokur" <al****@users.s ourceforge.net> wrote in message
news:11******** **************@ g14g2000cwa.goo glegroups.com.. .

Are there any restrictions/problems for use of C++ STL in development
in embedded systems?
Perhaps. That depends upon the implementation and
the platform (and perhaps other criteria, such as
the nature of your application).
In particular:
* Does STL require too much space/memory?
How much is too much? Also note that each specific
standard library implementation may consume different
amounts of resources.
* Is 'implementation of STL algorithms/methods' reenterable/reentrant?
That depends upon the implementation.
* What is the cost to provide continuity of vectors in memory?
Not sure what you mean my 'continuity'. However, the elements
of a std::vector object are required to be contiguous in memory.
Any other problems?

Perhaps.

-Mike

[Victor Bazarov]

Alex Vinokur wrote:

Are there any restrictions/problems for use of C++ STL in development
in embedded systems?
I think I am confused by the use of the second 'in' here. Do you mean
'for' or 'on'? If you develop elsewhere and then install your program
to run on an embedded system, that's "for". If you try to compile your
program so that the compiler is running right there, it would be "on"
an embedded system. Which one are you interested in?
In particular:
* Does STL require too much space/memory?
You need to define "too much". However, generally speaking, the library
design is such that the objects do not introduce enormous overhead.

Since most of the Standard library is templatised, the compiler does need
more memory for processing the code that does use templates than code that
does not. So, the difference usually exists during compile-time and not
in run-time.
* Is 'implementation of STL algorithms/methods' reenterable/reentrant?
Generally, probably yes. However, the Standard says that non-reentrancy
is implementation-defined (17.4.4.5). Look in the documentation for your
compiler.
* What is the cost to provide continuity of vectors in memory?
I don't understand the question. Vectors are contiguous. Each vector
object requires some memory for itself and then some overhead exists for
dynamic array allocation. That's essentially the cost.
Any other problems?

I have no answer here, but I am sure others who program for embedded
systems, do.

V

[Alex Vinokur]

Victor Bazarov wrote:

Alex Vinokur wrote:

Are there any restrictions/problems for use of C++ STL in development
in embedded systems?
I think I am confused by the use of the second 'in' here. Do you mean
'for' or 'on'? If you develop elsewhere and then install your program
to run on an embedded system, that's "for".

It should be 'for'.
Thanks.
If you try to compile your
program so that the compiler is running right there, it would be "on"
an embedded system. Which one are you interested in?

In particular:
* Does STL require too much space/memory?
You need to define "too much".

I would like to know of experience of people working with STL for
embedded systems.
Are there hard/insoluble problems related to issue?
However, generally speaking, the library
design is such that the objects do not introduce enormous overhead.

Since most of the Standard library is templatised, the compiler does need
more memory for processing the code that does use templates than code that
does not. So, the difference usually exists during compile-time and not
in run-time.

* Is 'implementation of STL algorithms/methods' reenterable/reentrant?

Generally, probably yes. However, the Standard says that non-reentrancy
is implementation-defined (17.4.4.5). Look in the documentation for your
compiler.

* What is the cost to provide continuity of vectors in memory?

I don't understand the question. Vectors are contiguous. Each vector
object requires some memory for itself and then some overhead exists for
dynamic array allocation. That's essentially the cost.

Let v be of vector<in> type.
For instance, at the moment v.size() = 10000.
Now we do the following thing:
for (int i; i < 20000; i++) v.push_back(i);

Must 'v' be reallocated/copied to provide its continuity for v.size()
== 30000.

P.S. By the way, does similar continuity problem exist for ordinary
array?
[snip]

Alex Vinokur
email: alex DOT vinokur AT gmail DOT com
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

[Victor Bazarov]

Alex Vinokur wrote:

[...]
Let v be of vector<in> type.
For instance, at the moment v.size() = 10000.
What's v.capacity() ?
Now we do the following thing:
for (int i; i < 20000; i++) v.push_back(i);

Must 'v' be reallocated/copied to provide its continuity for v.size()
== 30000.
Unknown. Depends on the capacity.
P.S. By the way, does similar continuity problem exist for ordinary
array?

Ordinary array has a fixed size, and no 'push_back' member function, so,
no, such problem does not exist there.

V

[mlimber]

Alex Vinokur wrote:

Victor Bazarov wrote:

Alex Vinokur wrote: [snip]

* Does STL require too much space/memory?
You need to define "too much".

I would like to know of experience of people working with STL for
embedded systems.
Are there hard/insoluble problems related to issue?

Presumably you mean, "Are there hard/insoluble problems related to
[this] issue [i.e., too much memory being required]?"

I have used STL on several different processors on embedded systems,
and I have had no problems related to memory usage that wouldn't have
also been incurred by statically allocated or new/malloc allocated
memory. However, problems related to std::vector certainly could be
incurred on an embedded (or other non-embedded!) system, especially
because of its exponential memory allocation strategy. Some embedded
systems have tighter memory requirements than others, so it will
entirely depend on your requirements. However, see below on how to
mitigate potential memory issues.

[snip]

* What is the cost to provide continuity of vectors in memory?

I don't understand the question. Vectors are contiguous. Each vector
object requires some memory for itself and then some overhead exists for
dynamic array allocation. That's essentially the cost.

Let v be of vector<in> type.
For instance, at the moment v.size() = 10000.
Now we do the following thing:
for (int i; i < 20000; i++) v.push_back(i);

Must 'v' be reallocated/copied to provide its continuity for v.size()
== 30000.

std::vector allocates memory exponentially to "amortize" the growing
cost over time. Consequently, when you do your first push_back, vector
will double its size (i.e., allocate a second buffer of double the
size, copy the existing data into it, and then delete the first
buffer), and when you exceed the new size, it will double it again to
40000. So this will (1) waste memory if the vector doesn't grow any
more beyond that, (2) take up some extra memory while you're doing the
copy, and (3) possibly fragment memory beyond repair.

If you know how big it will grow (or even approximately how big), you
can use std::vector<>:: reserve() to set the initial capacity, which
will help minimize copying. If you do not know how big the size will
grow and std::vector's memory allocation scheme doesn't work well for
your system, you should probably not use them.
P.S. By the way, does similar continuity problem exist for ordinary
array?

Yes, and it must be done by hand, which is more error prone. However,
you do then control the memory allocation strategy and could make it
something other than exponential if your system demands it (e.g., add
some predefined amount to the current size, allocate that mem, and then
copy the old into the new; or use some sort of "chunk allocator", where
non-contiguous chunks are tracked by a linked list; etc.).

Cheers! --M

[mlimber]

mlimber wrote:

Alex Vinokur wrote:

Victor Bazarov wrote:

Alex Vinokur wrote:

[snip] Let v be of vector<in> type.
For instance, at the moment v.size() = 10000.
Now we do the following thing:
for (int i; i < 20000; i++) v.push_back(i);

Must 'v' be reallocated/copied to provide its continuity for v.size()
== 30000.

std::vector allocates memory exponentially to "amortize" the growing
cost over time. Consequently, when you do your first push_back, vector
will double its size (i.e., allocate a second buffer of double the
size, copy the existing data into it, and then delete the first
buffer), and when you exceed the new size, it will double it again to
40000.

[snip]

Note: This discussion assumed that v.size() == v.capacity().

Cheers! --M

[Alex Colvin]

>> Are there any restrictions/problems for use of C++ STL in development

in embedded systems?
You might want to think about exception handling.
* Does STL require too much space/memory?
for a small system, yes. But if you need the functionality, it's probably
better than writing it yourself.
Any other problems?

I ran into trouble some years back with microsoft's VC++ implementation
not being reentrant. <string> reference counts were seeing race
conditions. STLPort seemed to fix the problem. But replacing shared
<string> with (const char*) really helped.


--
mac the naïf

[mlimber]

Alex Colvin wrote:

Are there any restrictions/problems for use of C++ STL in development
in embedded systems?

You might want to think about exception handling.

[snip]

Good point. On some of my embedded projects, the compiler didn't
support exceptions at all, and so, neither did the STL. Of course, such
an implementation is not fully conformant to the standard, but it was
still very useful. And some parts of the STL don't throw exceptions
anyway (e.g., std::auto_ptr, many algorithms).

Cheers! --M

[Alex Colvin]

>> >> Are there any restrictions/problems for use of C++ STL in development

>> in embedded systems?
You might want to think about exception handling.

[snip]

Good point. On some of my embedded projects, the compiler didn't
support exceptions at all, and so, neither did the STL. Of course, such
an implementation is not fully conformant to the standard, but it was
still very useful. And some parts of the STL don't throw exceptions
anyway (e.g., std::auto_ptr, many algorithms).

I'm with the Embedded C++ folks <http://www.caravan.net/ec2plus/> on this.
I think that the minimum "contract" for a method call is that it return.
But your needs may differ.

As to conformance, I don't know that I've run across a fully conformant
compiler/runtime yet. As implementations like GCC approach conformance,
their libraries have to keep changing.

The result seems to be that C++ has become unstable. You can't link
against a library unless you're using the same compiler version. It's best
if you have all the libraries in source.
--
mac the naïf