The bitmapped allocator in a standard form.

[Dhruv Matani <dhruvbird at gmx dot net>]

I've re-organized the files, so that the bitmapped allocator can
function as a separate entity itself. In particular, there are just 2
files. Once you have those, you can use the bitmapped allocator. I have
completely separated it from NSTL. Currently, I have put the allocator
in namespace std::, but I can change that later on. I have tested the
allocator as a complete replacement to the pool allocator for std::list,
and the results show that for every operation, the time taken is lesser
than that for the default allocator. In particular, sorting, and linear
searching after sorting and clearing the container are much faster (a
few hundred order of magnitudes). I'm attaching the 2 files (balloc.hpp
and cheap_alloc.hpp), and the driver (balloc_test.hpp), and the test
resiults for the driver. Please let me know the status, and if there's
anything more I can do.


Test Results for Driver Program:

//Bit mapped Allocator
Time Taken to Insert: 0.14 Seconds.
Time Taken to Search: 0.47 Seconds.
Size is: 650000
Time Taken to Sort: 1.35 Seconds.
Time Taken to Search: 5.83 Seconds.
Size is: 631316

Time Taken to Insert: 0.14 Seconds.
Time Taken to Search: 6.32 Seconds.
Size is: 1281316
Time Taken to Sort: 2.83 Seconds.
Time Taken to Search: 11.46 Seconds.
Size is: 91650

Time Taken to Insert: 0.13 Seconds.
Time Taken to Search: 1.71 Seconds.
Size is: 741650
Time Taken to Sort: 1.57 Seconds.
Time Taken to Search: 6.26 Seconds.
Size is: 165439

3
[dhruv@home test]$ compile balloc_test.cpp -O3
[dhruv@home test]$ ./balloc_test 

//Default Node Allocator.

Time Taken to Insert: 0.15 Seconds.
Time Taken to Search: 0.6 Seconds.
Size is: 650000
Time Taken to Sort: 1.42 Seconds.
Time Taken to Search: 6.07 Seconds.
Size is: 631316

Time Taken to Insert: 0.15 Seconds.
Time Taken to Search: 6.77 Seconds.
Size is: 1281316
Time Taken to Sort: 3.07 Seconds.
Time Taken to Search: 12.85 Seconds.
Size is: 91650


Time Taken to Insert: 0.34 Seconds.
Time Taken to Search: 6.79 Seconds.
Size is: 741650
Time Taken to Sort: 2.98 Seconds.
Time Taken to Search: 7.46 Seconds.
Size is: 165439

3


NOTE: cheap_allocator<> is the same as new_allocator, except that I'm
working with the g++3.2 default STL, so the renaming has not affected
me. That's why I  do not use new_allocator or __new_alloc as the case
may be.

As of g++3.4, I'd like to know whether it compiles this particular piece
of code without errors:


//BEGIN CODE.
#include <vector>

template <typename T>
struct A {
  typedef int Type;
  typedef std::vector <T> Vec_Type;
  typedef typename Vec_Type::difference_type DType;
//g++3.2 Compiles the above line fine even without the typename, which
is probably incorrect.

  struct B {
    Type TVar;
//It seems that g++3.4 does not allow this. I tested the above code on
comeau online, and it works fine.
  };
};


int main ()
{
  A<int> Aobj;
  Aobj = Aobj;
  A<double>::B Bobj;
  Bobj = Bobj;
}
//END CODE.





-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/


/* Copyright (c) 2003
 * Dhruv Matani.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  No representations about the 
 * suitability of this software for any purpose.  It is provided 
 * "as is" without express or implied warranty.
 */


//Bitmapped Allocator.
//====================


// This allocator will make use of 1 single bit to keep track of whther
// it has been allocated or not. A bit 1 indicates free, while 0
// indicates allocated. This has been done so that you can easily check a
// collection of bits for a free block. This kind of Bitmapped strategy
// works best for single object allocations, and with the STL type
// parameterized, we do not need to choose any size for the block which
// will be represented by a single bit. This will be the size of the
// parameter around which the allocator has been parameterized. Thus,
// close to optimal performace will result.

