Sign in to follow this  
Telcontar

Dynamic memory and very large c++ vectors

Recommended Posts

Telcontar    1554
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
Antheus    2409
[quote name='Telcontar' timestamp='1311113119' post='4837653']

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[/quote]

What does actual declaration look like?

Share this post


Link to post
Share on other sites
the_edd    2109
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
Telcontar    1554
[quote name='edd²' timestamp='1311118389' post='4837694']
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.
[/quote]

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
the_edd    2109
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
taz0010    277
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
Hinch    244
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: [url="http://stackoverflow.com/questions/1984186/what-is-private-bytes-virtual-bytes-working-set"]http://stackoverflow...tes-working-set[/url] .

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 [i]at least[/i] 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
taz0010    277
[quote name='Hinch' timestamp='1311257824' post='4838455']
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: [url="http://stackoverflow.com/questions/1984186/what-is-private-bytes-virtual-bytes-working-set"]http://stackoverflow...tes-working-set[/url] .

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 [i]at least[/i] enough for that amount of data, i.e. it could still be more (though usually it's not).
[/quote]

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
Telcontar    1554
[quote name='Hinch' timestamp='1311257824' post='4838455']
It's possible to pre-size them by calling vector::reserve
[/quote]

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
Trienco    2555
[quote name='Telcontar' timestamp='1311298162' post='4838733']
[quote name='Hinch' timestamp='1311257824' post='4838455']
It's possible to pre-size them by calling vector::reserve
[/quote]

I'm using vector::resize. This should have basically the same effect as vector::reserve, shouldn't it?[/quote]

No, one resizes the vector (adding elements and if storing classes calling tons of default constructors) and the other just allocates the memory for later use.

Share this post


Link to post
Share on other sites
Telcontar    1554
Yes indeed, but the world I'm building is generated at the players command, and all at once. So I wouldn't gain anything by reserving space I'm going to use in the next few lines of code. Would I?

Share this post


Link to post
Share on other sites
ApochPiQ    23000
It makes a difference. If Trienco's explanation isn't clear enough, you can try this:

[code]struct Foo
{
Foo()
{
std::cout << "Constructed foo\n";
}
};

int main()
{
std::cout << "Initial construction\n";
std::vector<Foo> myfoos;
std::cout << "Reserve\n";
myfoos.reserve(10000);
std::cout << "Resize\n";
myfoos.resize(10000);
}[/code]

Share this post


Link to post
Share on other sites
Slavik81    360
[quote name='ApochPiQ' timestamp='1311363984' post='4839095']
It makes a difference. If Trienco's explanation isn't clear enough, you can try this:

<snip>[/quote]
I think what Telcontar means is that

[code]
std::vector<Foo> myfoos;
myfoos.reserve(10000);
myfoos.resize(10000);
[/code]

is no different than

[code]
std::vector<Foo> myfoos;
myfoos.resize(10000);
[/code]

in any meaningful way.

Share this post


Link to post
Share on other sites
ApochPiQ    23000
In the [i]highly specific[/i] case of a reserve followed by an immediate resize, then yes, it's wasteful and you may as well just resize.

But if you don't want default-constructed objects, don't resize - reserve instead. If you don't want every push_back to potentially incur a copy-and-expand allocation, use reserve first, etc. I'm just saying that it's dangerous to generalize from "in this one case a reserve is pointless" to "it never makes sense to reserve."

Share this post


Link to post
Share on other sites
taz0010    277
Calling push_back inside a loop is generally the slower way of populating a vector, as the function must check that there's enough room, increment counters, etc. Even when you reserve so there's no reallocation, the logic that handles the reallocation case still sits of the control path of push_back, making the function fairly large and not a candidate for inlining.

If you are able to copy all the elements to the vector using it's iterator constructor (takes a begin() and end() iterator), you should do so. The magic of templates allows you to use this constructor to copy elements from a primitive array, which is very convenient and fast.

Otherwise, if the vector type has a trivial default constructor and no destructor, it is efficient to construct the vector with the number of elements you need, then use a loop to copy the actual elements across.

If your classes are complex (allocate memory), then make sure they have move constructors and move assignment operators, which will greatly improve their performance when vectors are concerned.

Share this post


Link to post
Share on other sites
Telcontar    1554
[quote name='taz0010' timestamp='1311395306' post='4839208']
Calling push_back inside a loop is generally the slower way of populating a vector, as the function must check that there's enough room, increment counters, etc. Even when you reserve so there's no reallocation, the logic that handles the reallocation case still sits of the control path of push_back, making the function fairly large and not a candidate for inlining.

If you are able to copy all the elements to the vector using it's iterator constructor (takes a begin() and end() iterator), you should do so. The magic of templates allows you to use this constructor to copy elements from a primitive array, which is very convenient and fast.

Otherwise, if the vector type has a trivial default constructor and no destructor, it is efficient to construct the vector with the number of elements you need, then use a loop to copy the actual elements across.

If your classes are complex (allocate memory), then make sure they have move constructors and move assignment operators, which will greatly improve their performance when vectors are concerned.


[/quote]

And whole new worlds open up. I'd never even known about [i]move[/i] constructors and assignment. Seperate reference types for Rvalue and Lvalue... aie. So much reading to do now.

Share this post


Link to post
Share on other sites
NickGomes    142
Do you need to create and store the entire world in memory all at once?? Perhaps you can offload chunks of the world that you don't need off memory and onto disk storage. Then you could stream in chunks as needed. (This could be a more complicated solution but for truly massive worlds you will need data streaming.) I really doubt that you want to take up all that memory just to represent the entire world and then be shot for resources when you need say audio or texture data.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this