July 28, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

Small Memory Allocation

  • February 19, 2004
  • By Radu Braniste
  • Send Email »
  • More Articles »

Code Examples

Following are some examples of allocators dealing with different facets of memory fragmentation.

First of all, we have to mention that the BREW API offers a memory pool that can be used as an allocator—IRscPool [4]. But from a memory fragmentation perspective, IRscPool is not usable because the pool is shared with the main heap.

What's next is a simple example of a temporary heap—used mainly for allocating temporary objects. The idea is to allocate temporary objects from a predefined pool, making allocation as fast as stack allocations and creating premises for less fragmentation. Allocated objects are destroyed in a block, simply by moving the "stack" pointer in the initial position. Deallocating is more problematic for objects keeping external resources, taking into account that they were allocated by placement new and the destructor has to be called explicitly. We will see some possible answers to this problem later.

template <size_t POOL_SIZE>
class DiscardableHeap
{
public:
  void* allocate(size_t sz)
  {
    if (allocated_ + sz >= POOL_SIZE)
      return 0;
    void * p = &pool_[0] + allocated_;
    allocated_ += sz;
    return p;
  }
  void deallocate()
  {
    allocated_ = 0;
  }
  ~DiscardableHeap() 
  { }
  DiscardableHeap() :allocated_(0)
  {
    pool_.ensureCapacity(POOL_SIZE);
  }
private:
  BrewVector<char>  pool_;
  size_t allocated_;
private:
  DiscardableHeap( const DiscardableHeap &value );
  const DiscardableHeap &operator = ( const DiscardableHeap &rhs );
};

used for an example, as in:

AA *a = new (th_) AA;
int j = a->guess();
a->~AA();
short * kk = new(rr_) short;
th_->deallocate();
kk = new(rr_) short[10];

An interesting allocator breed is the following:

template <size_t CHUNKS, size_t CHUNK_SZ = 8, size_t
          POOL_SIZE = CHUNKS*CHUNK_SZ>
class BrewAllocator;

BrewAllocator is more like a heap managing its internal memory pool and allowing reallocations. The pool is made of contiguous chunks of memory, facilitating management and alignment—please remember that a heap has to always return aligned memory. You can look at BrewAllocator as a generalization of the POOLED ALLOCATION concept. It can be used equally for small objects allocations as well as for general allocation purposes. Using BrewAllocator might incur internal fragmentation as in any POOLED ALLOCATOR but this can be easily minimized (via CHUNK_SZ).

template <size_t CHUNKS, size_t CHUNK_SZ = 8, size_t
          POOL_SIZE = CHUNKS*CHUNK_SZ>
class BrewAllocator
{
public:
  bool isInPool(void* p)
  {
    return ((p >= pool_) && ( p < pool_+POOL_SIZE));
  }
  void* allocate(size_t sz)
  {
    return findBestFit(sz);
  }
  void deallocate(void* p)
  {
    restorePool(p);
  }
  ~BrewAllocator() 
  {
    unregisterResources();
  }
  BrewAllocator() : pool_(new char[POOL_SIZE])
  {
    resources_.ensureCapacity(CHUNKS);
    for(UINT i = 0 ; i < CHUNKS; ++i)
    {
      resources_.append(0);
    }
  }
private:
  void unregisterResources()
  {
    delete[] pool_;
  }
  void* findBestFit( size_t sz)
  {
    if (!sz) 
      return 0;
    void* fit  = 0;
    size_t dif = sz/CHUNK_SZ;
    if ( (dif==0) || ((sz%CHUNK_SZ) > 0) )
      dif++;
    if (dif > CHUNKS)
      return 0;
    UINT i = 0;
    while( i < resources_.size() )
    {
      if (resources_[i] == 0)
      {
        int idx  = i;
        for(UINT k = 1 ; k <= dif; ++k)
        {
          if (resources_[i] == 0)
          {
            if (k == dif)
            {
              fit = pool_ + CHUNK_SZ * idx;
            }
            else
            {
              ++i;
            }
          }
          else
          {
            fit = 0;
            break;
          }
        }
        if (fit)
        {
          resources_[idx] = dif;
          for(UINT j = 1 ; j < dif; ++j)
          {
            resources_[idx+j] = 1;
          }
          break;
        }
      }
      else
      {
        ++i;
      }
    }
    return fit;
  }
  void restorePool(void* p)
  {
    int i = ((char*)p - pool_) / CHUNK_SZ;
    int dif = resources_[i] ;
    for(int k = 0 ; k < dif; ++k)
    {
      resources_[i+k] = 0;
    }
  }
private:
  char*  pool_;
  BrewVector<int> resources_;
private:
  BrewAllocator( const BrewAllocator &value );
  const BrewAllocator &operator = ( const BrewAllocator &rhs );
};

resources_ keeps track of allocated chunks (both qualitative and quantitative). There is a findBestFit strategy (far from perfect) that allocates the memory.

Using BrewAllocator is straightforward. Having defined:

typedef BrewAllocator<128> Allocator;
rr_ = new Allocator; 
void* operator new(size_t nbytes, Allocator* pool)
  {
    if (pool)
    return pool->allocate(nbytes);
    return 0;
  }

one can write:

  int* j = new (rr_) int();
//rr->deallocate(j); if not deallocated is automatically
//                   deallocated when the pool exits




Page 2 of 3



Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Sitemap | Contact Us

Rocket Fuel