7

I need to initialize a very large multidimensional std::array of data:

class Thing;

class World
{
public:
    World() : space{nullptr} {};
    ~World() = default;
private:
    static unsigned int const size = 1000;
    std::array<std::array<std::array<std::unique_ptr<Thing>, size>, size>, size> space;
};

If you try to instantiate this, G++ 4.8.2 chokes: it consumes all the available memory and will not return. That is, the compiler hangs and I never get an executable. Why is this? Note that clang++ has no trouble.

Note: I fully realize that putting this much data on the stack can overflow it. What is the best way to initialize it on the heap? I think making space a reference (to allocated memory) would be the best way, but I can't figure the syntax out.

George Hilliard
  • 15,402
  • 9
  • 58
  • 96
  • Does the *compiler* choke? Or does the compiled program choke at runtime? – Benjamin Lindley Mar 25 '14 at 03:35
  • 1
    If this is instantiated as simply `World world;` you're consuming slightly more than `1000^3 * sizeof(std::unique_ptr<>)` bytes. on a 64 bit system that would be a *minimum* 7.629 **GB**. So yeah, I'd say you crossed a line on the automatic variable space limit. I am *dying* to know the problem this is intended to solve. – WhozCraig Mar 25 '14 at 03:36
  • The compiler, g++ 4.8.2, will not return. – George Hilliard Mar 25 '14 at 03:36
  • @WhozCraig, this is a contrived example; I'm not instantiating anything this massive, but it illustrates my point. – George Hilliard Mar 25 '14 at 03:37
  • Ah. ok. so your *compiler* chokes (code fails to compile??), not the actual program ? What is the resultant error message? **Is `World` global or have static linkage?** ? if so you may have just hit the link-limit. – WhozCraig Mar 25 '14 at 03:38
  • Yes. There's not an error, I simply cannot get an executable before the machine runs out of RAM. No idea why this would consume so much memory at compile time. Reducing the size of the `array` to, say, 200x200x3 allows it to finish with a peak RAM usage of about 2GB. `World world` has static linkage (it's instantiated in `main`). – George Hilliard Mar 25 '14 at 03:38
  • 1
    I just tried compiling this (Changing Thing to int) and it compiled. Can you give a small example that demonstrates the compiler failing? – FDinoff Mar 25 '14 at 03:42
  • @FDinoff Now put `World world;` as a *global* and compile again. I'm genuinely curious. – WhozCraig Mar 25 '14 at 03:43
  • yeah mine did too, but I'm using clang, not g++. I need to go hit this on ideone and see if I can make it puke. Edit: after creating a global *and* ensuring it is referenced functionally so as not to optimize out (I was release-building) I managed to eat 4GB of ram on the loader, but at least it loaded. Still haven't tried g++. – WhozCraig Mar 25 '14 at 03:47
  • @WhozCraig same I was using clang++. I just switched to g++ and its still running... – FDinoff Mar 25 '14 at 03:49
  • @FDinoff be ready with Ctrl-C! Can confirm that clang++ has no trouble. No difference with global vs static. – George Hilliard Mar 25 '14 at 03:51
  • 3
    @WhozCraig not running locally hopefully no body at my school is using the machine for anything. Just got this g++: internal compiler error: Killed (program cc1plus) Please submit a full bug report, with preprocessed source if appropriate. See for instructions. Used all 24GB of ram on the computer – FDinoff Mar 25 '14 at 03:53
  • @FDinoff *awesome*. There are times I like gnu; this isn't one of them. Does that happen even without the global or static linkage var? I'm now seriously interested in this. (I'm on a Mac with 5.02 Xcode tools, so no g++ joy here, turns-out-thankfully). I want to say g++ is generating the loadable object code and is stretched to its limit, whereas clang is doing *something* smarter. – WhozCraig Mar 25 '14 at 03:54
  • 1
    @thirtythreeforty I can't explain why this pukes on g++ other than my suspicions about it building the object module with all those DDs embedded. I did post an alternative that *might* work for you in the interim. Hope it helps. – WhozCraig Mar 25 '14 at 04:03
  • 1
    @WhozCraig yeah it looks likes its failing while trying to just compile the class. I used the flags `g++ -std=c++11 -c` (I think this makes it only compile) and I removed the globals. – FDinoff Mar 25 '14 at 04:09
  • @FDinoff Thats exactly what that should do, I see nothing wrong with that at all (you did it right). That you went the extra mile to compile just the module to object code (`-c`) so no link-step and it *still* pukes is somewhat telling. – WhozCraig Mar 25 '14 at 04:12
  • @WhozCraig the worst part is if it did eventually compile the object file would only be 1.3K. I tried it with size at 50, 100 and 200. (I think I saw top max at 50% men usage (of 24GB) for the `size = 200`) – FDinoff Mar 25 '14 at 04:14
  • 1
    @FDinoff Yeah, I think if he vector's the outer-most part of this it may work for him in the interim, but I feel a little iffy on that only because it somewhat kicks the can down the road. The same problem would likely resurface with large enough numbers. – WhozCraig Mar 25 '14 at 04:18
  • 3
    This looks like [GCC Bug #59659](http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59659): the compiler generates *enormous* initializer code for large `std::array` by initializing each element directly. – Casey Mar 25 '14 at 07:30
  • @Casey: This is what I suspected, I remember killing Clang when trying to introduce a massive C-array of user-defined classes. With `int` there is no initialization so everything is fine but `unique_ptr` has a user-defined constructor. – Matthieu M. Mar 25 '14 at 07:53

3 Answers3

2

Ok, i can't explain the nuance of why g++ is puking on this, but until you work that out, consider this for your member declaration:

std::vector<std::array<std::array<std::unique_ptr<Thing>,size>,size>> space;

and in the constructor initializer list:

World() : space{size}

That should at least get you compiling and move all this to the heap. Note: this better be a 64bit process. I'm going to have to hunt to find out why g++ is doing what I suspect it is doing.

WhozCraig
  • 65,258
  • 11
  • 75
  • 141
  • 1
    This compiled with `size = 4000000000` in less than a second. – FDinoff Mar 25 '14 at 04:23
  • I feel like there is a way to do this with space as a `unique_ptr` to the 3D `array` construct and initializing it with the proper call to `new` (and modifying all the usage appropriately to dereference) but I can't work that constructor syntax out either just yet. Regardless, this works. – George Hilliard Mar 25 '14 at 04:23
  • @thirtythreeforty so long as you have something to work with. You certainly could do this with a std::unique_ptr<> at the outer reaches and allocate yourself, but if you need that at runtime, you can do the same just by reserving and emplacing as needed through World members and hit up the vector. At least this gets you on the heap and out of automatic storage. I'll try and do some bugs hunting and see if there is something on this already reported when I get the spare cycles. Glad you have something interim to work with. Wish you could prop FDinoff for this as well. He put some work in it. – WhozCraig Mar 25 '14 at 04:28
  • @thirtythreeforty or WhozCraig do either of you have an account at the gnu bug tracker and would be willing to submit the bug report there? Or should I just do it? – FDinoff Mar 25 '14 at 04:32
  • I may have an account but if you would rather handle it that would be fine with me. – George Hilliard Mar 25 '14 at 06:13
  • @thirtythreeforty I actually don't, so one of you will have to do it. sry for that inconvenience. But hey, *you* found it =P – WhozCraig Mar 25 '14 at 06:23
  • Alright. I'll do it when "I get some spare cycles" (I like that and I'm taking it ;). Thank you both for the help. And if you figure out the reason why and are bored one day, I would love to hear the reason. – George Hilliard Mar 25 '14 at 06:25
2

As you are using unique_ptr it looks like you are looking for a sparse 3d-matrix like type. For implementing a sparse matrix you could have a look at What is the best way to create a sparse array in C++? and as an implementation detail you could use Boost Multi-index for implementing fast access to all dimensions.

Community
  • 1
  • 1
Jan Herrmann
  • 2,717
  • 17
  • 21
0
vector<vector<vector<unique_ptr<Thing>>>> space;

and when initializing it:

for (int i = 0; i < 1000; i++)
{
   vector<vector<unique_ptr<Thing>>> sp1;
   for (int j = 0; j < 1000; j++)
   {
      vector<unique_ptr<Thing>> sp2;
      for (int k = 0; k < 1000; k++)
         sp2.push_back(make_unique<Thing>("params", "to", "construct", "thing"));

       sp1.push_back(move(sp2));
   }

   space.push_back(move(sp1));
}

It is similar to your approach, but it constructs the vectors in the heap instead of stack.

ebasconp
  • 1,608
  • 2
  • 17
  • 27