Re: Performance of the default Node Allocator.

[Dhruv Matani <dhruvbird at gmx dot net>]

On Wed, 2004-01-14 at 14:04, Stefan Olsson wrote:
> Hi Dhruv,
> 
> very interesting! Am I missing something, I tried to compile your
> testcase (in order to make a comp test with mt alloc of course ;) but
> with little luck:
> 
> void:~/nstl$ /home/admin/gcc/bin/g++ balloc_test.cpp -I ./ -O3
> In file included from ./nstl/algorithm.hpp:29,
>                  from nstl/balloc.hpp:35,
>                  from balloc_test.cpp:1:
> ./nstl/detail/nstl_algorithm.hpp: In member function `c
> nstd::_quick_sort<t>::_aux_unstable_partition(c, c)':
> ./nstl/detail/nstl_algorithm.hpp:227: error: expected `;' before "__pivot"
> ./nstl/detail/nstl_algorithm.hpp:231: error: `__pivot' undeclared (first
> use this function)
> ./nstl/detail/nstl_algorithm.hpp:231: error: (Each undeclared identifier
> is reported only once for each function it appears in.)
> 
> The line in question is:
> std::iterator_traits<c>::value_type __pivot = (*__first+*__last)/2;

The thing is that I've unknowingly used used some reserved names. The
possible causes for this would be:

1. Use of reserved names.
2. Assuming that *__first and *__last can be added, and then assuming
that the result can be divided by 2. Lots of stupid assumptions for
testing!

However, I have not used the code under question anywhere, so I guess
g++ should not even instantiate it. So, g++ trying to instantiate it for
types that don't suppport addition and division is out of the question.

I'm attaching a newer version of the file, so replace it and try again.

The g++ I'm using is:

[dhruv@home test]$ g++ -v
Reading specs from /usr/lib/gcc-lib/i386-redhat-linux/3.2.2/specs
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man
--infodir=/usr/share/info --enable-shared --enable-threads=posix
--disable-checking --with-system-zlib --enable-__cxa_atexit
--host=i386-redhat-linux
Thread model: posix
gcc version 3.2.2 20030222 (Red Hat Linux 3.2.2-5)




> The above was tried on:
> void:~/nstl$ /home/admin/gcc/bin/g++ -v
> Reading specs from /home/admin/gcc/lib/gcc/i686-pc-linux-gnu/3.4.0/specs
> Configured with: ../gcc-3.4-20040107/configure --prefix=/home/admin/gcc
> --enable-threads --enable-languages=c,c++
> Thread model: posix
> gcc version 3.4.0 20040107 (experimental)
> 
> Brgds
> 
> /Stefan
> 
> Dhruv Matani wrote:
> 
> >I was talking about the performance of the default node allocator in
> >situations where the list is sorted, and the nodes get splayed about in
> >memory, and then subsequent allocations/deallocations suffer due to bad
> >cache performance. I have here a bitmapped allocator that attempts to
> >remove those defects. I'm attaching a driver program that shows the
> >performance of the default node allocator v/s the bitmapped allocator.
> >You can see clearly that the bitmapped allocator not only allocates
> >memory faster, but also does not mess up the cache. If anyone wants the
> >source, I can send it by email. You can see that the sort is twice as
> >fast in the bitmapped allocator compared to the default node allocator
> >when used repeatedly. Also, could anyone test out these things for me on
> >other platforms?
> >
> >Link to get the bitmapped allocator:
> >http://www.geocities.com/dhruvbird/nstl/nstl0.2.zip
> >
> >
> >  
> >
> >------------------------------------------------------------------------
> >
> >#include <nstl/balloc.hpp>
> >#include <nstl/node_alloc.hpp>
> >#include <list>
> >#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;
> >
> >  //bitmap_allocator<int> ba;
> >
> >
> >  //  typedef std::list<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 < 550000; ++i)
> >    il1.push_back (rand()%10001);
> >    //    ba.allocate (1);
> >  t.stop ();
> >
> >  cout<<"Time Taken to Insert: "<<t.difference()<<" Seconds."<<endl;
> >
> >  My_List::iterator i = il1.begin();
> >
> >  cout<<"Size is: "<<il1.size ()<<endl;
> >
> >  t.start ();
> >  il1.sort ();
> >  t.stop ();
> >
> >  cout<<"Time Taken to Sort: "<<t.difference()<<" Seconds."<<endl;
> >
> >  //  il1.clear ();
> >  il1.erase (i, il1.end());
> >
> >  cout<<"Size is: "<<il1.size ()<<endl<<endl;
> >    }
> >
> >
> >  il1.clear ();
> >  int x;
> >  cin>>x;
> >
> >
> >}
> >
> >
> >
> >  
> >
> 
-- 
	-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 made about the 
 * suitability of this software for any purpose. It is provided 
 * "as is" without express or implied warranty.
 */

// Author: Dhruv Matani.
// Date: May 08, 2003.
// email: dhruvbird@yahoo.com


#if !defined __NSTL_ALGORITHM_HPP__
#define __NSTL_ALGORITHM_HPP__


namespace nstd {

template <class t>
inline t absolute (const t& a)
{
  return a < 0 ? -a : a;
}
template <class t>
inline bool equal_to_ (const t& arg1, const t& arg2)
{ return std::equal_to<t>() (arg1, arg2); }
template <class t>
inline bool greater_equal_ (const t& arg1, const t& arg2)
{ return std::greater_equal<t> () (arg1, arg2); }
template <class t>
inline bool less_ (const t& arg1, const t& arg2)
{ return std::less<t>() (arg1, arg2); }
template <class t>
inline bool greater_ (const t& arg1, const t& arg2)
{ return std::greater<t>() (arg1, arg2); }
template <class t>
inline bool less_equal_ (const t& arg1, const t& arg2)
{ return std::less_equal<t>() (arg1, arg2); }
template <class t>
inline bool not_equal_to_ (const t& arg1, const t& arg2)
{ return std::not_equal_to<t> () (arg1, arg2); }


template <class OutputIterator, class Size, class T>
OutputIterator __copy_n_ (OutputIterator first, Size n, const T& value)
{
  while (n)
    {
      *first = value;
      ++first; --n;
    }
  return first;
}
template <class OutputIterator, class Size, class T>
OutputIterator __copy_n_backward_ (OutputIterator last, Size n, const T& value)
{
  while (n)
    {
      --last; 
      *last = value;
      --n;
    }
  return last;
}

template <class InputIterator, class OutputIterator, class Size>
OutputIterator __copy_n_range_ (InputIterator src, OutputIterator dest, Size n)
{
  while (n)
    {
      *dest = *src;
      ++dest; ++src; --n;
    }
  return dest;
}
template <class InputIterator, class OutputIterator, class Size>
OutputIterator __copy_n_backward_range_ (InputIterator src, OutputIterator last, Size n)
{
  while (n)
    {
      --last; --src;       
      *last = *src;
      --n;
    }
  return last;
}





//Arguments.
//==========
//
// __first: Iterator to First element.  __last: Iterator to One past
// the Last element.  _condition: The condition for checking. It needs
// to have a !_condition defined. The condition will be used to
// compare elements. So, it needs to be of the kind (greater than: >,
// or less that: <).
//
//
//Returns.
//========
//
// 2 parts of the data set in the order: [first, bound), [bound,
// last). Here, last is not a valid element. It is only a valid
// iterator. However, if the data set contains 0 elements,
// i.e. __first == __last, then _last is returned.


template <class t, class c>
t unstable_partition(t __first, t __last, c _condition)
{
  //Do nothing if the data set contains only 1 or 0 elements.

  t __bottom = __last;

  if (__first != __bottom) --__bottom;

  if (__first != __bottom)
    {
      --__last;
      t __top = __first;
      ++__top;
      
      while (true)
	{
	  while (__top != __bottom && _condition (*__top, *__first)) ++__top;
	  while (__bottom != __top && !_condition(*__bottom, *__first)) --__bottom;
	  
	  //       while (*__top <= val && __top != __bottom) ++__top;
	  
	  //       while (*__bottom > val && __bottom != __top) --__bottom;
	  
	  if (__top != __bottom) swap(*__top, *__bottom);
	  else
	    {
	      if (__bottom == __last)
		if (!(!_condition (*__bottom, *__first) || 
		      equal_to_ (*__bottom, *__first)))
		  swap (*__bottom, *__first);
		  
	      return (__bottom);
  	    }
	}
    }
  else
    return (__last);
  
}




template <class t>
class _quick_sort {
private:
  t _condition;

// template <class c>
// c _aux_unstable_partition(c __first, c __last)
// {
//   //Do nothing if the data set contains only 1 or 0 elements.
  
//   c __bottom = __last;

//   if (__first != __bottom) --__bottom;
  
//   if (__first != __bottom)
//     {
//       --__last;
//       c __top = __first;
//       ++__top;
      
//       while (true)
// 	{
// 	  while (__top != __bottom && (__condition (*__top, *__first) 
// 				       || equal_to_(*__top, *__first))) ++__top;
// 	  while (__bottom != __top && !__condition(*__bottom, *__first)) --__bottom;
	  
// 	  if (__top != __bottom) std::swap(*__top, *__bottom);
// 	  else
// 	    {
// 	      if (__bottom == __last)

// 		//if (!(!__condition (*__bottom, *__first) || equal_to_ (*__bottom, *__first)))
// 		if (__condition (*__bottom, *__first))

// 		  std::swap (*__bottom, *__first);
		  
// 	      return (__bottom);
//   	    }
// 	}
//     }
//   else
//     return (__last);
  
// }







template <class c>
c _aux_unstable_partition(c _first, c _last)
{
  //Do nothing if the data set contains only 1 or 0 elements.
  
  c _bottom = _last;

  if (_first != _bottom) --_bottom;
  
  if (_first != _bottom)
    {
      --_last;
      c _top = _first;
      //      ++_top;
      std::iterator_traits<c>::value_type _pivot = *_first;
      //      std::iterator_traits<c>::value_type _pivot = (*_first+*_last)/2;
      
      while (true)
	{
	  while (_top != _bottom && (_condition (*_top, _pivot) 
				       || equal_to_(*_top, _pivot))) ++_top;
	  while (_bottom != _top && !_condition(*_bottom, _pivot)) --_bottom;
	  
	  if (_top != _bottom) std::swap(*_top, *_bottom);
	  else
	    {
	      //	      if (_bottom == _last)

	      //if (!(!_condition (*_bottom, *_first) || equal_to_ (*_bottom, *_first)))
// 		if (_condition (*_bottom, *_first))

// 		  std::swap (*_bottom, *_first);
	      //if (_condition (*_bottom, *_top)) std::swap (*_top, *_bottom);
		  
	      return (_bottom);
  	    }
	}
    }
  else
    return (_last);
  
}




  template <class c>
  void _aux_quick_sort(c _first, c _last)
  {
    c _bound = _aux_unstable_partition (_first, _last);

    if (_bound != _last)
      {
        _aux_quick_sort (_first, _bound);
	_aux_quick_sort (_bound, _last);
      }

  }



public:
template <class InputIterator, class Condition>
_quick_sort (InputIterator _first, InputIterator _last, Condition _c): _condition (_c)
{
  _aux_quick_sort (_first, _last);
}



};



//Takes a range of Iterators of the form: [first, last).
template <class t, class c>
void quick_sort (t _first, t _last, c _condition)
{
  _quick_sort<c> (_first, _last, _condition);
}


}


//NOT WORKING AS YET> NEED PPL> TO DEBUG IT.
//
// template <class t, class c>
// void quick_sort_iterative (t __first, t __last, const c __condition)
// {
//   queue<t> q;

//   //queue<t::value_type>::iterator qi;

//   t start1 = __first;
//   t finish1 = unstable_partition (__first, __last, _condition);

//   if (finish1 != __last) ++finish1;

//   t start2 = finish1;
//   t finish2 = __last;

//   if (start2 != finish2)
//     {

//       q.push (start2);
//       q.push (finish2);
//     }


//   //  qi = q.begin ();

//   while (start1 != finish1)
//     {
//       t temp = unstable_partition (__first, finish1, _condition);
      
//       if (temp != finish1)
// 	{
// 	  finish1 = temp;

// 	  if (temp != ++finish1)
// 	    {
// 	      q.push (temp);
// 	      q.push (finish1);
// 	    }
// 	}

//       start1 = temp;
//     }

//   while (!q.empty ())
//     {
//       start2 = q.front ();
//       q.pop ();
//       finish2 = q.front ();
//       q.pop ();

//       quick_sort_iterative (start2, finish2, _condition);
//     }

// }


#endif //__NSTL_ALGORITHM_HPP__