// Another issue would be whether to keep the all bitmaps in a
// separate area in memory, or to keep them near the actual blocks
// that will be given out or allocated for the client. After some
// testing, I've decided to keep these bitmaps close to the actual
// blocks. this will help in 2 ways. 1. Constant time access for the
// bitmap themselves, since no kind of look up will be needed to find
// the correct bitmap list or it's equivalent. 2. And also this would
// preserve the cache as far as possible. So in effect, this kind of
// an allocator might not prove beneficial from a purely cache point
// of view. But this allocator has been made to try and roll out the
// defects of the node_allocator, whrein the nodes get skewed about in
// memory, if they are not returned in the exact reverse order or in
// the same order in which they were allocated. Also, the
// vma_allocator's book keeping overhead is too much for small objects
// and single object allocations, though it preserves the locality of
// blocks very well when they are returned back to the allocator.

// Expected overhead per block would be 1 bit in memory. Also, once
// the address of the free list has been found, the cost for
// allocation/deallocation would be negligible, and is supposed to be
// conatant time. For these very reasons, it is very important to
// minimize the linear time costs, which include finding a free list
// with a free block while allocating, and finding the corresponding
// free list for a block while deallocating. Therefore, I have decided
// that the growth of the internal pool for this allocator will be
// exponential as compared to linear for node_allocator. There, linear
// time works well, because we are mainly concerned with speed of
// allocation/deallocation and memory consumption, whereas here, the
// allocation/deallocation part does have some linear/logarathmic
// complexity components in it. Thus, to try and minimize them would
// be a good thing to do at the cost of a little bit of memory.

// Another thing to be noted is the the pool size will double every
// time the internal pool gets exhausted, and all the free blocks have
// been given away. The initial size of the pool would be
// sizeof(int)*8 which is the nuber of bits in an integer, which can
// fit exactly in a CPU register. Hence, the term given is exponential
// growth of the internal pool.


#if !defined __STL_BITMAP_ALLOCATOR_HPP__
#define __STL_BITMAP_ALLOCATOR_HPP__

#include <cstddef>
//For std::size_t, and ptrdiff_t.
#include <utility>
//For std::pair.
#include <algorithm>
//std::find_if.
#include <vector>
//For the free list of exponentially growing memory blocks. At max,
//size of the vector should be  not more than the number of bits in an
//integer or an unsigned integer.
#include <functional>

#include <new>

#include <cheap_alloc.hpp>
//For std::cheap_allocator for std::vector.

#include <cassert>

namespace std {

namespace _aux_balloc {

  static const unsigned int Bits_Per_Byte = 8;
  static const unsigned int Bits_Per_Block = sizeof(unsigned int) * Bits_Per_Byte;

  //T should be a pointer type.
  template <typename T>
  class inclusive_between {
    typedef T pointer;
    pointer ptr_value;
    typedef typename std::pair<T, T> block_pair;

  public:
    inclusive_between (pointer _ptr) : ptr_value(_ptr) { }
    bool operator () (block_pair _bp)
    {
      if (std::less_equal<pointer> ()(ptr_value, _bp.second) && 
	  std::greater_equal<pointer> ()(ptr_value, _bp.first))
	return true;
      else
	return false;
    }
  };



  //T should be a pointer type, and A is the Allocator for the vector.
  template <typename T, typename A>
  class ffit_finder {
    typedef typename std::vector<std::pair<T, T>, A> BPVector;
    typedef typename BPVector::difference_type counter_type;
    typedef typename std::pair<T, T> block_pair;
    
    unsigned int *pbitmap;
    unsigned int _offset;

  public:
    ffit_finder () : _offset(0) { }

