Static Memory Pool Viability

  • (2 Pages)
  • +
  • 1
  • 2

19 Replies - 1353 Views - Last Post: 10 July 2013 - 08:38 AM Rate Topic: -----

#16 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3576
  • View blog
  • Posts: 11,125
  • Joined: 05-May 12

Re: Static Memory Pool Viability

Posted 03 July 2013 - 07:58 PM

This is an almost non sequitur, but as I mentioned before, I can't get to my books right now and I sort of remember something from Scott Meyer's Effective C++ series of books about interesting memory optimizations you could do with the placement new operator. It revolved around fixed sized objects and overriding the new operator so that you could allocate memory once and reuse it later without returning the block to the OS. If you have access to those books, it maybe worth taking a look.
Was This Post Helpful? 1
  • +
  • -

#17 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: Static Memory Pool Viability

Posted 03 July 2013 - 08:06 PM

View PostSkydiver, on 03 July 2013 - 07:58 PM, said:

This is an almost non sequitur, but as I mentioned before, I can't get to my books right now and I sort of remember something from Scott Meyer's Effective C++ series of books about interesting memory optimizations you could do with the placement new operator. It revolved around fixed sized objects and overriding the new operator so that you could allocate memory once and reuse it later without returning the block to the OS. If you have access to those books, it maybe worth taking a look.


Definitely will do. Any chance to read more from S. Meyer is worth it regardless.
I'll also try to find a copy or excerpt of the game programming gems book. I have one
book laying around, game coding complete, which discusses it, but the implementation
is a for variable size blocks.

EDIT: ---------------------------------------
I don't want to pull up an old thread, but I did want to share with you all the result that I ended up
coming up with:

What I ended up doing was using a deque of unique
pointers, such that when an alloc() is called, I use std::move to pass the owner ship of
the memory piece to the user, and the unique_ptr is removed from the deque. On a free
call, the unique_ptr transfers ownership to a new unique_ptr to be emplaced into the
structure. So, I believe there is a slightly higher cost on allocs() and deallocs() compared
to my old version, but I also think this one is a lot cleaner to use.

#ifndef MEMORY_H
#define MEMORY_H

#include <deque>
#include <memory>
using namespace std;

/*
* A class which allocates a static memory pool
* for a particular object type. Useful for items
* such as ships which will be continually alloc'd
* and dealloc'd throughout a level.
*/
template <typename T>
class StaticObjectPool
{
    public:
        StaticObjectPool(size_t numBlocks)
        {
            m_numBlocksFree = numBlocks;
        
            for(size_t iter = 0; iter < numBlocks; iter++)
            {
                m_memoryMap.push_back( unique_ptr<T> (new T()) );	
            }
        }
        
        ~StaticObjectPool()
        {
            m_memoryMap.clear();
        }
        
        bool alloc(unique_ptr<T>& memPtr)
        {
            if(m_numBlocksFree > 0)
            {
                m_numBlocksFree--;
                for(auto itr = m_memoryMap.begin(); itr != m_memoryMap.end(); itr++)
                {
                    if(*itr)
                    {	
                        memPtr = std::move(*itr);
                        m_memoryMap.erase(itr);
                        return true;
                    }
                } 
            }   	
        
            return false;
        }
        
        void free(unique_ptr<T>& memPtr)
        {
            m_numBlocksFree++;
            m_memoryMap.emplace_back(unique_ptr<T> (std::move(memPtr)));
            memPtr = nullptr;
        }
        
        bool blocksAvailable()
        {
            return m_numBlocksFree > 0;
        }

        //disable costly operations(copy, assignment)
        StaticObjectPool& operator=(const StaticObjectPool&) = delete;
        StaticObjectPool(const StaticObjectPool&) = delete;

    private:
        deque<unique_ptr<T>> m_memoryMap;
        size_t m_numBlocksFree;
};
#endif //MEMORY_H



Assuming my unit tests go well, it should be good for now.

Again, thank you to everyone for their wisdom and guidance.
raspy.

This post has been edited by raspinudo: 08 July 2013 - 03:25 AM

Was This Post Helpful? 0
  • +
  • -

#18 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Static Memory Pool Viability

Posted 09 July 2013 - 09:06 PM

First off, the way you are using unique_ptr is really odd. They should be by value objects only and they are strictly non copyable, only movable(this of course can be subverted however) you shouldn't pass them by reference, only return them.

I haven't looked too closely but you might look at standard allocators and std::allocate_unique/std::allocate_shared. These allow for smart pointers that use custom allocates. You might look at Andre Alexdrescu's fast memory allocator which uses free lists and the minimal number of constructor calls. You can actually combine the two to get fast, low latency, garbage collected pointers. It's quite a neat trick.

the quick way to get started with this is to use Boost.Pool and existing smart pointers with std::make_unique and std::make_shared. the interleaved free list idea has become an idiom of C++ and is one of my favorite techniques.

boost::fast_pool_allocator<T> alloc;
//...
tempalte<class... Args>
std::shared_ptr<T> create(Args&&... args) {
  return std::allocate_shared(alloc, std::forward<Args>(args)...);
}



