Memory footprint of std::vector<std::vector<T> >

Discussion in 'C++' started by Rune Allnor, Dec 10, 2008.

  1. Rune Allnor

    Rune Allnor Guest

    Hi all.

    I have a data structure which I naively implemented as
    std::vector<std::vector<T> >. Right now I'm testing it
    with 8000 vectors of vectors, each of which contain on the
    order of 1000 elements, ending up somewhere on the
    order of 350 MB of memory. I am nowhere near exhausting
    any meory limits.

    The program was compiled with default 'release' settings
    (VS2008) and takes forever to run.

    So I am curious about the memory footpint here. I am
    aware that the elements of a std::vector occupy a continuous
    block of memory. Is this memory assigned dynamically
    or is *everything* in the std::vector assigned as one
    dynamic block?

    That is, are the internal control variables etc located in a
    memory block 'close' to the data values of the vector,
    or can the data values be located somewhere else
    (e.g. on the heap)?

    That is, if everything is one continuous block of memory,
    all the data might have to be copied to new areas of
    memory as the vectors grow. Which might explain
    why the thing takes so long to run.

    Rune
     
    Rune Allnor, Dec 10, 2008
    #1
    1. Advertising

  2. Rune Allnor

    Guest

    On Dec 10, 9:24 am, Rune Allnor <> wrote:
    > Hi all.
    >
    > I have a data structure which I naively implemented as
    > std::vector<std::vector<T> >.  Right now I'm testing it
    > with 8000 vectors of vectors, each of which contain on the
    > order of 1000 elements, ending up somewhere on the
    > order of 350 MB of memory. I am nowhere near exhausting
    > any memory limits.

    <snip>
    > That is, if everything is one continuous block of memory,
    > all the data might have to be copied to new areas of
    > memory as the vectors grow. Which might explain
    > why the thing takes so long to run.


    You have 8000 contiguous blocks of memory here (each sub-vector). If
    you can pre-size :reserve(): them, you can reduce the amount of memory
    allocation while your program is running.

    I would bet all the tea in china that the locality of the vector class
    with the associated data is not your problem. Minimizing memory
    reallocations is really the goal here; especially in your tightest
    loops.

    Joe
     
    , Dec 10, 2008
    #2
    1. Advertising

  3. wrote:
    > You have 8000 contiguous blocks of memory here (each sub-vector). If
    > you can pre-size :reserve(): them, you can reduce the amount of memory
    > allocation while your program is running.


    If you can't do that (eg. because you don't have any idea what the
    sizes of the vectors will be), then you can use std::deque instead of
    std::vector. In general std::deque will cause less memory fragmentation
    and thus consume less memory in cases were the size of the container is
    incremented little by little.

    (OTOH std::deque cannot be used if you really need for the memory
    blocks to be contiguous, eg. because you are using them as raw arrays
    somewhere.)
     
    Juha Nieminen, Dec 10, 2008
    #3
  4. On Dec 10, 3:24 pm, Rune Allnor <> wrote:

    > I have a data structure which I naively implemented as
    > std::vector<std::vector<T> >.  Right now I'm testing it
    > with 8000 vectors of vectors, each of which contain on the
    > order of 1000 elements, ending up somewhere on the
    > order of 350 MB of memory. I am nowhere near exhausting
    > any meory limits.
    >
    > The program was compiled with default 'release' settings
    > (VS2008) and takes forever to run.


    Starting from VS2005, Microsoft has introduced a new feature called
    "checked iterators" that affect several STL classes.
    As a consequence, every time you access an element of std::vector<T>,
    the vector bounds are checked.
    The situation is even worse for std::vector<std::vector<T> > because
    double checks are performed (I think it requires 4 comparison for
    every element access).

    In order to disable this "feature", you should set the symbol
    _SECURE_SCL to 0 before including the stl headers.
    This is an example taken from MSDN:

    // checked_iterators_4.cpp
    // compile with: /EHsc
    #define _SECURE_SCL 0
    #include <vector>
    #include <iostream>
    using namespace std;
    int main() {
    vector<int> v;
    v.push_back(67);
    int i = v[0];
    cout << i << endl;
    };

    Apart from this, I suggest you to turn on all the optimizations (in
    particular SSE2, it can make a big difference).

    Regards,
    The Librarian
     
    The Librarian, Dec 10, 2008
    #4
  5. Rune Allnor

    Rune Allnor Guest

    On 10 Des, 23:35, The Librarian <> wrote:
    > On Dec 10, 3:24 pm, Rune Allnor <> wrote:
    >
    > > I have a data structure which I naively implemented as
    > > std::vector<std::vector<T> >.  Right now I'm testing it
    > > with 8000 vectors of vectors, each of which contain on the
    > > order of 1000 elements, ending up somewhere on the
    > > order of 350 MB of memory. I am nowhere near exhausting
    > > any meory limits.

    >
    > > The program was compiled with default 'release' settings
    > > (VS2008) and takes forever to run.

    >
    > Starting from VS2005, Microsoft has introduced a new feature called
    > "checked iterators" that affect several STL classes.
    > As a consequence, every time you access an element of std::vector<T>,
    > the vector bounds are checked.
    > The situation is even worse for std::vector<std::vector<T> > because
    > double checks are performed (I think it requires 4 comparison for
    > every element access).
    >
    > In order to disable this "feature", you should set the symbol
    > _SECURE_SCL to 0 before including the stl headers.
    > This is an example taken from MSDN:
    >
    > // checked_iterators_4.cpp
    > // compile with: /EHsc
    > #define _SECURE_SCL 0
    > #include <vector>
    > #include <iostream>
    > using namespace std;
    > int main() {
    >    vector<int> v;
    >    v.push_back(67);
    >    int i = v[0];
    >    cout << i << endl;
    >
    > };
    >
    > Apart from this, I suggest you to turn on all the optimizations (in
    > particular SSE2, it can make a big difference).


    The SSE2 optimization seems to have at least halved the
    data load + processing time.

    The #define _SECURE_SCL 0 trick caused a segmentation
    fault when I used it only in the main trasnslation unit;
    it might work better if I include it in every file.

    I'll have to try the std::deque and reserve() on the
    vectors, although there is probably more time to be
    saved by reimplementing some of the processing routines,
    although these don't take very long (about the same time
    it takes to convert from text to binary numbers when
    I tested the program with a different setup).

    When I run the program I watch memory consumption in
    the task manager. The numbers update approximately
    twice per second.

    From 0 MB data loaded to about 200 MB data loaded,
    the memory ticker increases about 1.7-1.8 MB/update.
    After 200MB it increases about 0.3-0.4 MB/update.
    Which is why I suspected reallocations of continuous
    blocks of memory to be the culprit.

    BTW, is there a way to adjust the size of the ifstream
    buffer? I know I will be working with files with
    sizes on the order of hundreds of MBytes, so I can
    just as well allocate, say, 10 MB for the stream buffer
    up front to reduce overhead on file I/O.

    Rune
     
    Rune Allnor, Dec 11, 2008
    #5
    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. gbrun
    Replies:
    1
    Views:
    467
    Andrey Kuznetsov
    Feb 19, 2006
  3. Replies:
    8
    Views:
    2,005
    Csaba
    Feb 18, 2006
  4. Varun  Kacholia

    STL vector memory footprint

    Varun Kacholia, Mar 18, 2006, in forum: C++
    Replies:
    12
    Views:
    3,081
    Mark P
    Mar 21, 2006
  5. nick
    Replies:
    58
    Views:
    1,985
    Bart van Ingen Schenau
    Mar 16, 2009
Loading...

Share This Page