Performance of the default Node Allocator.

[Dhruv Matani]

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/


-------------- next part --------------
A non-text attachment was scrubbed...
Name: nstl_algorithm.hpp
Type: text/x-c-header
Size: 7728 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040114/4d98eadc/attachment.bin>