Re: [Valgrind-users] Expected slowdown

[Christoph B. <bar...@or...>]

Am Dienstag, 24. Oktober 2006 17:58 schrieb Julian Seward:
> > It looks like your program is causing a lot of very similar and/or
> > identical stack traces to be created, and the comparisons against the
> > existing ones are taking up a lot of time.
>
> That was my guess too.  But later it occurred to me, Christoph
> said the program first has a nutshell (container, I guess?)
> which allocates a lot of memory - maybe 1 M blocks, and then the
> main algorithm runs.  Suppose the nutshell fills the table
> execontext table up a lot.  Then when the algorithm runs and
> does malloc/free, these will be expensive because each one
> requires searching through long hash chains.
>
> If that's true one simple fix would be the usual hack of moving
> an ExeContext in a chain one step forwards for each successful
> search.  Various other tables already do that.
>
> I suspect this is easy to fix if we have a way to reproduce
> the problem.

I have written a small testprogram that seems to reproduce the problem. First 
I allocate for a given x at 10^x different positions some memory and do not 
free it. Then I allocate and delallocate in an endless loop at the same 
position. 

This programm should simulate the situation you pointed out. The shell 
allocates 1,000,000 blocks of memory and then the core algorithm runs 
allocating only small amounts of memory.

Here is the time that valgrind uses to allocate the memory:

x=4 0.8 seconds
x=5 92 seconds 

I would expect that for x = 5 allocation takes below 10 seconds.

The programm prints the time between 10,000 allocations.

In the run phase the programm is about 10x slower for x=5 than x=4. For x=5 
10,000 allocations take 0.03 seconds and for x=4 they need 0.002 seconds.

Using oprofile the programm shows for x=5 or x=6 the profile I see for my main 
application.

#include <iostream>
#include <sstream>
#include <iomanip>

extern "C" {
#include <sys/time.h>
}

void * alloc() {
  static int count = 0;
  ++count;
  if (count % 10000 == 0) {
        struct timeval tv;
        gettimeofday(&tv, NULL);
        std::cout << "Allocating: " << count << " Time: " << tv.tv_sec << "." 
<< std::setw(6) << tv.tv_usec <<  std::endl;
  }
  return new int[random() % 100];
}

void allocate(int count) {
   if (count == 0) {
      alloc();
      return;
   }
   allocate(count-1);
   allocate(count-1);
   allocate(count-1);
   allocate(count-1);
   allocate(count-1);
   allocate(count-1);
   allocate(count-1);
   allocate(count-1);
   allocate(count-1);
   allocate(count-1);
}


void run() {
   while (true) {
       alloc();
   }
}

int main(int argc, char ** argv) {

   if (argc == 1) return -1;
   std::stringstream ss(argv[1]);
   int depth;
   ss >> depth;
   if (not ss) return -1;

   allocate(depth);
   std::cout << "Allocation ready" << std::endl;
   run();

}


Greetings
Christoph