Allocating a large multidimensional vector causes memory "overshoot"

Question

I observed an unexpected behavior when using a large multidmensional std::vector variable. In particular, when I allocate a 4-dimensional vector of large size, it can be seen, using a memory profiler, that my task shortly uses more memory than it would require for the variable.

An MWE to reproduce this behavior is the following:

#include <vector>
#include <iostream>

int main(int argc, char *argv[]){

    getchar();
    std::vector<std::vector<std::vector<std::vector<int64_t>>>> F(1, std::vector<std::vector<std::vector<int64_t>>>(15, std::vector<std::vector<int64_t>>(256, std::vector<int64_t>(100000, 0))));
    getchar();
}

The figure below shows the memory used by the task. The size of the array would require roughly 3GB, however the memory usage overshoots shortly to almost 6GB. Notice that the last dimension of the vector is the largest in size, meaning that the memory overhead from the vector class is relatively small.

This has been observed under Manjaro on a 64bit system, compiled with g++ (gcc version 11.1.0 (GCC)). I used psrecord to record the memory usage. Interestingly, I could not reproduce the same behavior for lower dimensional vectors. Even if I remove only the first dimension (which has size 1) I could not reproduce this overshoot on my system.

Does anyone have an idea where this comes from or if this can be avoided (without using a large 1 dimensional vector)? The main problem with this is that I am operating close to the maximum memory provided by my system, meaning that the short overshoot causes memory swapping.

I'll be glad about any ideas and comments. Thanks in advance.

This kind of debugging question is more suitable for [so] than Software Engineering. Hint: `std::vector::vector(size_t n, const T& value)` takes a *reference* to the value and *copies* it into every element. The outer constructor is called as `vector(1, 3gb_data_structure)`. Since a copy is made, 2× the expected memory usage sounds correct. — amon, Aug 19 '21 at 13:38
Is a vector of a vector of a vector of a vector really the best datastructure for this? It is fairly common to put at least some of the dimensions into a 1D buffer, with some custom indexing to provide multi-dimensional index. — JonasH, Aug 19 '21 at 14:43
@amon Thanks for your comments! I will keep the comment about the suitability in mind for future posts, thanks! That sounds actually quite plausible. I assume that there is some sort of vector or compiler optimization that avoids this copying for smaller dimensions, since otherwise I don't understand, why this happens only in the 4 dimensional case. — Andreas Lenz, Aug 19 '21 at 15:21
@JonasH Probably it is not. I will most likely implement it as a 1D or 2D vector in the future and write my own wrapper class for this. However, I was also curious what the problem with my current implementation is. Thanks! — Andreas Lenz, Aug 19 '21 at 15:22
`std::vector>>(1, std::vector>(256, std::vector(100000, 0)))` makes an object 3GB in size. You then copy that into `F`, so `F` is 3GB in size as well, consuming 6GB total. After that line ends, the temporary object is destroyed and then you drop back down to just 3GB being consumed. IMHO, the solution is to use a 1d vector. That doesn't mean you can't wrap that in a class that fakes that it has multiple dimensions, like this: https://stackoverflow.com/a/43358434/4342498 — NathanOliver, Aug 19 '21 at 15:38
@NathanOliver The copy happens because vector constructor takes parameter by const& and not &&? — Yksisarvinen, Aug 19 '21 at 15:41
@Yksisarvinen Yes. `vector` can't use `&&` here because it is making `N` copies of the value into the vector. If it moved, you could only make 1 object, not `N`. — NathanOliver, Aug 19 '21 at 15:42

Top-Master · Accepted Answer · 2021-08-19T17:56:17.287

This could be caused for different reasons, like returning without using smart-pointer (which could cause a copy).

But in your particular case, you pass something to F variable's constructor (no matter what), which takes additional memory till constructor returns.

Oh! yet another possible cause, an (un)intelligent vector implementation should reserve more than required (just in case, to speed up later appending).

Example:

Below is what fixed OP's issue:

#include <vector>
#include <iostream>

int main(int argc, char *argv[]){
    getchar();

    std::vector<std::vector<std::vector<std::vector<int64_t>>>> F(
        1, std::vector<std::vector<std::vector<int64_t>>>(15, std::vector<std::vector<int64_t>>(256))
    );
    for (int i = 0; i < 15; i++)
        for (int j = 0; j < 256; j++)
            F[0][i][j] = std::vector<int64_t>(100000, 0);

    getchar();
}

Thanks for your answer. As it turned out, in my case it was indeed the constructor issue, but I agree that the other reasons might also apply in other cases. — Andreas Lenz, Aug 19 '21 at 16:13

score 0 · Answer 2 · answered Aug 19 '21 at 16:11

Additional to the comments of @amon, @NathanOliver and @Top-Master that explain the origin of the problem, I will provide a code example that solves the issue.

#include <vector>
#include <iostream>

int main(int argc, char *argv[]){

    getchar();
    std::vector<std::vector<std::vector<std::vector<int64_t>>>> F(1, std::vector<std::vector<std::vector<int64_t>>>(15, std::vector<std::vector<int64_t>>(256)));
    for (int i=0; i<15; i++) for (int j=0; j<256; j++) F[0][i][j] = std::vector<int64_t>(100000, 0);
    getchar();
}

You could edit my answer and add above code (instead of new answer), but I will do that for you (with little formatting). — Top-Master, Aug 19 '21 at 17:58

Allocating a large multidimensional vector causes memory "overshoot"

2 Answers2

Example: