Exponential memory consumption growth using std::vector

Question

I'm developing a program which needs to be memory efficient. I have used std::vector in my program to store a large number of elements. But, I noticed that the program's memory size grows exponentially when the number of elements are chosen large. For example I wrote the following code:

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int vecSize;
    cin >> vecSize;
    vector<double> a(vecSize);
    return 0;
}

Then I monitored the memory consumption using the gnu time command like this:

/usr/bin/time -f "Mem: %M" a.out

This is the memory results I have got for different vector sizes:

VecSize       MemUsage
10:           4720 KB
100:          4720 KB
1000:         4736 KB
10000:        5024 KB
100000:       7744 KB
1000000:      35872 KB
10000000:     317120 KB

Does anybody know why the memory usage is growing so much fast when the number of elements are chosen more than 100000?

http://stackoverflow.com/questions/11560904/vector-memory-allocation-strategy — didierc, Dec 01 '14 at 08:06

druckermanly · Accepted Answer · 2014-12-01T08:19:10.880

8

MSalters was right, and I can't read!

The answer is very simple. To me, the growth seems linear.

You picked VecSize that increase exponentially. You should expect MemUsage to increase exponentially as well! (in the large n limit-- small size optimizations likely exist, as evidenced by the near constant usage for small n...)

I did a linear regression on the data out of curiosity, and the correlation coefficient was 1.0-- indicating that the relation between VecSize and MemUsage (as posted) is (most likely... don't kill me statisticians) linear.

Regression! :)

edited Dec 01 '14 at 08:19

answered Dec 01 '14 at 08:07

druckermanly

2,694
15
27

`+1` for 1. being faster and 2. applying a formal analysis method :-) – Angew is no longer proud of SO Dec 01 '14 at 08:09
1

As an aside, there's nearly a factor of 4 in allocator-overhead. Probably setting aside a pool for additional requests there... – Deduplicator Dec 01 '14 at 08:11
2

"formal" hah! This is formal so long as nobody from stats.stackexchange.com comes along :) – druckermanly Dec 01 '14 at 08:11
1

"*I disagree with MSalters-- I believe the answer is much more simple. To me, the growth seems linear.*" That's exactly what MSalters said – "*You just initialize a vector with exponentially increasing sizes. Its size is linear in the sire requested.*" The part you seem to be confused about ("*The runtime growth has to be exponential*") is entirely correct in respect to a _growing_ vector. – ildjarn Dec 01 '14 at 08:14
@ildjarn Thanks, reading comprehension is hard! He was right all along. Sorry to be rude @MSalters! However, I think MSalters was misinterpreting the question asker's misinterpretation (to get a little meta). The question asker expected to see linear growth as he made (unknowingly-- my assumption!) exponential growing vecsizes. – druckermanly Dec 01 '14 at 08:20
@user2899162 : I think you're misinterpreting the OP's misinterpretation too. ;-D I think the confusion is why the memory usage isn't linear _under_ 1000000 elements, but only Angew has addressed that. – ildjarn Dec 01 '14 at 08:22

score 4 · Answer 2 · answered Dec 01 '14 at 08:03

The runtime growth has to be exponential, for push_back to be amortized O(1). If you'd grow one element at a time, growing a 100.000 element vector would take 100.000 element copies.

However, in this case the vector doesn't grow at all. You just initialize a vector with exponentially increasing sizes. Its size is linear in the sire requested. No surprise there.

score 4 · Answer 3 · answered Dec 01 '14 at 08:08

I can't see any exponential growth in the numbers. Size going from 10^5 to 10^6 (10x) increases memory consumption roughly 5x. Going from 10^6 to 10^7 (10x) increaes memory consumption roughly 10x. So it's linear.

The first few numbers (small vector sizes) play little role here - the memory used by the vector is probably dominated by other needs of your program and its runtime. And as soon as you get past that and the vector size starts to dominate, you get roughly linear scaling, so all is well.

Upvote for the second paragraph, which I think is the relevant answer. — ildjarn, Dec 01 '14 at 08:33

Exponential memory consumption growth using std::vector

3 Answers3