STL vector memory footprint

Discussion in 'C++' started by Varun Kacholia, Mar 18, 2006.

  1. Apologies if this has been answered somewhere, but Google did not
    produce any concrete
    results. I would like to find out the memory footprint of a vector<T>.

    I tried to dig in the STL code and if I understand correctly, its 3 *
    void(*) +
    sizeof(T) * size_of_vector. (3 ptrs for __M_start, __M_finish and
    __M_end_of_storage).
    If any STL guru could confirm my findings, that would be much
    appreciated.
    Also, if someone could throw in the memory numbers for STL hashmap and
    set,
    that would be great!

    Thanks.
     
    Varun Kacholia, Mar 18, 2006
    #1
    1. Advertising

  2. Varun Kacholia <> wrote:
    > Apologies if this has been answered somewhere, but Google did not
    > produce any concrete
    > results. I would like to find out the memory footprint of a vector<T>.
    >
    > I tried to dig in the STL code and if I understand correctly, its 3 *
    > void(*) +
    > sizeof(T) * size_of_vector. (3 ptrs for __M_start, __M_finish and
    > __M_end_of_storage).
    > If any STL guru could confirm my findings, that would be much
    > appreciated.
    > Also, if someone could throw in the memory numbers for STL hashmap and
    > set,
    > that would be great!


    What you dug up is specific to your implementation. Mine might be
    completely different. What is wrong with using sizeof (std::vector <T>)
    (where T is the type you are storing)?

    hth
    --
    jb

    (reply address in rot13, unscramble first)
     
    Jakob Bieling, Mar 18, 2006
    #2
    1. Advertising

  3. Varun Kacholia wrote:
    > I would like to find out the memory footprint of a vector<T>.
    > I tried to dig in the STL code and if I understand correctly, its 3 *
    > void(*) + sizeof(T) * size_of_vector.


    Essentially, '3 * sizeof(T*) + v.capacity() * sizeof(T)' is essentially
    the minimum storage requirement. There may be an additional word for
    the allocator which can be optimized away for the standard allocator
    but might require additional memory for other allocators.

    The memory footprint for 'std::set<T>' or 'std::tr1::unordered_set<T>'
    will be bigger per object and probably also per container. For
    'std::set<T>' the computation is probably something like
    '3 * sizeof(Node*) + s.size() * (sizeof(T) + 3 * sizeof(Node*) +
    sizeof(void*))'. This is effectively a pointer to the tree root, the
    left most and the right most tree nodes for the container. For each
    object, a node stores the object plus pointers to the left and right
    subtree and some representation of the relative balance e.g. colors
    "red" and "black" or some integer value. This effectively ends up to
    be the size of a pointer due to padding. An additional pointer would
    point to the parent of the node although this is not really
    necessary to meet the standard's performance requirements but would
    impede iteration. Depending on the allocator, an extra word per
    object might be necessary to contain the size of the memory block but
    this can be relatively easily avoided and be traded for something like
    one word for 'block / sizeof(Node)' elements.

    For 'std::tr1::unordered_set<T>' things become even more unclear: the
    hashing strategies can be rather different and there are various
    trade-offs with respect to object allocation and conflicts. This will
    affect both the container size and the per object size. I would
    expect that in general the overhead is a little bit smaller than that
    of the 'std::set<T>' but substantially bigger than that of
    'std::vector<T>'.

    What is your actual problem, BTW?
    --
    <mailto:> <http://www.dietmar-kuehl.de/>
    <http://www.eai-systems.com> - Efficient Artificial Intelligence
     
    Dietmar Kuehl, Mar 19, 2006
    #3
  4. > What is your actual problem, BTW?

    Trying to optimize the memory usage by comparing the consumption of
    different containers.

    jb: sizeof(vector<T>) wont work as STL containers allocate some memory
    on
    the heap too.
     
    Varun Kacholia, Mar 19, 2006
    #4
  5. Varun  Kacholia

    Ben Pope Guest

    Varun Kacholia wrote:
    >> What is your actual problem, BTW?

    >
    > Trying to optimize the memory usage by comparing the consumption of
    > different containers.
    >
    > jb: sizeof(vector<T>) wont work as STL containers allocate some memory
    > on
    > the heap too.


    vector has the smallest requirement per element of any of the containers.

    If vector suits your needs, then use that.

    If not, then what are your requirements?

    Ben Pope
    --
    I'm not just a number. To many, I'm known as a string...
     
    Ben Pope, Mar 19, 2006
    #5
  6. Varun Kacholia <> wrote:

    > jb: sizeof(vector<T>) wont work as STL containers allocate some memory
    > on
    > the heap too.


    Yes, I assumed you would add the size of the actual elements as you
    did in your original post.

    You are right tho, for other containers, this is admittingly not as
    simple. I did not think about those when answering.

    regards
    --
    jb

    (reply address in rot13, unscramble first)
     
    Jakob Bieling, Mar 19, 2006
    #6
  7. Ben,
    I understand that vector has the smallest requirement per element.
    However I
    was interested in finding out how much memory does it exactly require
    per
    element (since I am curious to find the exact numbers, and also I need
    to compare
    them with some alternate containers--similar to vector-- that we have)
     
    Varun Kacholia, Mar 19, 2006
    #7
  8. Varun  Kacholia

    Daniel T. Guest

    In article <>,
    "Varun Kacholia" <> wrote:

    > Apologies if this has been answered somewhere, but Google did not
    > produce any concrete
    > results. I would like to find out the memory footprint of a vector<T>.
    >
    > I tried to dig in the STL code and if I understand correctly, its 3 *
    > void(*) +
    > sizeof(T) * size_of_vector. (3 ptrs for __M_start, __M_finish and
    > __M_end_of_storage).
    > If any STL guru could confirm my findings, that would be much
    > appreciated.
    > Also, if someone could throw in the memory numbers for STL hashmap and
    > set,
    > that would be great!
    >
    > Thanks.


    The area of a vector (the total number of bytes it occupies) is sizeof(
    vector<T> ) + sizeof(T) * vec.capacity(). Understand though, there is no
    requirement for vector to reduce its area when elements are removed from
    it.



    --
    Magic depends on tradition and belief. It does not welcome observation,
    nor does it profit by experiment. On the other hand, science is based
    on experience; it is open to correction by observation and experiment.
     
    Daniel T., Mar 19, 2006
    #8
  9. Varun  Kacholia

    Ben Pope Guest

    Varun Kacholia wrote:
    > Ben, I understand that vector has the smallest requirement per
    > element. However I was interested in finding out how much memory does
    > it exactly require per element (since I am curious to find the exact
    > numbers, and also I need to compare them with some alternate
    > containers--similar to vector-- that we have)


    I'm pretty sure sure the element size of:
    std::vector<T>
    is
    sizeof(T)

    In just about every implementation (probably all), the underlying data
    structure is an array of T.

    Ben Pope
    --
    I'm not just a number. To many, I'm known as a string...
     
    Ben Pope, Mar 19, 2006
    #9
  10. Daniel, Thanks! That does sound fair enough. Any pointers as to going
    about
    measuring the memory footprint of STL map<X,Y>?
     
    Varun Kacholia, Mar 20, 2006
    #10
  11. Varun  Kacholia

    Rolf Magnus Guest

    Ben Pope wrote:

    > Varun Kacholia wrote:
    >> Ben, I understand that vector has the smallest requirement per
    >> element. However I was interested in finding out how much memory does
    >> it exactly require per element (since I am curious to find the exact
    >> numbers, and also I need to compare them with some alternate
    >> containers--similar to vector-- that we have)

    >
    > I'm pretty sure sure the element size of:
    > std::vector<T>
    > is
    > sizeof(T)


    However, the size of the allocated memory may be quite a bit larger. When
    push_back() decides to reallocate, it usually gets a block that is larger
    than required (often twice as large), so it doesn't need to reallocate each
    time. Another thing is that vectors don't shrink, so if you remove a lot of
    elements, the amount of allocated memory won't be reduced.
     
    Rolf Magnus, Mar 20, 2006
    #11
  12. Varun  Kacholia

    Daniel T. Guest

    In article <>,
    "Varun Kacholia" <> wrote:

    > Daniel, Thanks! That does sound fair enough. Any pointers as to going
    > about
    > measuring the memory footprint of STL map<X,Y>?


    std::map doesn't have a proscribed implementation like std::vector does.
    However all standard containers have a complexity guarantee in this
    regard... sizeof( container ) + (K + sizeof( element ) ) *
    container.size();

    What you are asking for is the value of K in the above equation. I
    suggest you ask the company that implemented the STL that you are using.


    --
    Magic depends on tradition and belief. It does not welcome observation,
    nor does it profit by experiment. On the other hand, science is based
    on experience; it is open to correction by observation and experiment.
     
    Daniel T., Mar 20, 2006
    #12
  13. Varun  Kacholia

    Mark P Guest

    Varun Kacholia wrote:
    > Daniel, Thanks! That does sound fair enough. Any pointers as to going
    > about
    > measuring the memory footprint of STL map<X,Y>?
    >


    One way to do this is to use an allocator that reports all of its
    allocations and deallocations. Try this one:

    http://www.josuttis.com/libbook/memory/myalloc.hpp.html

    Mark
     
    Mark P, Mar 21, 2006
    #13
    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. Beatrice Rutger

    JMS memory footprint size

    Beatrice Rutger, Jun 5, 2005, in forum: Java
    Replies:
    0
    Views:
    382
    Beatrice Rutger
    Jun 5, 2005
  2. francois
    Replies:
    1
    Views:
    465
    Peter Koch Larsen
    Dec 5, 2003
  3. Replies:
    8
    Views:
    2,002
    Csaba
    Feb 18, 2006
  4. Rune Allnor
    Replies:
    4
    Views:
    993
    Rune Allnor
    Dec 11, 2008
  5. nick
    Replies:
    58
    Views:
    1,980
    Bart van Ingen Schenau
    Mar 16, 2009
Loading...

Share This Page