Re: Performance of the default node allocator.

[Loren James Rittle <rittle at latour dot rsch dot comm dot mot dot com>]

> I have here a program that allocates lots of list node, deallocates
> them, and then reallocates them. It appears that the default node
> allocator fails to preserve the locality or something, and it's
> performance is reflected while sorting the list, when the 2nd time is 
> observered to perform much worse compared to the first (double the
> time). I wonder if the allocation starategy of the default node
> allocator can be changed? BTW, an allocator calling malloc and free
> performs better in terms of preserving order of elements in memory.

Hi, This is the best answer I can give quickly.

I think your test is somewhat interesting.  However, the library
doesn't make performance guarantees regarding interactions with the
cache architecture on any given platform.  I believe that is the
effect you are seeing.  Based on your report, I assume that malloc
implementations which do coalescing and/or ordering upon free() will
perform better, with your case mapped directly to malloc, than those
that don't.  Hint: the library does no coalescing or ordering of its
free list.

Dhruv, do I have your permission to install this modified version of
your performance test case?

Regards,
Loren

#include <iostream>
#include <algorithm>
#include <list>
#include <memory>
#include <testsuite_performance.h>

template <class T>
void clear_container (T& _cont) { T temp; std::swap (temp, _cont); }

int main ()
{
  std::list <double> il;
  using namespace __gnu_test;
  time_counter time;
  resource_counter resource;

  for (int x = 3; x--;)
    {
      srand(0);
      start_counters(time, resource);
      for (int i = 0; i < 700000; ++i)
	il.push_back(rand()%300);
      stop_counters(time, resource);
      report_performance(__FILE__, "insert", time, resource);

      start_counters(time, resource);
      il.sort();
      stop_counters(time, resource);
      report_performance(__FILE__, "sort", time, resource);

      start_counters(time, resource);
      clear_container(il);
      stop_counters(time, resource);
      report_performance(__FILE__, "clear", time, resource);
    }
}