C++ STL in embedded systems

Discussion in 'C++' started by Alex Vinokur, Jan 3, 2006.

  1. Alex Vinokur

    Alex Vinokur Guest

    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
     
    Alex Vinokur, Jan 3, 2006
    #1
    1. Advertising

  2. 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
     
    Victor Bazarov, Jan 3, 2006
    #2
    1. Advertising

  3. Alex Vinokur

    Mike Wahler Guest

    "Alex Vinokur" <> wrote in message
    news:...
    > 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
     
    Mike Wahler, Jan 3, 2006
    #3
  4. Alex Vinokur

    Alex Vinokur Guest

    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
     
    Alex Vinokur, Jan 3, 2006
    #4
  5. 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
     
    Victor Bazarov, Jan 3, 2006
    #5
  6. Alex Vinokur

    mlimber Guest

    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, Jan 3, 2006
    #6
  7. Alex Vinokur

    mlimber Guest

    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
     
    mlimber, Jan 3, 2006
    #7
  8. Alex Vinokur

    Alex Colvin Guest

    >> 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
     
    Alex Colvin, Jan 3, 2006
    #8
  9. Alex Vinokur

    mlimber Guest

    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
     
    mlimber, Jan 3, 2006
    #9
  10. Alex Vinokur

    Alex Colvin Guest

    >> >> 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
     
    Alex Colvin, Jan 3, 2006
    #10
  11. Alex Vinokur

    Shezan Baig Guest

    Alex Vinokur wrote:
    > 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?




    One thing to note here, you might not be able to use a particular
    standard library implementation, but you can certainly use the STL
    concepts. As long as you have some class that models the concepts in
    STL, you should be able to use many of the standard library algorithms
    without any problems.

    I think the major overhead comes from iostreams, locales etc.

    Hope this helps,
    -shez-
     
    Shezan Baig, Jan 4, 2006
    #11
  12. Alex Vinokur

    Evan Carew Guest

    -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    Alex Vinokur wrote:
    > 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?

    In the any category, the main criticism for using a straight C++ lib,
    let alone STL, is that the stock new() is non-deterministic. I hear tho
    that there are certain embedded C++ tool chains which might have some
    methods of getting around this. At least, in the early 90's I remember
    Chrysler getting into one for one of its auto controllers.
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.0.6 (GNU/Linux)
    Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

    iD8DBQFDu0FwpxCQXwV2bJARAsm+AJ0c3bCEdHDsiKzEhM6AEk3PIBYtvACeNRTa
    jB2W3uidBsbZsnsViEz7eB0=
    =bBVe
    -----END PGP SIGNATURE-----
     
    Evan Carew, Jan 4, 2006
    #12
  13. Alex Vinokur

    Alex Vinokur Guest

    Victor Bazarov wrote:
    > 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.


    Is the capacity is too big, will 'v' be reallocated/copied?

    >
    > > 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.

    [snip]

    I meant use of 'realloc'.

    Alex Vinokur
    email: alex DOT vinokur AT gmail DOT com
    http://mathforum.org/library/view/10978.html
    http://sourceforge.net/users/alexvn
     
    Alex Vinokur, Jan 4, 2006
    #13
  14. Alex Vinokur wrote:
    > Victor Bazarov wrote:
    >> 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.

    >
    > Is the capacity is too big, will 'v' be reallocated/copied?


    I would rather use the words "large enough" instead of "too big", but
    if what you meant was "if the capacity is larger than 30000", then no
    reallocation would be necessary.

    >>> 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.

    > [snip]
    >
    > I meant use of 'realloc'.


    I don't understand this statement. Use of 'realloc' for what?
    'realloc' allocates another object and copies the contents. It is
    a _deliberate_ action. There is no automatic growing of arrays.

    And, according to the Standard, 'realloc' returns a pointer to
    a _new_ object (array), whereas the original one is deallocated.
    There is no analogy with 'std::vector' whatsoever. But do look
    at an implementation of one.

    V
     
    Victor Bazarov, Jan 4, 2006
    #14
  15. In comp.arch.embedded Alex Colvin <> wrote:

    > The result seems to be that C++ has become unstable.


    Whaddayamean, "become"? From where I sit, C++ feels like it has been
    a moving target ever since its invention. Its defining standards
    change faster than the implementations. Each time the implementors
    finally seem to be catching up, the goal is moved.

    --
    Hans-Bernhard Broeker (-aachen.de)
    Even if all the snow were burnt, ashes would remain.
     
    Hans-Bernhard Broeker, Jan 4, 2006
    #15
  16. Alex Vinokur

    Alex Vinokur Guest

    Victor Bazarov wrote:

    [snip]

    > 'realloc' allocates another object and copies the contents. It is
    > a _deliberate_ action. There is no automatic growing of arrays.
    >
    > And, according to the Standard, 'realloc' returns a pointer to
    > a _new_ object (array), whereas the original one is deallocated.
    > There is no analogy with 'std::vector' whatsoever.


    How is 'continuity of vectors in memory' provided? Without using
    reallocation/deallocation?

    [snip]

    Alex Vinokur
    email: alex DOT vinokur AT gmail DOT com
    http://mathforum.org/library/view/10978.html
    http://sourceforge.net/users/alexvn
     
    Alex Vinokur, Jan 4, 2006
    #16
  17. Alex Vinokur

    Shezan Baig Guest

    Alex Vinokur wrote:
    > > 'realloc' allocates another object and copies the contents. It is
    > > a _deliberate_ action. There is no automatic growing of arrays.

    >
    > How is 'continuity of vectors in memory' provided? Without using
    > reallocation/deallocation?



    "automatically" :)

    Seriously though, the way vectors grow is just an implementation detail
    - different implementations will do it differently - only the semantics
    are consistent across implementations.

    In your case, if you *do* care about the way it is implemented, then I
    would suggest try to find (if possible) a standard library
    implementation that's intended to be used in an embedded system. Or
    you also might find more convenient to use a custom allocator if you
    have memory constraints (be aware of type incompatibilities though,
    with the existing C++ standard). If you have other constraints (apart
    from memory constraints) then roll out your own "vector", implemented
    with whatever contraints you have.


    Hope this helps,
    -shez-
     
    Shezan Baig, Jan 4, 2006
    #17
  18. Alex Vinokur

    mlimber Guest

    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).

    >
    > 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.


    It depends entirely on the needs of the particular embedded systems.
    Some of today's embedded systems use yesterday's desktop processors,
    and consequently, they often have more memory available, have compiler
    and standard library with relatively good conformance to the C++03
    Standard, and are less susceptible to the kind of problems that the OP
    was concerned about.

    On the other hand, I have successfully used a subset of the STL
    (including std::vector) on an embedded system that has stricter
    requirements than "high-end" embedded applications. The compiler for
    that system doesn't support exceptions or some other C++ features
    (yet), but otherwise, it is fairly good as far as conformance.

    > As to conformance, I don't know that I've run across a fully conformant
    > compiler/runtime yet.


    No fully conformant compiler cum library exists, though some are close
    and are available on a wide variety of platforms (GNU, Comeau, etc.).
    But things are getting better IMHO, and many of the remaining
    non-conformancies are in areas of the Standard that are not as useful
    as they first appeared (e.g., the export keyword).

    In any case, I write object-oriented C++ code that uses the STL that is
    buildable on several different embedded platforms with different
    compilers, and I use a commercial lint tool that helps maximize the
    portability (as well as check for errors). The bottom line for me is
    that, while C++ compilers and libraries are not fully conformant, they
    are conformant enough for my needs (and I suspect for many other
    programmers' needs).

    > As implementations like GCC approach conformance,
    > their libraries have to keep changing.


    Can you give an example? The library implementations might be refined
    or tweaked behind the scenes, but the interfaces should generally be
    stable.

    > 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.


    I'm not sure what you mean here. I don't think you mean that different
    compilers generate different object file formats or that they use
    different calling conventions since these problems would apply equally
    to any language, but are you referring to the fact that, e.g., a
    library function might throw an exception but your compiler doesn't
    support exceptions? Please clarify.

    Cheers! --M
     
    mlimber, Jan 4, 2006
    #18
  19. Alex Vinokur

    mlimber Guest

    Alex Vinokur wrote:
    > Victor Bazarov wrote:
    >
    > [snip]
    >
    > > 'realloc' allocates another object and copies the contents. It is
    > > a _deliberate_ action. There is no automatic growing of arrays.
    > >
    > > And, according to the Standard, 'realloc' returns a pointer to
    > > a _new_ object (array), whereas the original one is deallocated.
    > > There is no analogy with 'std::vector' whatsoever.

    >
    > How is 'continuity of vectors in memory' provided? Without using
    > reallocation/deallocation?


    std::vector does sometimes use the allocated-copy-destroy mechanism
    while it is growing (see my other post for more details). std::realloc
    does a similar thing with malloc'ed memory and POD types when the size
    passed to std::realloc is larger than the current size. The difference
    is that std::vector works on non-POD types as well.

    You might be interested in these articles by Andrei Alexandrescu:

    http://www.cuj.com/documents/s=7992/cujcexp1908alexandr/alexandr.htm
    http://www.cuj.com/documents/s=7990/cujcexp1910alexandr/alexandr.htm
    http://www.cuj.com/documents/s=7988/cujcexp1912alexandr/alexandr.htm

    They describe generic typed buffers, which are somewhere in between
    built-in arrays (which are evil; see the FAQ) and std::vector, which
    may not have acceptable performance for certain applications. The third
    discusses realloc and growing in gory detail.

    Cheers! --M
     
    mlimber, Jan 4, 2006
    #19
  20. Alex Vinokur

    JustBoo Guest

    On 3 Jan 2006 10:47:05 -0800, "Alex Vinokur"
    <> wrote:
    >Are there any restrictions/problems for use of C++ STL in development
    >in embedded systems?


    Hey look what I just found, from their website:

    The Dinkum EC++ Library as specified by the Embedded C++ Technical
    Committee. (See the Dinkum EC++ Library.) This is far and away the
    most widely used EC++ library in the embedded programming community.

    http://www.dinkumware.com/libdual_vc.html

    Good Luck.

    Not all those who wander are lost. - J.R.R. Tolkien
     
    JustBoo, Jan 4, 2006
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. merodeshpyarocha

    embedded systems...

    merodeshpyarocha, Apr 20, 2004, in forum: Java
    Replies:
    2
    Views:
    368
    chris
    Apr 21, 2004
  2. Mike
    Replies:
    2
    Views:
    650
  3. Replies:
    0
    Views:
    446
  4. news.mot.com
    Replies:
    0
    Views:
    377
    news.mot.com
    Nov 19, 2003
  5. Alex Vinokur
    Replies:
    10
    Views:
    549
    Alex Vinokur
    Apr 1, 2006
Loading...

Share This Page