    bool operator() (block_pair _bp)
    {
      //Set the _rover to the last unsigned integer, which is the
      //bitmap to the first free block. Thus, the bitmaps are in exact
      //reverse order of the actual memory layout. So, we count down
      //the bimaps, which is the same as moving up the memory.
      unsigned int *_rover = reinterpret_cast<unsigned int*>(&_bp.first) - 1;
      counter_type _diff = &_bp.second - &_bp.first + 1;
      _diff /= Bits_Per_Block;

      for (counter_type i = 0; i < _diff; ++i, --_rover)
	{
	  _offset = i;
	  if (*_rover)
	    {
	      pbitmap = _rover;
	      return true;
	    }
	}
      return false;
    }

    unsigned int *get () { return pbitmap; }
    unsigned int offset () { return _offset * Bits_Per_Block; }
  };



  //T should be a pointer type.
  template <typename T, typename A>
  class Bit_Map_Counter {

    typedef typename std::vector<std::pair<T, T>, A> BPVector;
    typedef typename BPVector::size_type index_type;
    typedef T pointer;

    BPVector& _vbp;
    unsigned int *_curr_bmap;
    unsigned int *_last_bmap_in_block;
    index_type _curr_index;

  public:
    //Use the 2nd parameter with care. Make sure that such an entry
    //exists in the vector before passing that particular index to
    //this ctor.
    Bit_Map_Counter (BPVector& Rvbp, index_type Index = 0) : _vbp(Rvbp)
    {
      this->reset (Index);
    }

    void reset (index_type Index = 0)
    {
      _curr_index = Index;
      _curr_bmap = reinterpret_cast<unsigned int*>(_vbp[_curr_index].first) - 1;

      assert (Index <= _vbp.size() - 1);

      _last_bmap_in_block = _curr_bmap - 
	((_vbp[_curr_index].second - _vbp[_curr_index].first + 1) / Bits_Per_Block - 1);
    }

    //Dangerous Function! Use with extreme care. Pass to this
    //functions ONLY those values that are known to be correct,
    //otherwise this will mess up big time.
    void Set_Internal_Bit_Map (unsigned int *New_Internal_Marker)
    {
      _curr_bmap = New_Internal_Marker;
    }

    bool finished ()
    {
      return (_curr_bmap == 0);
    }


    Bit_Map_Counter& operator++ ()
    {
      if (_curr_bmap == _last_bmap_in_block)
	{
	  if (++_curr_index == _vbp.size())
	    {
	      _curr_bmap = 0;
	    }
	  else
	    {
	      this->reset (_curr_index);
	    }
	}
      else
	{
	  --_curr_bmap;
	}
      return *this;
    }
    
    unsigned int *get ()
    {
      return _curr_bmap;
    }

