C++ STL in embedded systems

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • Alex Vinokur

    #1

    C++ STL in embedded systems

    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://sourceforge.net/users/alexvn

  • Mike Wahler

    #2
    Re: C++ STL in embedded systems

    "Alex Vinokur" <alexvn@users.s ourceforge.net> wrote in message
    news:1136314025 .374598.239200@ g14g2000cwa.goo glegroups.com.. .[color=blue]
    > Are there any restrictions/problems for use of C++ STL in development
    > in embedded systems?[/color]

    Perhaps. That depends upon the implementation and
    the platform (and perhaps other criteria, such as
    the nature of your application).
    [color=blue]
    > In particular:
    > * Does STL require too much space/memory?[/color]

    How much is too much? Also note that each specific
    standard library implementation may consume different
    amounts of resources.
    [color=blue]
    > * Is 'implementation of STL algorithms/methods' reenterable/reentrant?[/color]

    That depends upon the implementation.
    [color=blue]
    > * What is the cost to provide continuity of vectors in memory?[/color]

    Not sure what you mean my 'continuity'. However, the elements
    of a std::vector object are required to be contiguous in memory.
    [color=blue]
    > Any other problems?[/color]

    Perhaps.

    -Mike


    Comment

    • Victor Bazarov

      #3
      Re: C++ STL in embedded systems

      Alex Vinokur wrote:[color=blue]
      > Are there any restrictions/problems for use of C++ STL in development
      > in embedded systems?[/color]

      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?
      [color=blue]
      > In particular:
      > * Does STL require too much space/memory?[/color]

      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.
      [color=blue]
      > * Is 'implementation of STL algorithms/methods' reenterable/reentrant?[/color]

      Generally, probably yes. However, the Standard says that non-reentrancy
      is implementation-defined (17.4.4.5). Look in the documentation for your
      compiler.
      [color=blue]
      > * What is the cost to provide continuity of vectors in memory?[/color]

      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.
      [color=blue]
      > Any other problems?[/color]

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

      V

      Comment

      • Alex Vinokur

        #4
        Re: C++ STL in embedded systems


        Victor Bazarov wrote:[color=blue]
        > Alex Vinokur wrote:[color=green]
        > > Are there any restrictions/problems for use of C++ STL in development
        > > in embedded systems?[/color]
        >
        > 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".[/color]

        It should be 'for'.
        Thanks.
        [color=blue]
        > 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?
        >[color=green]
        > > In particular:
        > > * Does STL require too much space/memory?[/color]
        >
        > You need to define "too much".[/color]

        I would like to know of experience of people working with STL for
        embedded systems.
        Are there hard/insoluble problems related to issue?
        [color=blue]
        > 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.
        >[color=green]
        > > * Is 'implementation of STL algorithms/methods' reenterable/reentrant?[/color]
        >
        > Generally, probably yes. However, the Standard says that non-reentrancy
        > is implementation-defined (17.4.4.5). Look in the documentation for your
        > compiler.
        >[color=green]
        > > * What is the cost to provide continuity of vectors in memory?[/color]
        >
        > 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.[/color]

        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://sourceforge.net/users/alexvn

        Comment

        • Victor Bazarov

          #5
          Re: C++ STL in embedded systems

          Alex Vinokur wrote:[color=blue]
          > [...]
          > Let v be of vector<in> type.
          > For instance, at the moment v.size() = 10000.[/color]

          What's v.capacity() ?
          [color=blue]
          > 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.[/color]

          Unknown. Depends on the capacity.
          [color=blue]
          > P.S. By the way, does similar continuity problem exist for ordinary
          > array?[/color]

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

          V

          Comment

          • mlimber

            #6
            Re: C++ STL in embedded systems

            Alex Vinokur wrote:[color=blue]
            > Victor Bazarov wrote:[color=green]
            > > Alex Vinokur wrote:[/color][/color]
            [snip][color=blue][color=green][color=darkred]
            > > > * Does STL require too much space/memory?[/color]
            > >
            > > You need to define "too much".[/color]
            >
            > I would like to know of experience of people working with STL for
            > embedded systems.
            > Are there hard/insoluble problems related to issue?[/color]

            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][color=blue][color=green][color=darkred]
            > > > * What is the cost to provide continuity of vectors in memory?[/color]
            > >
            > > 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.[/color]
            >
            > 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.[/color]

            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.
            [color=blue]
            > P.S. By the way, does similar continuity problem exist for ordinary
            > array?[/color]

            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

            Comment

            • mlimber

              #7
              Re: C++ STL in embedded systems

              mlimber wrote:[color=blue]
              > Alex Vinokur wrote:[color=green]
              > > Victor Bazarov wrote:[color=darkred]
              > > > Alex Vinokur wrote:[/color][/color][/color]
              [snip][color=blue][color=green]
              > > 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.[/color]
              >
              > 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.[/color]
              [snip]

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

              Cheers! --M

              Comment

              • Alex Colvin

                #8
                Re: C++ STL in embedded systems

                >> Are there any restrictions/problems for use of C++ STL in development[color=blue][color=green]
                >> in embedded systems?[/color][/color]

                You might want to think about exception handling.
                [color=blue][color=green]
                >> * Does STL require too much space/memory?[/color][/color]

                for a small system, yes. But if you need the functionality, it's probably
                better than writing it yourself.
                [color=blue][color=green]
                >> Any other problems?[/color][/color]

                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

                Comment

                • mlimber

                  #9
                  Re: C++ STL in embedded systems

                  Alex Colvin wrote:[color=blue][color=green][color=darkred]
                  > >> Are there any restrictions/problems for use of C++ STL in development
                  > >> in embedded systems?[/color][/color]
                  >
                  > You might want to think about exception handling.[/color]
                  [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

                  Comment

                  • Alex Colvin

                    #10
                    Re: C++ STL in embedded systems

                    >> >> Are there any restrictions/problems for use of C++ STL in development[color=blue][color=green][color=darkred]
                    >> >> in embedded systems?[/color]
                    >>
                    >> You might want to think about exception handling.[/color]
                    >[snip][/color]
                    [color=blue]
                    >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).[/color]

                    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

                    Comment

                    • Shezan Baig

                      #11
                      Re: C++ STL in embedded systems

                      Alex Vinokur wrote:[color=blue]
                      > 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?[/color]



                      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-

                      Comment

                      • Evan Carew

                        #12
                        Re: C++ STL in embedded systems

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

                        Alex Vinokur wrote:[color=blue]
                        > 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?[/color]
                        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

                        iD8DBQFDu0FwpxC QXwV2bJARAsm+AJ 0c3bCEdHDsiKzEh M6AEk3PIBYtvACe NRTa
                        jB2W3uidBsbZsns ViEz7eB0=
                        =bBVe
                        -----END PGP SIGNATURE-----

                        Comment

                        • Alex Vinokur

                          #13
                          Re: C++ STL in embedded systems


                          Victor Bazarov wrote:[color=blue]
                          > Alex Vinokur wrote:[color=green]
                          > > [...]
                          > > Let v be of vector<in> type.
                          > > For instance, at the moment v.size() = 10000.[/color]
                          >
                          > What's v.capacity() ?
                          >[color=green]
                          > > 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.[/color]
                          >
                          > Unknown. Depends on the capacity.[/color]

                          Is the capacity is too big, will 'v' be reallocated/copied?
                          [color=blue]
                          >[color=green]
                          > > P.S. By the way, does similar continuity problem exist for ordinary
                          > > array?[/color]
                          >
                          > Ordinary array has a fixed size, and no 'push_back' member function, so,
                          > no, such problem does not exist there.[/color]
                          [snip]

                          I meant use of 'realloc'.

                          Alex Vinokur
                          email: alex DOT vinokur AT gmail DOT com

                          http://sourceforge.net/users/alexvn

                          Comment

                          • Victor Bazarov

                            #14
                            Re: C++ STL in embedded systems

                            Alex Vinokur wrote:[color=blue]
                            > Victor Bazarov wrote:[color=green]
                            >> Alex Vinokur wrote:[color=darkred]
                            >>> [...]
                            >>> Let v be of vector<in> type.
                            >>> For instance, at the moment v.size() = 10000.[/color]
                            >>
                            >> What's v.capacity() ?
                            >>[color=darkred]
                            >>> 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.[/color]
                            >>
                            >> Unknown. Depends on the capacity.[/color]
                            >
                            > Is the capacity is too big, will 'v' be reallocated/copied?[/color]

                            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.
                            [color=blue][color=green][color=darkred]
                            >>> P.S. By the way, does similar continuity problem exist for ordinary
                            >>> array?[/color]
                            >>
                            >> Ordinary array has a fixed size, and no 'push_back' member function,
                            >> so, no, such problem does not exist there.[/color]
                            > [snip]
                            >
                            > I meant use of 'realloc'.[/color]

                            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


                            Comment

                            • Hans-Bernhard Broeker

                              #15
                              Re: C++ STL in embedded systems

                              In comp.arch.embed ded Alex Colvin <alexc@theworld .com> wrote:
                              [color=blue]
                              > The result seems to be that C++ has become unstable.[/color]

                              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 (broeker@physik .rwth-aachen.de)
                              Even if all the snow were burnt, ashes would remain.

                              Comment

                              Working...