Is this caused by memory fragmentation? If yes, why did that happen?

Question

Environment:

Memory Limit: 512 MB

Run the following code, will finish smoothly:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>

using namespace std;

int main() {
    long long N;

    vector<long long> set3;
    for(long long i = 1; i < 20000000; ++i) {
        set3.push_back(i);
    }
    cout << "count:" << set3.size() << " capacity:" << set3.capacity() << endl;

    vector<long long> set5;
    for(long long i = 1; i < 12000000; ++i) {
        set5.push_back(i);
    }
    cout << "count:" << set5.size() << " capacity:" << set5.capacity() << endl;

    return 0;
}

If I swap set3 and set5, it will fail by exception:

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Here is the failed code:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>

using namespace std;

int main() {
    long long N;

    vector<long long> set5;
    for(long long i = 1; i < 12000000; ++i) {
        set5.push_back(i);
    }
    cout << "count:" << set5.size() << " capacity:" << set5.capacity() << endl;

    vector<long long> set3;
    for(long long i = 1; i < 20000000; ++i) {
        set3.push_back(i);
    }
    cout << "count:" << set3.size() << " capacity:" << set3.capacity() << endl;

    return 0;
}

Why?

Here is another successful case, we can even succeeded in allocating 370 MB by vector::assign

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>

using namespace std;

int main() {
    long long N;

    vector<long long> set5;
    for(long long i = 1; i < 12000000; ++i) {
        set5.push_back(i);
    }
    cout << "count:" << set5.size() << " capacity:" << set5.capacity() << endl;


    vector<long long> set3;
    //set3.assign(49807360, 0); // fail: 49807360 * 64 / 8 / 1024 / 1024 == 380 MB
    set3.assign(48496640, 0); // succeed: 48496640 * 64 / 8 / 1024 / 1024 == 370 MB
    /*
     for(long long i = 1; i < 20000000; ++i) {
     set3.push_back(i);
     }
     */
    cout << "count:" << set3.size() << " capacity:" << set3.capacity() << endl;

    return 0;
}

Why does memory allocation by vector's push_back (causing memory increase from 128MB to 256MB) fail on 384 MB; while vector.assign(370MB, much bigger than 256 MB) on the same 384 MB will succeed?

Is this a memory fragmentation issue?

In the successful case:

Allocate for set3: (by vector::push_back) 
    256 MB out of 512 MB ---- Good; 
then allocate for set5: (by vector::push_back) 
    128 MB out of the remaining 256 MB ---- Good;

In the failed case:

Allocate for set5: (by vector::push_back) 
    128 MB out of 512 MB ---- Good; 
then allocate for set3: (by vector::push_back) 
    256 MB out of the remaining 384 MB ---- Fail.

In another successful case:

Allocate for set5: (by vector::push_back) 
    128 MB out of 512 MB ---- Good; 
then allocate for set3: (by vector::assign) 
    370 MB out of the remaining 384 MB ---- Good.

Usually such appears when you have undefined behavior somewhere in your code. Use a debugger to narrow what happens. — πάντα ῥεῖ, Sep 19 '15 at 07:13
How can it give the same result if one throws an exception? A profiler won't help find bugs. — Jonathan Wakely, Sep 19 '15 at 11:00
Please construct a [minimal test-case](http://stackoverflow.com/help/mcve). — Oliver Charlesworth, Sep 19 '15 at 11:54
tl;dr. I don't understand what all the blurb about profiling and performance and "even using `time` and `difftime`" has to do with this? — Lightness Races in Orbit, Sep 19 '15 at 11:59
Is there a difference in `set5.capacity()` between both runs? I think in the failed example, `set5` overallocates more than in the second one, leaving less space for `set3`. Note that `set.size()` does NOT return how much memory is allocated but how much is used; you need to use `capacity()` to check how much is allocated. — StenSoft, Sep 19 '15 at 12:28
@milesma it can be caused by memory fragmentation. You might have more than 16777216 * sizeof(long long) bytes available, but not in a consecutive block — wimh, Sep 20 '15 at 10:16
You need to clean it up first. It's a mess of edits and irrelevant information (e.g. profiling data). Form it into a simple, single, coherent question. — Lightness Races in Orbit, Sep 20 '15 at 15:20
Other processes on the same machine are irrelevant for memory fragmentation, it's only your process' virtual memory space which might be getting fragmented. — Jonathan Wakely, Sep 21 '15 at 09:47
**Why the array refuse to increase capacity to go beyond a previous irrelevant array's capacity?** `std::vector` grows in a predictable pattern if you just keep using `push_back`, growing in size by a constant factor every time (typically a factor of two). So the first vector kept growing until it reached 16777216, and didn't need to grow more. The second vector needs to grow past that so probably tries to allocate 2 x 16777216 which fails. Use `reserve` on each vector before you start, that will pre-allocate, so it doesn't need to grow repeatedly. That should also make it run much faster. — Jonathan Wakely, Sep 21 '15 at 09:54
@JonathanWakely You are correct!! Just found out the hackerRank's environment indicated that the memory limit is 512 MB. In my example, the set5 already consumed: 128 MB; Now left 512 - 128 = 384 MB. Then comes the set3, it allocated 128MB when size is below 16777216, then it is trying to allocate more to be double the size: 2*16777216 = 256 MB; So allocate 256 MB out of 384 MB, failed. The succeeded case is: for set3 allocate 256 MB out of 512 MB, succeeded; now left 256 MB, then for set5 allocate 128 out of 256 MB, still succeeded. Cool! — milesma, Sep 21 '15 at 10:30
I'm not getting any errors whatsoever. Ran it with Valgrind too but nothing suspicious came out. I don't think that if indeed memory fragmentation is the culprit it is coming from the code directly. Vectors have a contiguous memory layout plus you are not allocating anything dynamically. You can read a small description about what happens when you call push_back at http://stackoverflow.com/a/7900003/1559401. I would also suggest if you have a memory limit of a known size that you implement this in your code. Here you can use the constructor of `std::vector` to give it the size you want. — rbaleksandar, Sep 21 '15 at 12:37

Is this caused by memory fragmentation? If yes, why did that happen?

0 Answers0