this code allows a shared pointer to be created with *minimal* overhead of allocation and constructor calls. This will allocate raw memory which will then be constructed (internally using in place new) using the perfectly forwarded arguments. That pointer will then be given to the shared pointer. Note internally type erasure is being used to provide this and still have std::shared_ptr<T>. This function will actually produce a MORE EFFICIENT representation than just constructing a shared_ptr via an allocation from new. Here is the explanation

allocate_shared can construct an object with all the information it needs at once so internally a type like the following gets constructed

template<class T, class Alloc>
class allocate_shared_impl : public shared_ptr_impl {
  int count;
  T obj;
  Alloc& alloc;
  tempalte<typename... Args>
  allocate_shared_impl(Alloc& a, Args... args) : alloc(a), obj(std::forward<Args>(args)...) {}
  virtual ~allocate_shared_impl() { //note the destructor is virtual
    //does the reference count stuff in destructor
  }
  virtual void inc() { //called by shared_ptr when pointer is copied, this is a overridden virtual method
    count++;
  }
  virtual T& get() {
    return obj;
  }
}; 



this is all allocated in one big chunk and the locality is amazing (note: depending on access patters of the implementation 'obj' may come first to improve locality)

if you use the standard shared_ptr constructor it has to construct something like this

template<class T, class Alloc>
class plain_shared_impl : public shared_ptr_impl {
  int count;
  T* obj;
  tempalte<typename... Args>
  plain_shared_impl (T* p) : obj(p)) {}
  virtual ~plain_shared_impl () { //note the destructor is virtual
    //does the reference count stuff in destructor
  }
  virtual void inc() { //called by shared_ptr when pointer is copied, this is a overridden virtual method
    count++;
  }
  virtual T& get() {
    return *obj;
  }
}; 



this looses the locality of having the reference count and object in the same block AND requires an extra layer of indirection to access the pointer.

so, I think the best solution for you is allocate_shared or allocate_unique with boost pool's fast_pool_allocator. It's going to be VERY hard to improve on the performance of this setup. The only way to do better would be to have a custom smart pointer class that didn't need the type erasure but every allocator would have a different smart pointer type and you wouldn't be able to use new at all; that would be a real pain just to gain some inlining. The code would have to VERY performance critical to warrant such an action. The other solution is to just have 1 allocator type for your special smart point. This purely sacrifices flexibility for performance and should be a last resort for only the most critical code. At either of these points you should consider if smart pointers are actually the right fit.

hope this helps and gives you a deeper understanding of the already tools in palace for memory management!

edit: also as for fragmentation. The free list solves fragmentation for the most part but not locality of reference, a related issue. I have seen a couple of ideas on how to fix this but only really like one of them: a compacting alocator

You can implement a pointer type that uses double indirection so that the allocator can periodically compact the used memory and the fake pointer will just reference the new location after the compaction because the allocator updated the actual pointers location to all the fake pointers. This is the cleanest I can think of and sorta seems like what you talked about already. Just perhaps a bit more refined.

I *think* you can still use this in a smart pointer by setting the 'pointer' type of your allocator class to use your pointer type instead of T*; this may not be guaranteed by the standard to work, I am not sure.

This post has been edited by ishkabible: 09 July 2013 - 09:43 PM

Was This Post Helpful? 2
  • +
  • -

#19 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: Static Memory Pool Viability

Posted 09 July 2013 - 10:06 PM

Could you explain why my usage of unique pointer is poor? I just thought of it like this: user passes in a new unique pointer which points to nothing is then given the ownership of the raw memory. I probably did this because I don't have a full understanding of adequate move sematics. It just seemed the simplest thing conceptually at the time.
The basic usage broke down as:

    StaticObjectPool<int> s(2);
    unique_ptr<int> a;
    if(s.alloc(a))
        cout << "alloc success" << endl;



I had considered using make_unique, but I couldn't remember if it had made it into the standard, I knew make shared did. I am going to read Andre's paper on his fast pool allocator right now. I did a simple benchmark which only allocs(), and the performance seems to be good so far, but I am always up for improving it. By my guess, my game should only warrant a max of 5k object per level, so it may not make too much of a difference.

I have various other questions, but I would like to do my research into perfect forwarding, rvalues and the boost library as to not waste anyone's time unnecessarily.
Was This Post Helpful? 0
  • +
  • -

#20 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Static Memory Pool Viability

Posted 10 July 2013 - 08:38 AM

I think you are right about make_unique, it does not seem to have maid it into the standard. There seems to be speculation that it will make it into C++14 (if C++14 makes it that is). It would require some kind of polymorphism that may intern require an extra allocation. This may be seen as paying for something you don't use which is against the key philosophy behind C++. As it is right now unique pointers are just safe raw pointers. If it doesn't require an extra allocation then it would only require storing an extra reference in the unique pointer which would be pretty cheap.

As for your use of unique pointer, why not just return a unique pointer? It is much more efficient and idiomatic. Also, as much as possible pointers should not be null. I'm not saying to needlessly allocate something, that is just as bad. Just don't construct a unique pointer if it isn't being used if you can. Your way is not wrong it just isn't what I would call idiomatic. You can throw an exception or something if it can't allocate. Handling these errors with if statements is a bad idea if you ask me.

This post has been edited by ishkabible: 10 July 2013 - 08:45 AM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2