A Custom Block Allocator for Speeding Up VC++ STL

1. Alignment issues. An allocator reserving memory on a per-object basis can incur a constant alignment overhead (e.g. reserving always 32 bytes when requested 31). IMHO, in release mode this will only happen in very bad designed allocators; I don't think malloc based allocation suffers from this defect.
   
2. Memory fragmentation. This can actually be an issue. Reserving memory in larger chunks prevents the formation of many unusable little blocks that can fragment memory to the point that the practical limit of total memory seen by the program is much less than theoretically possible. Here, block allocators have a reputation for doing a good job. Furthermore, block allocation improves locality and hence, due to cache considerations, speed.

#define DEFINE_BLOCK_ALLOCATED_SET
#include <blockallocator.h>

int main()
{
  block_allocated_set<int,1000> s;
  s.insert(5);

  return 0;
}

output.reserve(min(input1.capacity(),input2.capacity()))

#define DEFINE_BLOCK_ALLOCATED_MAP
#include "blockallocator.h"

#include <crtdbg.h>

using namespace std;

typedef block_allocated_map<int,int,1024> bmap;

//static bmap last_to_abandon; /* comment out/in to fix/show the problem */

int main(void)
{
  _CrtSetDbgFlag(_CRTDBG_DELAY_FREE_MEM_DF|_CrtSetDbgFlag(_CRTDBG_REPORT_FLAG));

  bmap *m1=new bmap;
  bmap *m2=new bmap;

  delete m1;
  delete m2;

  _CrtCheckMemory();
  
  return 0;
}

<br />
#define DEFINE_BLOCK_ALLOCATED_LIST<br />
#include "blockallocator.h"<br />
<br />
#include <iostream><br />
#include <windows.h><br />
<br />
using namespace std;<br />
<br />
template <class T1,class T2,class X1,class X2><br />
DWORD test(T1& l1,T2& l2,X1& x1,X2& x2)<br />
{<br />
  srand(0);<br />
  DWORD dw=GetTickCount();<br />
<br />
  for(int n=0;n<500;++n){<br />
    for(int m=0;m<1000;++m){<br />
      if(rand()<RAND_MAX/2)l1.push_front(x1);<br />
      if(rand()<RAND_MAX/2)l2.push_front(x2);<br />
    }<br />
    for(T1::iterator it1=l1.begin();it1!=l1.end(); ){<br />
      if(rand()<RAND_MAX/2)it1=l1.erase(it1);<br />
      else it1++;<br />
    }<br />
    for(T2::iterator it2=l2.begin();it2!=l2.end(); ){<br />
      if(rand()<RAND_MAX/2)it2=l2.erase(it2);<br />
      else it2++;<br />
    }<br />
    for(m=0;m<500;++m){<br />
      if(rand()<RAND_MAX/2)l2.push_back(x2);<br />
      if(rand()<RAND_MAX/2)l1.push_back(x1);<br />
    }<br />
  }<br />
<br />
  l1.clear();<br />
  l2.clear();<br />
<br />
  return GetTickCount()-dw;<br />
}<br />
<br />
struct node<br />
{<br />
  DWORD x,y,z;<br />
<br />
  bool operator <(const node &) const;<br />
  bool operator >(const node &) const;<br />
  bool operator ==(const node &) const;<br />
  bool operator !=(const node &) const;<br />
};<br />
<br />
int main(void)<br />
{<br />
  DWORD total_default=0;<br />
  DWORD total_block_allocator=0;<br />
  for(int i=1;i<10;++i){<br />
    {<br />
      cout<<"default allocator: ";<br />
<br />
      list<int> l1;<br />
      list<node> l2;<br />
      int x1=0;<br />
      node x2;<br />
      DWORD dw=test(l1,l2,x1,x2);<br />
      cout<<dw<<endl;<br />
<br />
      total_default+=dw;<br />
    }<br />
    {<br />
      cout<<"block allocator: ";<br />
      block_allocated_list<int,1024> l1;<br />
      block_allocated_list<node,1024> l2;<br />
      int x1=0;<br />
      node x2;<br />
      DWORD dw=test(l1,l2,x1,x2);<br />
      cout<<dw<<endl;<br />
      total_block_allocator+=dw;<br />
    }<br />
  }<br />
  cout<<"----------------------------------------"<<endl;<br />
  cout<<"Total time default allocator: "<<total_default<<endl;<br />
  cout<<"Total time block allocator: "<<total_block_allocator<<endl;<br />
  cout<<"Block allocator improvement: "<<<br />
    (DWORD)(100.0*(total_default-total_block_allocator)/total_default)<<"%"<<endl;<br />
<br />
  return 0;<br />
}<br />