stack vs. heap. a loaded question.

Discussion in 'C++' started by Dan Elliott, Nov 17, 2004.

  1. Dan Elliott

    Dan Elliott Guest

    Hello all,

    I am writing a program which needs to run as quickly as possible, but holds
    a lot of data in memory (around 1GB for a usual run). Is this too much
    memory to even consider putting most/all of it on the stack? Does it
    matter?

    Any considerations I might take into account when deciding how to allocate
    the many data structures? By the way, the system will consist of a handful
    of very large data structures (primarily matrices and vectors).

    Historically, I have always used the heap. This was more a result of my C
    background than anything else. However, I am now writing a system which
    will use only C++ and OO practices. Therefore, I feel I have a new choice
    to make. Amy assistance to make this design as efficient as possible would
    be greatly appreciated.

    Thank you,

    dan elliott
     
    Dan Elliott, Nov 17, 2004
    #1
    1. Advertising

  2. Dan Elliott napisa³:
    > Hello all,
    >
    > I am writing a program which needs to run as quickly as possible, but holds
    > a lot of data in memory (around 1GB for a usual run). Is this too much
    > memory to even consider putting most/all of it on the stack? Does it
    > matter?
    >
    > Any considerations I might take into account when deciding how to allocate
    > the many data structures? By the way, the system will consist of a handful
    > of very large data structures (primarily matrices and vectors).
    >
    > Historically, I have always used the heap. This was more a result of my C
    > background than anything else. However, I am now writing a system which
    > will use only C++ and OO practices. Therefore, I feel I have a new choice
    > to make. Amy assistance to make this design as efficient as possible would
    > be greatly appreciated.
    >


    C++ has no concept of heap or stack (well, not in the meaning you
    have used, anyway), but <OT> usually the data allocated via
    new or malloc will end up on the heap. The stack is used for
    local objects which should not be too large. The stack is
    usually limited to at most a few MB, often less. </OT>

    Therefore I suggest you allocate from the heap:

    void foo() {
    bigmatrix Matrices[1000]; // allocates on the stack, no-go
    }

    vod goo() {
    bigmatrix* Matrices =new bigmatrix[1000]; // allocates on the heap, ok

    // don't forget to "delete[] Matrices", when you're done
    }

    I suspect you have a custom matrix or vector class? If not,
    you might want to use std::vector<> for your data.

    HTH,
    - J.
     
    Jacek Dziedzic, Nov 17, 2004
    #2
    1. Advertising

  3. Dan Elliott wrote:
    > I am writing a program which needs to run as quickly as possible
    > but holds a lot of data in memory (around 1GB for a usual run).
    > Is this too much memory
    > to even consider putting most/all of it on the stack?


    How would you "put it on the stack"?

    > Does it matter?


    Use automatic storage [the stack] if you have lots of small objects.
    Using automatic storage for large objects [> 1GByte]
    might not be such a good idea.

    > Any considerations I might take into account
    > when deciding how to allocate the many data structures?
    > By the way, the system will consist of a handful
    > of very large data structures (primarily matrices and vectors).


    Unless you are planning to use variable size arrays
    to represent vectors and matrices, you will be allocating memory
    from free storage for these objects anyway.

    > Historically, I have always used the heap.
    > This was more a result of my C background than anything else.
    > However, I am now writing a system which will use only C++ and OO practices.
    > Therefore, I feel I have a new choice to make.


    I don't think so.
    I think that you are confused.
    All of the vector and matrix classes for large objects
    allocate memory from free storage.

    > Any assistance to make this design as efficient as possible
    > would be greatly appreciated.


    Take a look at
    The Scalar, Vector, Matrix and Tensor class Library

    http://www.netwood.net/~edwin/svmtl/

    then visit
    The Object-Oriented Numerics Page

    http://www.oonumerics.org/oon/
     
    E. Robert Tisdale, Nov 17, 2004
    #3
  4. On Wed, 17 Nov 2004 22:02:58 +0100, Jacek Dziedzic wrote:

    > Dan Elliott
    >> Hello all,
    >>
    >> I am writing a program which needs to run as quickly as possible, but holds
    >> a lot of data in memory (around 1GB for a usual run). Is this too much
    >> memory to even consider putting most/all of it on the stack? Does it
    >> matter?
    >>
    >> Any considerations I might take into account when deciding how to allocate
    >> the many data structures? By the way, the system will consist of a handful
    >> of very large data structures (primarily matrices and vectors).
    >>
    >> Historically, I have always used the heap. This was more a result of my C
    >> background than anything else. However, I am now writing a system which
    >> will use only C++ and OO practices. Therefore, I feel I have a new choice
    >> to make. Amy assistance to make this design as efficient as possible would
    >> be greatly appreciated.
    >>

    >
    > C++ has no concept of heap or stack (well, not in the meaning you
    > have used, anyway), but <OT> usually the data allocated via
    > new or malloc will end up on the heap. The stack is used for
    > local objects which should not be too large. The stack is
    > usually limited to at most a few MB, often less. </OT>
    >
    > Therefore I suggest you allocate from the heap:
    >
    > void foo() {
    > bigmatrix Matrices[1000]; // allocates on the stack, no-go
    > }
    >
    > vod goo() {
    > bigmatrix* Matrices =new bigmatrix[1000]; // allocates on the heap, ok
    >
    > // don't forget to "delete[] Matrices", when you're done
    > }
    >
    > I suspect you have a custom matrix or vector class? If not,
    > you might want to use std::vector<> for your data.
    >
    > HTH,
    > - J.


    Thank you for the response. So, as a general rule, large objects should
    be allocated on the "heap?" In what way is the "stack" limited in size
    that the "heap" is not? I sorry if this is something I should have
    learned as an undergrad.

    This question became especially salient in my mind when reading about the
    uBLAS library. They mention that a particular data structure will
    allocate matrices on automatic storage (stack in my terminology) which
    is better than free store.

    Thanks again for making my stay in system design hell a little brighter.

    - dan
     
    Daniel L Elliott, Nov 17, 2004
    #4
  5. On Wed, 17 Nov 2004 13:03:24 -0800, E. Robert Tisdale wrote:

    > Dan Elliott wrote:
    >> I am writing a program which needs to run as quickly as possible
    >> but holds a lot of data in memory (around 1GB for a usual run).
    >> Is this too much memory
    >> to even consider putting most/all of it on the stack?

    >
    > How would you "put it on the stack"?
    >
    >> Does it matter?

    >
    > Use automatic storage [the stack] if you have lots of small objects.
    > Using automatic storage for large objects [> 1GByte]
    > might not be such a good idea.
    >
    >> Any considerations I might take into account
    >> when deciding how to allocate the many data structures?
    >> By the way, the system will consist of a handful
    >> of very large data structures (primarily matrices and vectors).

    >
    > Unless you are planning to use variable size arrays
    > to represent vectors and matrices, you will be allocating memory
    > from free storage for these objects anyway.
    >
    >> Historically, I have always used the heap.
    >> This was more a result of my C background than anything else.
    >> However, I am now writing a system which will use only C++ and OO practices.
    >> Therefore, I feel I have a new choice to make.

    >
    > I don't think so.
    > I think that you are confused.
    > All of the vector and matrix classes for large objects
    > allocate memory from free storage.
    >
    >> Any assistance to make this design as efficient as possible
    >> would be greatly appreciated.

    >
    > Take a look at
    > The Scalar, Vector, Matrix and Tensor class Library
    >
    > http://www.netwood.net/~edwin/svmtl/
    >
    > then visit
    > The Object-Oriented Numerics Page
    >
    > http://www.oonumerics.org/oon/


    Thank you for the information. I am planning to use uBLAS which can do
    either free or automatic storage.

    None of my individual vector or matrices will occupy more than, perhaps,
    50MB. However, all told, the vectors and matrices could easily total over
    1GB of data.

    Do you still suggest that I use the heap exclusively. Would it be
    sensable to use the automatic storage whenever advisable (still not sure
    when that would be)?

    Is access to free-store slower? What are the incentives for using
    automatic storage?

    Thank you, everyone, for your time.

    - dan elliott
     
    Daniel L Elliott, Nov 17, 2004
    #5
  6. Daniel L Elliott wrote:

    > E. Robert Tisdale wrote:
    >
    >>Dan Elliott wrote:
    >>
    >>>I am writing a program which needs to run as quickly as possible
    >>>but holds a lot of data in memory (around 1GB for a usual run).
    >>>Is this too much memory
    >>>to even consider putting most/all of it on the stack?

    >>
    >>How would you "put it on the stack"?
    >>
    >>>Does it matter?

    >>
    >>Use automatic storage [the stack] if you have lots of small objects.
    >>Using automatic storage for large objects [> 1GByte]
    >>might not be such a good idea.
    >>
    >>>Any considerations I might take into account
    >>>when deciding how to allocate the many data structures?
    >>>By the way, the system will consist of a handful
    >>>of very large data structures (primarily matrices and vectors).

    >>
    >>Unless you are planning to use variable size arrays
    >>to represent vectors and matrices, you will be allocating memory
    >>from free storage for these objects anyway.
    >>
    >>>Historically, I have always used the heap.
    >>>This was more a result of my C background than anything else.
    >>>However, I am now writing a system which will use only C++ and OO practices.
    >>>Therefore, I feel I have a new choice to make.

    >>
    >>I don't think so.
    >>I think that you are confused.
    >>All of the vector and matrix classes for large objects
    >>allocate memory from free storage.
    >>
    >>>Any assistance to make this design as efficient as possible
    >>>would be greatly appreciated.

    >>
    >>Take a look at
    >>The Scalar, Vector, Matrix and Tensor class Library
    >>
    >> http://www.netwood.net/~edwin/svmtl/
    >>
    >>then visit
    >>The Object-Oriented Numerics Page
    >>
    >> http://www.oonumerics.org/oon/

    >
    >
    > Thank you for the information. I am planning to use uBLAS which can do
    > either free or automatic storage.
    >
    > None of my individual vector or matrices will occupy more than, perhaps,
    > 50MB. However, all told, the vectors and matrices could easily total over
    > 1GB of data.
    >
    > Do you still suggest that I use the heap exclusively. Would it be
    > sensable to use the automatic storage whenever advisable (still not sure
    > when that would be)?
    >
    > Is access to free-store slower? What are the incentives for using
    > automatic storage?
    >
    > Thank you, everyone, for your time.


    Take a look at the TinyVector and TinyMatrix classes in Blitz++

    http://www.oonumerics.org/blitz/examples/
     
    E. Robert Tisdale, Nov 17, 2004
    #6
  7. Dan Elliott

    Prash Guest

    Re: stack vs. heap. a loaded question.

    Object allocation on Heap or Stack have nothing much to do with C or
    C++. It is more of a design issue independent of the language.

    There are a few things which you need to consider while choosing the
    option. Object creation and deletion on stack is faster than that on
    Heap; but once the objects are created there is no difference in access
    times required for objects on stack or on heap.

    Stack is there for automatic variables and its size is limited. So, I
    suggest that you use heap for your data storage. If have performace to
    consider then see to it that object creation and deletion might take
    some time and you should minimize on that; like instead of allocation
    10 small memory chunks, you can create a larger chunk of memory and
    then divide it by urself.

    Also, I'd suggest you not to use variable sized arrays as they are
    implemented in libraries using lists or something and access to them is
    definetly slower than the fixed sized conventional arrays.

    Also maybe u can have a look at the GNU Scientific library as an option
    for components. www.gnu.org/software/gsl/
     
    Prash, Nov 18, 2004
    #7
  8. Re: stack vs. heap. a loaded question.

    Prash wrote:

    > Stack is there for automatic variables and its size is limited.
    > So, I suggest that you use heap for your data storage.


    Actually, automatic storage [the program stack]
    and free storage [the heap] share the same virtual memory.
    The typical program stack grows up from the bottom of virtual memory
    and the heap grows downward to the top of the stack.

    The stack size may be limited but can be easily increased
    using shell commands or compiler options.
    For example, on a Linux workstation:

    > limit stacksize

    stacksize 10240 kbytes
    > limit stacksize unlimited
    > limit stacksize

    stacksize unlimited

    > If [you] have performace to consider, then see to it that some time
    > object creation and deletion might take and you should minimize on that;
    > like, instead of allocation 10 small memory chunks,
    > you can create a larger chunk of memory and then divide it by yourself.
    >
    > Also, I'd suggest you not to use variable sized arrays
    > as they are implemented in libraries using lists or something
    > and access to them is definetly slower
    > than the fixed sized conventional arrays.


    No!

    C99 style variable size arrays

    http://gcc.gnu.org/ml/gcc/2004-05/msg00746.html

    are allocated from free storage [the stack]
    and have performance characteristics similar to "conventional arrays".

    > Also, maybe you can have a look at the GNU Scientific library
    > as an option for components. www.gnu.org/software/gsl/


    You may as well check out
    the Vector, Signal and Image Processing Library

    http://www.vsipl.org/

    or, better yet,
    the High Performance Embedded Computing Software Initiative

    http://www.hpec-si.org/

    which actually proposes a C++ language binding.
     
    E. Robert Tisdale, Nov 18, 2004
    #8
  9. "Dan Elliott" <> wrote in message news:<8MOmd.4$>...
    > Hello all,
    >
    > I am writing a program which needs to run as quickly as possible, but holds
    > a lot of data in memory (around 1GB for a usual run). Is this too much
    > memory to even consider putting most/all of it on the stack? Does it
    > matter?


    I assume with that with 'stack' you mean allocations like:
    void foo () {
    int x[BIG];
    }
    and with heap you mean
    void bar () {
    int* ax = new int[BIG];
    delete[] ax;
    }

    In that case, the answer is that you should use the latter.

    However, in C++ the issue you probably want
    void foobar() {
    std::deque<int> x(BIG);
    }
    if you could use both. You don't have to clean up, and there are
    less size limits. In fact, std::deque is likely to support larger
    arrays than new.

    If you pass them around, be aware that copying a std::deque is rather
    expensive. In such cases a boost::shared_array class might help
    (www.boost.org)

    Regards,
    Michiel Salters
     
    Michiel Salters, Nov 18, 2004
    #9
  10. Daniel L Elliott wrote:

    > In what way is the "stack" limited in size
    > that the "heap" is not? I sorry if this is something I should have
    > learned as an undergrad.


    As far as I understand it, upon the start of your program a fixed
    amount of memory is denoted as 'stack' and the rest of the memory
    is denoted as heap. In that way, stack is usually limited to a
    certain amount -- often only 1MB in order not to waste too much
    memory that could be used as heap (because you can't shrink the
    stack if it is not used).

    That way you get a limited amount of stack storage. This can
    bite you in a cruel manner if you don't remember about it.
    Under Linux, when the stack is overfilled you usually only
    get "Aborted" and your program dies instantly.

    The size of the stack is usually controlled via a compiler
    switch.

    You might try to run these two programs:

    // program 1
    // This tries to have a 50MB structure on stack
    // Will most likely crash
    void foo() {
    char bigarray[50000000];
    bigarray[0]=0; // use bigarray to make sure the
    // compiler does not optimize it away
    }

    int main() {
    foo();
    }

    // program 2
    // This tries to allocate a 50MB structure on the heap
    // Will most likely succeed, if you have 50MB spare memory
    #include<iostream>
    void foo() {
    try{
    char* bigarray = new char[50000000];
    }
    catch(std::bad_alloc) {
    std::cerr << "Shit, not enough memory" << std::endl;
    }
    // use bigarray here...
    }

    int main() {
    foo();
    }

    HTH,
    - J.
     
    Jacek Dziedzic, Nov 19, 2004
    #10
  11. Re: stack vs. heap. a loaded question.

    Thank you for the education everyone! These excellent posts will help me
    create the best-possible design.

    - dan elliott

    On Wed, 17 Nov 2004 19:57:17 -0800, E. Robert Tisdale wrote:

    > Prash wrote:
    >
    >> Stack is there for automatic variables and its size is limited.
    >> So, I suggest that you use heap for your data storage.

    >
    > Actually, automatic storage [the program stack]
    > and free storage [the heap] share the same virtual memory.
    > The typical program stack grows up from the bottom of virtual memory
    > and the heap grows downward to the top of the stack.
    >
    > The stack size may be limited but can be easily increased
    > using shell commands or compiler options.
    > For example, on a Linux workstation:
    >
    > > limit stacksize

    > stacksize 10240 kbytes
    > > limit stacksize unlimited
    > > limit stacksize

    > stacksize unlimited
    >
    >> If [you] have performace to consider, then see to it that some time
    >> object creation and deletion might take and you should minimize on that;
    >> like, instead of allocation 10 small memory chunks,
    >> you can create a larger chunk of memory and then divide it by yourself.
    >>
    >> Also, I'd suggest you not to use variable sized arrays
    >> as they are implemented in libraries using lists or something
    >> and access to them is definetly slower
    >> than the fixed sized conventional arrays.

    >
    > No!
    >
    > C99 style variable size arrays
    >
    > http://gcc.gnu.org/ml/gcc/2004-05/msg00746.html
    >
    > are allocated from free storage [the stack]
    > and have performance characteristics similar to "conventional arrays".
    >
    >> Also, maybe you can have a look at the GNU Scientific library
    >> as an option for components. www.gnu.org/software/gsl/

    >
    > You may as well check out
    > the Vector, Signal and Image Processing Library
    >
    > http://www.vsipl.org/
    >
    > or, better yet,
    > the High Performance Embedded Computing Software Initiative
    >
    > http://www.hpec-si.org/
    >
    > which actually proposes a C++ language binding.
     
    Daniel L Elliott, Nov 19, 2004
    #11
  12. Ah yes! Very helpful. Thank you.

    - dan elliott

    On Fri, 19 Nov 2004 16:23:33 +0100, Jacek Dziedzic wrote:

    > Daniel L Elliott wrote:
    >
    >> In what way is the "stack" limited in size
    >> that the "heap" is not? I sorry if this is something I should have
    >> learned as an undergrad.

    >
    > As far as I understand it, upon the start of your program a fixed
    > amount of memory is denoted as 'stack' and the rest of the memory
    > is denoted as heap. In that way, stack is usually limited to a
    > certain amount -- often only 1MB in order not to waste too much
    > memory that could be used as heap (because you can't shrink the
    > stack if it is not used).
    >
    > That way you get a limited amount of stack storage. This can
    > bite you in a cruel manner if you don't remember about it.
    > Under Linux, when the stack is overfilled you usually only
    > get "Aborted" and your program dies instantly.
    >
    > The size of the stack is usually controlled via a compiler
    > switch.
    >
    > You might try to run these two programs:
    >
    > // program 1
    > // This tries to have a 50MB structure on stack
    > // Will most likely crash
    > void foo() {
    > char bigarray[50000000];
    > bigarray[0]=0; // use bigarray to make sure the
    > // compiler does not optimize it away
    > }
    >
    > int main() {
    > foo();
    > }
    >
    > // program 2
    > // This tries to allocate a 50MB structure on the heap
    > // Will most likely succeed, if you have 50MB spare memory
    > #include<iostream>
    > void foo() {
    > try{
    > char* bigarray = new char[50000000];
    > }
    > catch(std::bad_alloc) {
    > std::cerr << "Shit, not enough memory" << std::endl;
    > }
    > // use bigarray here...
    > }
    >
    > int main() {
    > foo();
    > }
    >
    > HTH,
    > - J.
     
    Daniel L Elliott, Nov 19, 2004
    #12
    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. joe

    stack and heap question

    joe, Aug 4, 2004, in forum: Java
    Replies:
    3
    Views:
    430
    Michael Borgwardt
    Aug 5, 2004
  2. Olumide
    Replies:
    14
    Views:
    813
  3. Michal Slocinski

    Heap dump file size vs heap size

    Michal Slocinski, Mar 25, 2008, in forum: Java
    Replies:
    1
    Views:
    739
    GArlington
    Mar 25, 2008
  4. viki
    Replies:
    6
    Views:
    566
    Erik Wikström
    Jun 28, 2008
  5. Raymond Schanks
    Replies:
    0
    Views:
    536
    Raymond Schanks
    Apr 11, 2010
Loading...

Share This Page