title: severe slowdown in a population genetics algorithm using C++ OpenMP: memory management problem?
body: <p>I have a question about optimization in OpenMP that I think involves the organization of memory. My code runs population genetics for a group of N genomes in parallel. A &quot;Genome&quot; is a vector of &quot;Xomes&quot; (chromosomes), which are themselves lists of mutant &quot;Alleles&quot; - the structures are shown below, redacted a bit to keep things simple (I'm working in C++).</p>
  <p><strong>Genome class :</strong></p>
  <pre><code>class Allele {
  public:
      int x;
      int t;
  
      Allele() {}
  };
  
  
  class Xome : public list&lt;Allele&gt; {
  public:
      char t;
       int L;
  
      Xome() {}
  };
  
  
  class Genome : public vector&lt;Xome&gt; {
  public:
  //  location :
      double x;
      double y;
  
  //  sex :
      char t;
  
      Genome() {}
  };
  
  
  typedef list&lt;Genome&gt; Genome_list;
  </code></pre>
  <p>In the population genetics loop, organisms (Genomes) disperse on a landscape, find mates, interbreed and create offspring. Offspring are formed from the parent Genomes in the list x and placed in a buffer, x_buf, as shown below (see &quot;Master loop&quot;, again significantly redacted for clarity).</p>
  <p><strong>Master loop :</strong></p>
  <pre><code>//  parent Genomes :
  Genome_list x;
  
  
  //  initialize x with N Genomes (N=10,000)
  
  
  //  offspring Genome buffer :
  vector&lt;Genome_list&gt; x_buf(n_threads);
  
  
  for (int generation=0; generation!=N; ++generation) {
  
  
  #pragma omp parallel
  {
  //  disperse Genomes in the Genome_list x
  }
  
  
  #pragma omp parallel
  {
      int id;
  
      id=omp_get_thread_num();
  
  //  select mates from x, mutate, put offspring Genomes in x_buf[id]
  }
  
  
  //  clear parent list :
  x.clear();
  
  
  //  splice offspring to parent list :
  int i;
  i=0;
  for ( ; i!=(int) y.size(); ++i) {
  {
      x.splice(x.end(),x_buf[i]);
  }
  
  
  } //  end master loop
  </code></pre>
  <p>At the end of each iteration of the loop, the parent Genome list x is cleared, and the offspring Genomes in x_buf are spliced into x to become the new parent population.</p>
  <p>As the program continues, Genomes accumulate mutations (new Alleles) which causes the program to slow down, obviously. However, I'm finding that even routines that have nothing to do with the memory size of a Genome (e.g the &quot;dispersal&quot; section of the master loop, which only involves changing the values of Genome member variables x and y) get slower as well, even to the point where using, say, two threads takes just as long (in CPU time) as using one thread after about 3000 iterations.</p>
  <p>I remember someone mentioning to me a long while back that I should allocate memory for my Genome lists <strong>within an omp parallel block</strong>; Somehow this was supposed make it easier for the cores to look-up the Genome list data. Anyways, I'm not sure why the code is slowing down. Any help would be appreciated.</p>