    pointer base () { return _vbp[_curr_index].first; }
    unsigned int offset ()
    {
      return Bits_Per_Block * ((reinterpret_cast<unsigned int*>(this->base()) - _curr_bmap) - 1);
    }
    
  };



}



template <class T> class bitmap_allocator;
// specialize for void:
template <> class bitmap_allocator<void> {
public:
  typedef void*       pointer;
  typedef const void* const_pointer;
  //  reference-to-void members are impossible.
  typedef void  value_type;
  template <class U> struct rebind { typedef bitmap_allocator<U> other; };
};

template <class T> class bitmap_allocator {
public:
  typedef size_t    size_type;
  typedef ptrdiff_t difference_type;
  typedef T*        pointer;
  typedef const T*  const_pointer;
  typedef T&        reference;
  typedef const T&  const_reference;
  typedef T         value_type;
  template <class U> struct rebind { typedef bitmap_allocator<U> other; };

private:

  static const unsigned int Bits_Per_Byte = 8;
  static const unsigned int Bits_Per_Block = sizeof(unsigned int) * Bits_Per_Byte;

  //The following function has been written by Apurva
  //Mehta. apurva@gmx.net.
  static inline unsigned int first_right_bit (unsigned int num)
  {
    int tmp = 0;
    __asm__ ("bsf %1, %0"
	     : "=r" (tmp)
	     : "r" (num)
	     : "%eax", "%ebx", "%edx", "%ecx"
	     );
    
    return tmp;
  }
  
  
  static inline void bit_allocate (unsigned int *pbmap, unsigned int Pos)
  {
    unsigned int _mask = 1 << Pos;
    _mask = ~_mask;
    *pbmap &= _mask;
  }
  
  
  static inline void bit_free (unsigned int *pbmap, unsigned int Pos)
  {
    unsigned int _mask = 1 << Pos;
    *pbmap |= _mask;
  }

  void *Memory_Get (size_t _sz) throw (std::bad_alloc)
  {
    return operator new (_sz);
  }

  void Memory_Put (void *_ptr) throw ()
  {
    operator delete (_ptr);
  }


  typedef typename std::pair<pointer, pointer> block_pair;
  typedef typename std::cheap_allocator<block_pair> BPVec_Allocator_Type;
  typedef typename std::vector<block_pair, BPVec_Allocator_Type> BPVector;



  
  void Refill_Pool ()
  {
    const unsigned int Num_Bit_Maps = Block_Size / Bits_Per_Block;

    const unsigned int _size_to_allocate = 
      Block_Size * sizeof(value_type) + Num_Bit_Maps*sizeof(unsigned int);

    unsigned int *temp = 
      reinterpret_cast<unsigned int*>(this->Memory_Get (_size_to_allocate));

    //The Header information goes at the Beginning of the Block.
    block_pair _bp = std::make_pair (reinterpret_cast<pointer>(temp + Num_Bit_Maps), 
				     reinterpret_cast<pointer>(temp + Num_Bit_Maps) + Block_Size - 1);


    //Fill the Vector with this information.
    mem_blocks.push_back (_bp);

    unsigned int Bit_Mask = 0; //0 Indicates all Allocated.
    Bit_Mask = ~Bit_Mask; //1 Indicates all Free.

    for (unsigned int i = 0; i < Num_Bit_Maps; ++i)
      temp[i] = Bit_Mask;

    //On some implementations, operator new might throw bad_alloc, or
    //malloc might fail if the size passed is too large, therefore, we
    //limit the size passed to malloc or operator new.
    if (Block_Size < 102400) Block_Size *= 2;
  }

  void _init_me ()
  {
    if (!mem_blocks.empty ())
      return;

    mem_blocks.reserve (16);
    this->Refill_Pool ();
    static std::_aux_balloc::Bit_Map_Counter<pointer, BPVec_Allocator_Type> _bmc (mem_blocks);
    //    Bit_Map_Counter *_bmc = new Bit_Map_Counter (mem_blocks);
    last_request = &_bmc;
  }

  static BPVector mem_blocks;
  static unsigned int Block_Size;
  static std::_aux_balloc::Bit_Map_Counter<pointer, BPVec_Allocator_Type> *last_request;

public:
  bitmap_allocator()
  {
    this->_init_me ();
  }

  //Copy Ctor means that a class of this type has already been
  //instantiated. Meaning that we need not call _do_init() again.
  bitmap_allocator(const bitmap_allocator&) { }

  template <class U> bitmap_allocator(const bitmap_allocator<U>&) throw()
  {
    this->_init_me ();
  }

  //Dtor not needed.
  //~bitmap_allocator() throw();

  pointer allocate (size_type n)
  {
    if (n != 1)
      return reinterpret_cast<pointer>(this->Memory_Get (n * sizeof(value_type)));

    //The algorithm is something like this: The last_requst variable
    //points to the last accessed Bit Map. When such a condition
    //occurs, we try to find a free block in the current bitmap, or
    //succeeding bitmaps until the last bitmap is reached. If no free
    //block turns up, we resort to First Fit method. But, again, the
    //First Fit is used only upto the point where we started the
    //previous linear search.

    while (last_request->finished () == false && (*(last_request->get()) == 0))
      {
	last_request->operator++ ();
      }

    if (last_request->finished ())
      {
	//Fall Back to First Fit algorithm.
	std::_aux_balloc::ffit_finder<pointer, BPVec_Allocator_Type> _fff;
	typedef typename BPVector::iterator bpiter;
	bpiter _bpi = std::find_if (mem_blocks.begin(), mem_blocks.end(), _fff);


	if (_bpi != mem_blocks.end())
	  {
	    //Search was successful. Ok, now mark the first bit from
	    //the right as 0, meaning Allocated. This bit is obtained
	    //by calling get() on _fff.
	    unsigned int nz_bit = first_right_bit (*_fff.get());
	    bit_allocate (_fff.get(), nz_bit);

	    last_request->reset (_bpi - mem_blocks.begin());
	    //last_request->reset ();

	    //Now, get the address of the bit we marked as allocated.
	    pointer Ret_Val = _bpi->first + _fff.offset() + nz_bit;
	    return Ret_Val;
	  }
	else
	  {
	    //Search was unsuccessful. We Add more memory to the pool
	    //by calling Refill_Pool().
	    this->Refill_Pool ();

	    //Reset the last_request structure to the first free
	    //block's bit map.
	    last_request->reset (mem_blocks.size () - 1);

	    //now, mark that bit as allocated.
	    unsigned int nz_bit = first_right_bit (*last_request->get());
	    bit_allocate (last_request->get(), nz_bit);

	    pointer Ret_Val = last_request->base() + last_request->offset() + nz_bit;
	    return Ret_Val;
	  }
      }
    else
      {
	//last_request holds a pointer to a valid bit map, that points
	//to a free block in memory.
	unsigned int nz_bit = first_right_bit (*last_request->get());
	bit_allocate (last_request->get(), nz_bit);

	pointer Ret_Val = last_request->base() + last_request->offset() + nz_bit;
	return Ret_Val;
      }
  }

  pointer allocate (size_type n, typename bitmap_allocator<void>::const_pointer hint)
  {
    //I will probably implement this beahviour later. For no, just
    //call the previous allocate function.
    return allocate (n);

  }


  void deallocate(pointer p, size_type n)
  {
    if (n != 1)
      return this->Memory_Put (p);

    typedef typename BPVector::iterator iterator;
    typedef typename BPVector::difference_type diff_type;

    iterator iter = std::find_if (mem_blocks.begin(), mem_blocks.end(), 
				  std::_aux_balloc::inclusive_between<pointer> (p));

    assert (iter != mem_blocks.end());

    //Get the position of the iterator that has been found.
    diff_type _diff = iter - mem_blocks.begin();
    int _displacement = p - mem_blocks[_diff].first;
    unsigned int _rotate = _displacement % Bits_Per_Block;
    unsigned int *_bit_mapC = reinterpret_cast<unsigned int*>(mem_blocks[_diff].first) - 1;
    _bit_mapC -= (_displacement / Bits_Per_Block);

    bit_free (_bit_mapC, _rotate);
  }



  pointer address (reference r) const { return &r; }
  const_pointer address (const_reference r) const { return &r; }

  size_type max_size (void) const throw () { return (size_type()-1)/sizeof(value_type); }



  void construct (pointer p, const_reference _data)
  {
    new (p) value_type (_data);
  }

  //Specialize the destroy function to do nothing for built-in types.
  void destroy (pointer p)
  {
    p->~value_type();
  }


};

