Jump to content
  • Advertisement
Sign in to follow this  
Gumgo

Memory allocation in practice

This topic is 1969 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

So from everything I've read, game engines are one type of software where having fine control over how memory is allocated is often very important. I often read that during gameplay you ideally don't want to actually allocate any memory - it should all be preallocated when the level loads. This seems like a good idea, but in practice there are many cases where it seems very difficult to judge what the allocation limits should be. I've got some specific examples in mind which I'll list below. Could someone give examples on how these decisions might be made in practice?

 

(One thing to keep in mind is that in the particular project I'm working on, the levels are procedurally generated.)

 

- Enemy limits. Normally the player might be fighting maybe 5-6 enemies at once. But what if the player runs around the level and gathers a huge crowd? Would you allocate for worst possible case?

 

- Similarly, with items. Five players fire bow and arrow as rapidly as possible, and there are a ton of arrow items stuck in walls. Should I calculate "max fire rate" and determine the maximum possible amount of arrows that could be fired and stuck in the wall before they despawned? It seems like it might be really hard to determine these limits on certain gameplay elements. And networked objects just complicate things further, since their ordering isn't guaranteed.

 

- Network buffers. Messages that are guaranteed are queued up until the ACK has been received. But if there's a network blip, the queue might briefly have to get big.

 

- Objects that have variable sizes. For example, suppose one enemy has a skeletal mesh with 3 bones, and another has 20 bones. Each requires a "state" buffer. But if I allocate space for at most, say, 100 "enemies", I'd have to assume worst case (they all have 20 bones) if I didn't do some sort of on-demand allocation.

 

- Strings. Perhaps they should be avoided altogether. Right now for example, I have a file which describes the "sword" item, and an enemy might spawn "sword" when killed. Should these all be preprocessed into indices?

 

- Components in an entity component system. If it's possible to dynamically add components (e.g. an enemy is OnFire, Frozen, and Poisoned), should you assume the worst and allocate in case all enemies obtain the largest possible combination of dynamic components?

 

It seems like a lot of these "worst cases" could potentially be pretty hard to spot. Especially if there's any sort of user-provided scripting system. What is usually done to deal with these types of issues?

Share this post


Link to post
Share on other sites
Advertisement

I don't generally worry too much about it. The main thing is to make sure you're not doing a LOT of heap allocations at runtime, so reuse buffers/vectors, or use a pre-allocated memory pool and use your own allocator. The more allocations you do, the more memory fragmentation there will be, and thus can run into problems on embedded systems/consoles where virtual memory is not available.

 

You're not going to have many problems if you do a few dynamic allocations, the main issue is if you are doing many hundreds or thousands of allocations every frame.

 

One particular pattern that I've found helpful in reducing dynamic allocations is this:

template < typename T, size_t localCapacity >
class ShortList
{
	public:
		
		ShortList()
			:	storage( (T*)localStorage ),
				size( 0 ),
				capacity( localCapacity )
		{
		}
		
		~ShortList()
		{
			if ( storage != (T*)localStorage )
				free( storage );
		}
		
		void add( const T& newElement )
		{
			if ( size == capacity )
				reallocate( capacity*2 );
			
			new (storage + size) T( newElement );
			size++;
		}
		
		
	private:
		
		void reallocate( size_t newCapacity )
		{
			// replace current storage with dynamically allocated storage.
		}
		
		T* storage;
		size_t size;
		size_t capacity;
		
		UByte localStorage[localCapacity*sizeof(T)];
		
};

 

Basically you have a local storage buffer for a small fixed number of elements which can grow to be any size if necessary. This way, you get the best of both worlds: a statically allocated array, plus the ability to store any number of elements.

Share this post


Link to post
Share on other sites
There are two relevant problems here that one could run into:

1. Too many allocations happening per second: In this case you would probably first discover this was a problem through profiling, and you would target the low-hanging fruit, changing only those things to use a memory pool or fixed-size buffer.

2. Memory fragmentation: Harder to detect and harder to deal with, but the solution is more of the same.

And of course, avoid unnecessary allocation. E.g. don't do dynamic memory allocation for things that are small and only exist for the lifetime of a function call. That's what the stack is for.

Share this post


Link to post
Share on other sites

Thanks for the replies. My target platforms are PC/Mac and iPad. I'm certainly glad to hear that these allocation issues are less of an issue on platforms with virtual memory. From what I've read, it seems like the iPad virtual memory setup is fairly similar to that of a PC, with the exception of swapping memory to disk (which shouldn't happen in a game anyway). Can anyone comment on this?

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!