Jump to content
  • Advertisement
Sign in to follow this  
Telcontar

Dynamic memory and very large c++ vectors

This topic is 2550 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello.

So I've run into one of my biggest knowledge gaps - memory management. I'm hoping someone will have articles or something for me to read, as my own web searches haven't turned up anything useful yet.

I'm trying to create a large 'world' for my game. This world is fashioned from blocks that represent 1 meter cubes.

Currently I'm using vectors of pointers. to create a 3d representation. However, I can't seem to allocate a very large world this way - in fact, I can't seem to allocate much at all. When I try to create a 300x300x300 vector I'm getting exceptions thrown (std::bad_alloc), so something is wrong with using that much space, so now its time to learn more. I don't understand exactly WHAT I need to learn to make this work, though. Any help is appreciated.

My own quick guess is that using Vectors for this is just too inefficient, and that I should switch to arrays and handle the memory management myself. I wasn't sure how much that would save me, though.

(If it helps, I'm trying for something akin to Dwarf Fortress - which generates a massive world before play)

Share this post


Link to post
Share on other sites
Advertisement


Currently I'm using vectors of pointers. to create a 3d representation. However, I can't seem to allocate a very large world this way - in fact, I can't seem to allocate much at all. When I try to create a 300x300x300 vector


What does actual declaration look like?

Share this post


Link to post
Share on other sites
300*300*300 allocates (27 million * object-size) bytes. Windows (XP at least) has a 2Gb limit per process unless you take special system-wide measures. If your objects are 100 bytes or so in size, you're going to hit that limit.

If that's not the problem, you'll have to do as Antheus suggests and show us what you're doing in more detail.

Share this post


Link to post
Share on other sites

300*300*300 allocates (27 million * object-size) bytes. Windows (XP at least) has a 2Gb limit per process unless you take special system-wide measures. If your objects are 100 bytes or so in size, you're going to hit that limit.

If that's not the problem, you'll have to do as Antheus suggests and show us what you're doing in more detail.


Nowhere near that large, fortunately. However, after some number crunching, I see that there is no way I'll be able to generate the whole world at the level of detail I want at the outset.

Also, I'm silly for not realizing I can handle this with a bit of abstraction - that is, generate the world at a much lower resolution, and then focus in when the player comes into any particular zone. Ah, beginner mistakes.

Thank you both for your help.

Share this post


Link to post
Share on other sites
Ok, but it should be noted that your guess about vectors being inefficient is most likely incorrect. Typically there's all of 12 bytes overhead (per vector, not per element) on a 32 bit system.

Share this post


Link to post
Share on other sites
That is very good to know, thank you. I wasn't sure, because I'd heard a great deal about how wonderful the usual STL containers are supposed to be.

Share this post


Link to post
Share on other sites
Dynamically allocated structures have both internal and external memory overhead. This is a pretty important thing to know when you're worrying about whether your program can fit in RAM...

Create a list<int> (where int = 32 bits) with 1,000,000 elements and run it in debug mode in VS2010. Check the task manager and you'll see the program consumes a whopping 70MB of RAM. So where is all that memory going?

Debug mode:


sizeof(list<int>) = 16 bytes. This includes the integer itself so there's 12 bytes of internal overhead
70MB according to task manager
70 - 16 = 54 bytes due to allocation overhead


Release mode, inside IDE:

sizeof(list<int>) = 12 bytes. The structure is 4 bytes larger in debug mode. The only internal overhead in release mode are the prev and next pointers
40MB according to task manager
40 - 12 = 28 bytes due to allocation overhead. Because we're running in the IDE, some level of memory debugging is present, even under release mode settings

Release mode, outside IDE

sizeof(list<int>) = 12 bytes
24MB according to task manager
24 - 12 = 12 bytes due to allocation overhead.


So for every allocation you're looking at 12 bytes of overhead. But the number is significantly higher while debugging (54 or 28).




sizeof(vector<int>) = 16, so in the case of a 300 x 300 x 300 grid, you have:

Innermost vector of 300 ints. 16 bytes internal overhead, 8 bytes external, 1200 bytes of actual data (4 bytes/element) = 1224 bytes
Middle vector of 300 vectors. 16 bytes internal overhead, 8 bytes external, 300 * 1224 bytes from inner vector = 367224 bytes
Outer vector of 300 inner vectors, 16 bytes internal overhead, 8 bytes external, 300 * 367224 = 110,167,224 bytes


Share this post


Link to post
Share on other sites
Just FYI, task manager is a terrible way to check how much memory your process is using as the stats displayed by default aren't very useful and it has mixed up terminology. Get process explorer and have a look at the "Private bytes" value if you want to know how much you have requested from the OS. Here's a brief explanation of some of the different stats you will be able to see: http://stackoverflow...tes-working-set .

Also taz, some of that memory used by the vectors might not necessarily be "overhead" (by which I presume you mean 'wasted' memory used for book-keeping rather than storing your own data), they can allocate more memory than you actually request so that they don't need to reallocate and move large chunks of memory around every time you want to expand the vector. It's possible to pre-size them by calling vector::reserve, but if you read the docs you will notice that will try to allocate at least enough for that amount of data, i.e. it could still be more (though usually it's not).

Share this post


Link to post
Share on other sites

Just FYI, task manager is a terrible way to check how much memory your process is using as the stats displayed by default aren't very useful and it has mixed up terminology. Get process explorer and have a look at the "Private bytes" value if you want to know how much you have requested from the OS. Here's a brief explanation of some of the different stats you will be able to see: http://stackoverflow...tes-working-set .

Also taz, some of that memory used by the vectors might not necessarily be "overhead" (by which I presume you mean 'wasted' memory used for book-keeping rather than storing your own data), they can allocate more memory than you actually request so that they don't need to reallocate and move large chunks of memory around every time you want to expand the vector. It's possible to pre-size them by calling vector::reserve, but if you read the docs you will notice that will try to allocate at least enough for that amount of data, i.e. it could still be more (though usually it's not).


The page size under Windows is 4KB IIRC, and the figure I calculated for the 300 x 300 x 300 vector was within 2KB of the memory use displayed by task manager. I'm pretty confident that the magic number is 8 bytes. That's the bookkeeping cost of the default allocator.
In previous versions of VS they allocated memory to vectors in their default constructor, but they have stopped doing that in VS2010. (Thank god, it was a terrible idea) This might have inflated the numbers due to fragmemtation if I ran the test on VS2008 instead. Under VS2010 vectors are only "padded out" when you trigger a reallocation using push_back or insert. And the vector capacity is visible in the IDE now - a very nice feature.

Share this post


Link to post
Share on other sites

It's possible to pre-size them by calling vector::reserve


I'm using vector::resize. This should have basically the same effect as vector::reserve, shouldn't it? These are some of the first structures to be created in the game and their size will never change.

Or should I be using reserve, and then resize?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!