[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

Memory footprint of std::vector >

Rune Allnor

12/10/2008 2:24:00 PM

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
9 Answers

joseph cook

12/10/2008 2:45:00 PM

0

On Dec 10, 9:24 am, Rune Allnor <all...@tele.ntnu.no> 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

Juha Nieminen

12/10/2008 9:46:00 PM

0

joecook@gmail.com 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.)

The Librarian

12/10/2008 10:35:00 PM

0

On Dec 10, 3:24 pm, Rune Allnor <all...@tele.ntnu.no> 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

Rune Allnor

12/11/2008 5:45:00 PM

0

On 10 Des, 23:35, The Librarian <7h3.l1br4r...@gmail.com> wrote:
> On Dec 10, 3:24 pm, Rune Allnor <all...@tele.ntnu.no> 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

Stephen Howe

12/11/2008 6:40:00 PM

0

>BTW, is there a way to adjust the size of the ifstream
>buffer?

Yup, like setvbuf for stdio :

ifFile.rdbuf()->pubsetbuf(NULL, yoursize);

Stephen Howe

Paavo Helde

12/11/2008 9:53:00 PM

0

Rune Allnor <allnor@tele.ntnu.no> kirjutas:
>
> 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.

Sure, otherwise disaster happens; I would expect at least different name
mangling schemes for binarily incompatible functions, to get linker errors
instead of runtime crashes in such situations. Alas, it seems I must be
living in a dream world.

Paavo

sheldonlg

6/25/2014 12:36:00 PM

0

On 6/25/2014 2:25 AM, news wrote:
> Statistically more prone to winning Nobel prizes would be more
> accurate.

Its not the "Jewish genes". It is the "Jewish culture of promoting
education".

--
Shelly

news

6/25/2014 1:26:00 PM

0

On Tue, 24 Jun 2014 15:26:01 +0000 (UTC), "Evertjan."
<exxjxw.hannivoort@inter.nl.net> wrote:

>"news" <news@fx28.iad.highwinds-media.com> wrote on 24 jun 2014 in
>soc.culture.jewish.moderated:
>
>>>Being a Jew 'IS not' a convenant. Jews have a convenant, the bris.
>>
>> Do you really not understand English? It clearly says above that
>> *conversion* is a covenant with God.
>
>How christian! "it is written" above/somewhere, so it is true?

Not 'it is written' but 'it says'. It may or may not be true, but
that's what it says: 'conversion is a covenant', NOT 'being a Jew is
a covenant'. It is up to you to understand it. Apparently, you
didn't.

--
Francis Xavier Turlough
University of the Witwatersrand
Johannesburg
South Africa

news

6/25/2014 1:28:00 PM

0

On Tue, 24 Jun 2014 19:58:54 +0000 (UTC), Yisroel Markov
<ey.markov@MUNGiname.com> wrote:

>On Tue, 24 Jun 2014 05:17:32 +0000 (UTC), "news"
><news@fx07.iad.highwinds-media.com> said:
>
>>On Thu, 19 Jun 2014 07:45:03 +0000 (UTC), mm <mm2005@bigfoot.com>
>>wrote:
>
>[snip]
>
>>>Therefore it's not true that anything one can enter at will can be
>>>abandoned at will.
>>
>>Strawman. I didn't say that. I was specifically referring to
>>conversion to Judaism.
>>
>>>Therefore there is no basis to assume your previous
>>>quoted line is true.
>>
>>Misinterpretation. In the case of religion and conversion, it IS
>>true.
>
>"There are no 'facts' here, only opinions, definitions, and toothless
>'laws'." Therefore, IMHO one can't state the above as anything other
>than an opinion.

Indeed. And if anyone has a different opinion, they are welcome to
present it. As long as it's based on reality and doesn't rely on 'God
said so' or 'that's Jewish law' as an argument.

>>>>>>What possible claim can the Jewish
>>>>>>people have on him?
>>>>>
>>>>>This is not an answer about claim. Claim is not my word.
>>>>
>>>>It's a word that others have used.
>>>
>>>But except for that one time, not me. I plan not to use it again.
>>
>>OK.
>>
>>>>>He's a Jew.
>>>>
>>>>Of course he's not. He's turned his back on Judaism.
>>>
>>>Doesn't matter. You agree that if he were a born-Jew it wouldn't
>>>matter, so clearly turning one's back on Judaism is not necessarily
>>>enough to make one not a Jew. To insist it is for converts, for the
>>>reason you've given, is simplistic and contrary to the facts.
>>
>>A born Jew cannot, obviously, turn his back on being a Jew. The DNA
>>can't change. But a convert definitely can turn his back. There are
>>no 'facts' here, only opinions, definitions, and toothless 'laws'.
>
>Right. Now suppose a childless couple converts to Judaism and has a
>child. Then they convert to something else, while the child refuses.
>What is the child's status according to you?

The way I see it, the child would have to convert to become a Jew in
the first place. Simply being the child of a convert is insufficient.

>What about the same case, but only one spouse had converted while the
>other has born Jew DNA (whatever that means)?

Half-Jewish, then. Just as would be the case for Italian or Irish
heritage. I know that this isn't an accepted concept, but
realistically, that's what it is.

>>>>>Although I used the word "claim" myself this one time, right after
>>>>>"OTOH" above, following my habit of trying to make my replies reflect
>>>>>what I'm replying to, I've never, before Yisroel said it, heard the
>>>>>attitude of other Jews to one Jew called a claim**. Anyhow, the
>>>>>convert's status as a Jew doesn't depend on any claim**.
>>>>>
>>>>>You do know, don't you, that as part of conversion, or even maybe prior
>>>>>to the start of it, the prospective convert is told that it's
>>>>>irreversible. He goes into it knowing it's irreversible, but still he
>>>>>agrees to it all (or he woudn't be a convert to begin with) . Are you
>>>>>claiming these converts are not men and women of their word?
>>>>
>>>>I'm not making any claims about such people. But it clearly IS
>>>>reversible.
>>>
>>>It's not clear. It's not even true.
>>
>>It certainly is.
>
>"There are no 'facts' here, only opinions, definitions, and toothless
>'laws'." Therefore, IMHO one can't state the above as anything other
>than an opinion.

Indeed. As above.

>BTW, suppose the law did have teeth somehow. So John becomes Yohanan,
>then decides he wants to be John again. The halakhic police won't let
>him, but he sneaks to the local church, converts in secret, and lives
>as a crypto-Christian. What is his status according to you? What was
>that of the marranos, for that matter?

Purely hypothetical. If Jewish 'law' had teeth, we'd be in a totally
different situation and we wouldn't be having this discussion.

--
Francis Xavier Turlough
University of the Witwatersrand
Johannesburg
South Africa