  template <typename T>
  bitmap_allocator<T>::BPVector bitmap_allocator<T>::mem_blocks;

  template <typename T>
  unsigned int bitmap_allocator<T>::Block_Size = bitmap_allocator<T>::Bits_Per_Block;

  template <typename T>
  std::_aux_balloc::Bit_Map_Counter 
  <bitmap_allocator<T>::pointer, bitmap_allocator<T>::BPVec_Allocator_Type> 
  *bitmap_allocator<T>::last_request;

}




#endif //__NSTL_BITMAP_ALLOCATOR_HPP__


/*
 *
 * Copyright (c) 2003
 * Dhruv Matani.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  No representations are being made 
 * about the suitability of this software for any purpose.  It is 
 * provided "as is" without express or implied warranty.
 */




#if !defined __STL_CHEAP_ALLOC_HPP__
#define __STL_CHEAP_ALLOC_HPP__

#include <new>

namespace std {
template <class T> class cheap_allocator;
// specialize for void:
template <> class cheap_allocator<void> {
public:
  typedef void*       pointer;
  typedef const void* const_pointer;
  //  reference-to-void members are impossible.
  typedef void  value_type;
  template <class U> struct rebind { typedef cheap_allocator<U> other; };
};

template <class T> class cheap_allocator {
public:
  typedef size_t    size_type;
  typedef ptrdiff_t difference_type;
  typedef T*        pointer;
  typedef const T*  const_pointer;
  typedef T&        reference;
  typedef const T&  const_reference;
  typedef T         value_type;
  template <class U> struct rebind { typedef cheap_allocator<U> other; };
  cheap_allocator() throw() { }
  cheap_allocator(size_type, size_type) throw() { }
  cheap_allocator(const cheap_allocator&) throw() { }
  template <class U> cheap_allocator(const cheap_allocator<U>&) throw() { }
  ~cheap_allocator() throw() { }
  pointer address (reference r) const { return &r; }
  const_pointer address (const_reference r) const { return &r; }
  pointer allocate(
		   size_type n, typename cheap_allocator<void>::const_pointer hint = 0)
  {
    return reinterpret_cast<T*>(operator new (n*sizeof(T)));
  }
  void deallocate(pointer p, size_type n)
  {
    operator delete (p);
  }
  size_type max_size() const throw() { return (size_type()-1)/sizeof(T); }
  void construct(pointer p, const T& val)
  {
    new (p) T(val);
  }
  void destroy(pointer p)
  {
    p->~T();
  }
};


}


