Dealing with variable size objects in an array
Author
I'm currently developing a message system for the network component of my game. As part of this, I'm trying to make an 'inbox' for each message recipient that new messages get placed into pending processing. All messages derive from a common Message base containing sender, recipient, a timestamp etc and have virtual Serialise and Deserialise functions.
The problem I'm having is how to store the messages in the inbox using a templated queue.
As far as I can tell there are two options:
1) Messages are created on the heap, new'd for sending, pointer to it is stored in the queue, then deleted after processing. The problem with this comes to where new/delete can be expensive and messages could not easily be sent to multiple recipients due to multiple deletions (which I guess could be sorted with ref-counting).
2) Messages are created on the stack then copied into the queue using placement new. The problem with this is that messages are of differing sizes, and I can't think of a safe way to put them in a templated queue that can accept them without having to do some funky type-casting.
Has anyone encountered this problem before or got any suggestions to solve it?
Cheers,
Ed
I'd use solution 1. The cost of frequent memory allocation/de-allocation can be easily reduced by using more efficient allocators than the global new/delete if that's really necessary.
1 is the best way, using a pool allocator assuming your objects are fairly small it should perform fine. You *could* make a list of objects which are all the size of the largest object, and cast them in for 2), but it's a waste of memory if the smallest and biggest objects have a big size difference. If it's a small difference, it's also perfectly viable.
Quote:Original post by Degra
All messages derive from a common Message base containing sender, recipient, a timestamp etc and have virtual Serialise and Deserialise functions.
The problem I'm having is how to store the messages in the inbox using a templated queue.
As far as I can tell there are two options:
1) Messages are created on the heap, new'd for sending, pointer to it is stored in the queue, then deleted after processing. The problem with this comes to where new/delete can be expensive and messages could not easily be sent to multiple recipients due to multiple deletions (which I guess could be sorted with ref-counting).
In a statically typed language that lets you allocate things on the stack, you basically always know the type of anything that's created on the stack, because you have to specify a type in order to do the instantiation. (Unless you're doing some magic with alloca() or equivalent, anyway.) Thus, adding virtual functions to a class, which suggests that you usually won't know the exact type, pretty much admits right there that the class will normally be instantiated on the heap.
This is not really a problem. Consider that if your "stack" or "queue" are not of a fixed size, they will have to be allocated on the heap anyway. If you're worried about frequent small allocations, consider using a pool allocator. If you're worried about multiple deletions (which you should be), look into smart pointers. the_edd's value_ptr is especially appropriate for this sort of situation, where you want to store instances polymorphically, and be able to copy the instances, but don't intend to "share" them between containers. Alternatively, you might look into Boost's ptr_containers. I would guess that boost::ptr_list is optimized to avoid excess indirection (by allocating varying amounts of memory for each list node depending on the derived type), but I don't know for sure.
Author
Quote:Original post by Zahlman
In a statically typed language that lets you allocate things on the stack, you basically always know the type of anything that's created on the stack, because you have to specify a type in order to do the instantiation. (Unless you're doing some magic with alloca() or equivalent, anyway.) Thus, adding virtual functions to a class, which suggests that you usually won't know the exact type, pretty much admits right there that the class will normally be instantiated on the heap.
This is not really a problem. Consider that if your "stack" or "queue" are not of a fixed size, they will have to be allocated on the heap anyway. If you're worried about frequent small allocations, consider using a pool allocator. If you're worried about multiple deletions (which you should be), look into smart pointers. the_edd's value_ptr is especially appropriate for this sort of situation, where you want to store instances polymorphically, and be able to copy the instances, but don't intend to "share" them between containers. Alternatively, you might look into Boost's ptr_containers. I would guess that boost::ptr_list is optimized to avoid excess indirection (by allocating varying amounts of memory for each list node depending on the derived type), but I don't know for sure.
Thankyou for your replies.
The reason I did not know the type statically know the type of the object is because its being created via a class factory. A variable size data structure is not a viable option because it can create an unpredictable memory footprint as well as fragmenting address space causing long term instability, it would be better to effectively manage the data going into the queue rather than just making it bigger as needed.
I have decided to go with option 2 - creating the queue on top of a fixed-size memory pool, using placement new to create objects within it via the class factory pattern.
Thanks all,
Ed
!
In this case, the object is already on the heap, and the factory returns some kind of handle to it (for any sane sort of factory design, anyway). So all you need to do is put the handle in the list, and arrange for destruction to happen later. Using some kind of smart pointer for the handle type generally makes this trivial.
I suspect that (a) your fears of instability are not well founded and (b) any possible process of fragmentation is already well under way.
And you know for certain the maximum possible queue length? Because there is something about your design that mandates a specific maximum value?
Quote:Original post by Degra
The reason I did not know the type statically know the type of the object is because its being created via a class factory.
In this case, the object is already on the heap, and the factory returns some kind of handle to it (for any sane sort of factory design, anyway). So all you need to do is put the handle in the list, and arrange for destruction to happen later. Using some kind of smart pointer for the handle type generally makes this trivial.
Quote:A variable size data structure is not a viable option because it can create an unpredictable memory footprint as well as fragmenting address space causing long term instability,
I suspect that (a) your fears of instability are not well founded and (b) any possible process of fragmentation is already well under way.
Quote:it would be better to effectively manage the data going into the queue rather than just making it bigger as needed.
I have decided to go with option 2 - creating the queue on top of a fixed-size memory pool, using placement new to create objects within it via the class factory pattern.
And you know for certain the maximum possible queue length? Because there is something about your design that mandates a specific maximum value?
Author
Quote:Original post by ZahlmanQuote:Original post by Degra
The reason I did not know the type statically know the type of the object is because its being created via a class factory.
In this case, the object is already on the heap, and the factory returns some kind of handle to it (for any sane sort of factory design, anyway). So all you need to do is put the handle in the list, and arrange for destruction to happen later. Using some kind of smart pointer for the handle type generally makes this trivial.
My class factory supports both heap and placement new allocation.
Quote:Quote:A variable size data structure is not a viable option because it can create an unpredictable memory footprint as well as fragmenting address space causing long term instability,
I suspect that (a) your fears of instability are not well founded and (b) any possible process of fragmentation is already well under way.
Fragmentation is non-existant and a non-problem in my engine & game as there are no game-time (after loading) allocations...
Quote:Quote:it would be better to effectively manage the data going into the queue rather than just making it bigger as needed.
I have decided to go with option 2 - creating the queue on top of a fixed-size memory pool, using placement new to create objects within it via the class factory pattern.
And you know for certain the maximum possible queue length? Because there is something about your design that mandates a specific maximum value?
On a restricted resource platform such as the console I'm using the game can't afford to have memory chewed into randomly. If the game is to work 100% of the time, no matter how long it is played for or under what conditions, everything has to be predictable, including memory usage.
It is much better imho to create the queue with a sensible length and tweak it later on if asserts tell you its too small, or reduce it if it becomes obviously way too big rather than have it silently increase its size.
Ed
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
