4

I ran into a funny issue today working with large data structures. I initially was using a vector to store upwards of 1000000 ints but later decided I didn't actually need the dynamic functionality of the vector (I was reserving 1000000 spots as soon as it was declared anyway) and it would be beneficial to, instead, be able to add values any place in the data structure. So I switched it to an array and BAM stack overflow. I'm guessing this is because declaring the size of the array at compile time puts it in the stack and making use of a dynamic vector instead placed it on the heap (which I'm guessing is larger?).

So what's the right answer here? Move back to a dynamic memory system just so it gets put on the heap? Increase the size of the stack? Or am I way off base on the whole thing here...?

Thanks!

Hoyt
  • 317
  • 3
  • 7

1 Answers1

4

I initially was using a vector to store upwards of 1000000 ints

Good idea.

but later decided I didn't actually need the dynamic functionality of the vector (I was reserving 1000000 spots as soon as it was declared anyway)

Not such a good idea. You did need it.

and it would be beneficial to, instead, be able to add values any place in the data structure.

I don't follow.

I'm guessing this is because declaring the size of the array at compile time puts it in the stack and making use of a dynamic vector instead placed it on the heap (which I'm guessing is larger?).

Much. The call stack is typically of the order of 1MB-2MB in size by default. Your "heap" (free store) is only really bounded by your available RAM.

So what's the right answer here? Move back to a dynamic memory system just so it gets put on the heap?

Yes.

[edit: Joachim's right — static is another possible answer.]

Increase the size of the stack?

You could but even if you could stretch 4MB out of it, you've left yourself no wiggle room for other local data variables. Best use dynamic memory — that's the appropriate thing to do.

Or am I way off base on the whole thing here...?

No.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • On Windows I think the default stack size is [1 MB](http://msdn.microsoft.com/en-us/library/windows/desktop/ms686774(v=vs.85).aspx). – ChrisW Nov 20 '12 at 01:25
  • @BenjaminLindley: I did mean 8KB, but I admit that I was mostly making that part up. – Lightness Races in Orbit Nov 20 '12 at 01:26
  • Got it, back to the vector it is. For future reference, is there any way to force a non-dynamic array to be put on the heap instead of the stack? – Hoyt Nov 20 '12 at 01:29
  • @Hoyt: `int* ptr = new int[1000000]; /* f(ptr); */ delete[] ptr;` – Lightness Races in Orbit Nov 20 '12 at 01:29
  • Based on a swift survey of Linux boxen that I have access to, the default seems to be 8MB on Ubuntu and 10MB on CentOS (`uname -s`). Of course, most of that is just virtual address space, and never gets pages allocated to it unless you actually create a million `int` on the stack. – Steve Jessop Nov 20 '12 at 01:30
  • @SteveJessop: I'm used to it being much smaller on the sort-of-embedded platforms I work with, despite their access to like 64MB of RAM. Dynamic memory is the way to go here. – Lightness Races in Orbit Nov 20 '12 at 01:31
  • Yeah, I ended up just declaring it static since I really only needed the one array. Out of curiosity, where does the memory come from for static arrays? – Hoyt Nov 20 '12 at 01:33
  • @Hoyt: You know what I'm not actually sure. A third area, I believe - either part of or near the actual program code, possibly. – Lightness Races in Orbit Nov 20 '12 at 01:34
  • 1
    @Hoyt: in principle it depends on the OS, in practice it's dynamically allocated by the loader. The executable contains metadata how much memory is needed, and when the executable is loaded it's given the right amount. Compilers for properly-embedded systems without an OS might dedicate the whole resources of the device to one program, so can just decide what physical address to put the statics at and configure `malloc` to allocate from elsewhere. – Steve Jessop Nov 20 '12 at 01:35
  • I meant `ulimit -s` above. `uname -s` would be `Linux` ;-) And agreed, even if you expect 8MB stack, using half of that is well within the realms of "risky". You never know when your code will be handed over to Lightness to port to some tiny-little-stack system. – Steve Jessop Nov 20 '12 at 01:42
  • You might want to add that in addition to "static" you could make variable global. This isn't a nice coding style, but (I think) this is an important thing to know. When you make variable global, compiler will no longer allocate it on stack. This might be platform/compiler-specific, though. – SigTerm Nov 20 '12 at 03:39
  • @SigTerm: That's precisely what I was talking about: giving it static storage duration. – Lightness Races in Orbit Nov 20 '12 at 10:11