#endif //__STL_CHEAP_ALLOC_HPP__

#include <nstl/balloc.hpp>
//#include <allocator.hpp>
#include <list>
#include <map>
#include <algorithm>
#include <nstl/timer.hpp>
#include <cstdlib>
#include <iostream>

using namespace std;

using nstd::bitmap_allocator;


int main ()
{
  nstd::timer t;

  //typedef std::list<int, bitmap_allocator<int> > My_List;
  //typedef std::map <int, int, bitmap_allocator<int> > My_List;

  typedef std::list<int> My_List;
  //typedef std::map <int, int> My_List;


  //std::list<int, nstd::node_allocator<int> > il1;
  //  nstd::node_allocator<int> ba;

  My_List il1;

  int ctr = 3;
  while (ctr--)
    {

  t.start ();

  for (int i = 0; i < 650000; ++i)
    //  il1.insert (make_pair (rand()%10001, i));
    il1.push_back (rand()%50001);

  t.stop ();

  cout<<"Time Taken to Insert: "<<t.difference()<<" Seconds."<<endl;

  //Search for random values that may or may not belong to the list.
  t.start ();
  for (int i = 0; i < 50; ++i)
    //il1.find (rand()%20001);
    std::find (il1.begin(), il1.end(), rand()%100001);

  t.stop ();
  cout<<"Time Taken to Search: "<<t.difference()<<" Seconds."<<endl;


  My_List::iterator i = il1.begin();

  int LSize = il1.size ();
  std::advance (i, LSize/2);

  cout<<"Size is: "<<LSize<<endl;

  t.start ();
  il1.sort ();
  t.stop ();

  cout<<"Time Taken to Sort: "<<t.difference()<<" Seconds."<<endl;

  //Search for random values that may or may not belong to the list.
  t.start ();
  for (int i = 0; i < 50; ++i)
    //    il1.find (rand()%20001);
    std::find (il1.begin(), il1.end(), rand()%100001);

  t.stop ();
  cout<<"Time Taken to Search: "<<t.difference()<<" Seconds."<<endl;


  //  il1.clear ();
  il1.erase (il1.begin(), i);

  cout<<"Size is: "<<il1.size ()<<endl<<endl;
    }


  il1.clear ();
  int x;
  cin>>x;


}