0

I'm making a picture editing program, and I'm stuck in allocating memory. I have no idea what is going on.

Ok.. So when I do this:

std::vector<unsigned char> h;
for (int a = 0; a < 10000 * 10000 * 3; a++) {
    h.push_back(0);
}

this is fine(sorry I had to), but when I do this:

std::vector<std::vector<std::vector<unsigned char>>> h;
for (uint32_t a = 0; a < 10000; a++) {
  h.push_back({});
  for (uint32_t b = 0; b < 10000; b++) {
    h.at(a).push_back({});
    for (uint32_t c = 0; c < 3; c++) {
      h.at(a).at(b).push_back(0xff);
    }
  }
}

my memory usage explodes, and I get error: Microsoft C++ exception: std::bad_alloc at memory location 0x009CF51C

I'm working with .bmp.

Currently, code is in testing mode so it's basically a giant mess... I'm 15, so don't expect much of me.

I was searching for solutions, but all I found was like how to handle large integers and so on...

If you can give me maybe another solution, but I want my code to be as beginner friendly as it can get.

Zoran
  • 37
  • 2
  • 5
    I suspect your image size is 10000 x 10000 and you want to store the pixel RGB values? There are libraries (e.g. opencv) you can use to do that efficiently. Using nested vectors simply isn't suitable for that. – πάντα ῥεῖ Jan 10 '19 at 22:00
  • You may want to build a 64 bit application. With 300MB images its easy to fill the available address space (which probably is less than 2GB with around 1.2GB contiguous). Using a 64 bit application would eliminate these 2 problems. – drescherjm Jan 10 '19 at 22:06
  • 1
    The problem might be that "Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth." [ref](https://en.cppreference.com/w/cpp/container/vector). So in your 2nd case the actual size might be much larger than the already large 10000*10000*3=300MB vector in the 1st case. I suggest going with the 1st case and a function to convert x,y positions to vector index: `index = (y * width) + x`. – simon Jan 10 '19 at 22:08

3 Answers3

7

This is due to overhead of vector<char>. Each such object with 3 elements takes not 3 bytes, but probably 4 (due to reallocation policy), plus 3 pointers which probably take 3*8=24 bytes. Overall your structure takes 9.3 times the memory it could have.

If you replace the inner vector with an array, it will start working, since array does not have this overhead:

std::vector<std::vector<std::array<unsigned char, 3>>> h;
for (uint32_t a = 0; a < 10000; a++) {
  h.emplace_back();
  for (uint32_t b = 0; b < 10000; b++) {
    h.at(a).emplace_back();
    for (auto &c : h.at(a).at(b)) {
      c = 0xff;
    }
  }
}

Another alternative is to put the smaller dimension first.

Michael Veksler
  • 8,217
  • 1
  • 20
  • 33
  • This could easily be bigger than the available address space in a 32 bit application. – drescherjm Jan 10 '19 at 22:15
  • @drescherjm 32 bit application on Windows in 2019? – SergeyA Jan 10 '19 at 22:16
  • It's probably still the default depending on the ide. Edit: `0x009CF51C` is 32 bits. – drescherjm Jan 10 '19 at 22:16
  • This is the first time I see something like ` for (auto &c : h.at(a).at(b)) { c = 0xff; }` and It says for `auto &c : H.at(a...` it doesn't have suitable begin function... wut? – Zoran Jan 10 '19 at 22:26
  • `for (auto &c : h.at(a).at(b)) {` is a range based for loop. It was added in the 2011 standard c++11: https://en.cppreference.com/w/cpp/language/range-for – drescherjm Jan 10 '19 at 22:27
  • What do i have to do to fix it? My head just spins when I try to read what says here: https://en.cppreference.com/w/cpp/language/range-for – Zoran Jan 10 '19 at 22:46
  • @Zoran there are many different levels of documentation. cppreference strives for maximum accuracy and sometimes this results in description that look as through they were written by Martians. [This is less precise](https://learn.microsoft.com/en-us/cpp/cpp/range-based-for-statement-cpp?view=vs-2017), but should be easier to swallow. If it leaves you with questions, go back to the first site and see if the easier entry makes it more readable. – user4581301 Jan 10 '19 at 22:55
  • @user4581301 thanks, It would be more helpful IF I DID THIS `#include ` – Zoran Jan 10 '19 at 23:34
1

My guess would be that the memory is being heavily fragmented by the constant vector reallocation, resulting in madness. For data this large, I would suggest simply storing a 1-dimensional pre-allocated vector:

std::vector h(10000 * 10000 * 3);

And then come up with an array accessing scheme that takes the X/Y arguments and turns them into an index in your 1d array, eg.:

int get_index(int x, int y, int width) {
    return ((y * width) + x) * 3;
}

If the image size is always fixed, you can also use std::array (see multi-dimensional arrays), since the size is defined at compile-time and it won't suffer the same memory issues as the dynamically allocated vectors.

Colin Basnett
  • 4,052
  • 2
  • 30
  • 49
-3

I don't know if this will help your problem, but you could try allocating the memory for the vec of vecs of vecs all at the beginning, with the constructor.

std::vector<std::vector<std::vector<unsigned char>>> h(10000, std::vector<std::vector<unsigned char>>(10000, std::vector<unsigned char>(3,0xff)));

BTW, you're getting a good start writing C++ at 15! I didn't start studying computer science till I was in my 20s. It really is a very marketable career path, and there are a lot of intellectually stimulating, challenging things to learn. Best of luck!

mannyglover
  • 2,139
  • 14
  • 18
  • 1
    Preallocation won't help much in such case. – πάντα ῥεῖ Jan 10 '19 at 22:02
  • @πάνταῥεῖ, why did his first example work and not his second? But yeah, you're probably right that pre-allocation won't help here. A vector of vectors of something will be just as contiguous as a vector of somethings, yes? – mannyglover Jan 10 '19 at 22:04
  • 2
    @mannyglover Unfortunately no. Each `vector` contains a pointer to its dynamically allocated data store, so the outer `vector` contains a pointer to N contiguous `vector`s, but each of those inner `vector`s has a pointer some other block of memory which may or may not be located near the other blocks owned by the other inner `vectors`. – user4581301 Jan 10 '19 at 22:07
  • 3
    You should note that most CPUs allocate memory blocks pagewise (e.g. at a minimum size of 1K). If you have three dimensions there would be a large overhead regarding these pages allocated. – πάντα ῥεῖ Jan 10 '19 at 22:08