title: Why is multithreading slower than sequential programming in my case?
body: <p>I'm new to multithreading and try to learn it through a simple program, which adds 1 to n and return the sum. In the sequential case, the <code>main</code> call the <code>sumFrom1</code> function twice for n = 1e5 and 2e5; in the multithreaded cases, two threads are created using <code>pthread_create</code> and two sums are calculated in separate thread. The multithreadting version is much slower than the sequential version (see results below). I run this on a 12-CPU platform and there are no communication between threads.</p>
  
  <p>Multithreaded:</p>
  
  <pre><code>Thread 1 returns: 0 
  Thread 2 returns: 0 
  sum of 1..10000: 50005000
  sum of 1..20000: 200010000
  time: 156 seconds
  </code></pre>
  
  <p>Sequential:</p>
  
  <pre><code>sum of 1..10000: 50005000
  sum of 1..20000: 200010000
  time: 56 seconds
  </code></pre>
  
  <p>When I add <strong>-O2</strong> in compilation, the time of multithreaded version (9s) is less than that of sequential version (11s), but not much as I expect. I can always have the <strong>-O2</strong> flag on but I'm curious about the low speed of multithreading in the unoptimized case. Should it be slower than sequential version? If not, what can I do to make it faster?</p>
  
  <p>The code:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;pthread.h&gt;
  #include &lt;time.h&gt;
  
  typedef struct my_struct
  {
    int n;                                                                                                                                                              
    int sum;                                                                                                                                                            
  }my_struct_t;                                                                                                                                                         
  
  void *sumFrom1(void* sit)                                                                                                                                              
  {                                                                                                                                                                     
    my_struct_t* local_sit = (my_struct_t*) sit;                                                                                                                          
    int i;                                                                                                                                                              
    int nsim = 500000;  // Loops for consuming time                                                                                                                                                
    int j;                                                                                                                                                              
  
    for(j = 0; j &lt; nsim; j++)                                                                                                                                           
    {                                                                                                                                                                   
      local_sit-&gt;sum = 0;                                                                                                                                                
      for(i = 0; i &lt;= local_sit-&gt;n; i++)                                                                                                                                 
        local_sit-&gt;sum += i;                                                                                                                                             
    }    
  }
  
  int main(int argc, char *argv[])                                                                                                                                      
  {                                                                                                                                                                     
    pthread_t    thread1;                                                                                                                                               
    pthread_t    thread2;                                                                                                                                               
    my_struct_t  si1;                                                                                                                                                   
    my_struct_t  si2;                                                                                                                                                   
    int          iret1;                                                                                                                                                 
    int          iret2;                                                                                                                                                 
    time_t       t1;                                                                                                                                                    
    time_t       t2;                                                                                                                                                    
  
  
    si1.n = 10000;                                                                                                                                                      
    si2.n = 20000;                                                                                                                                                      
  
    if(argc == 2 &amp;&amp; atoi(argv[1]) == 1) // Use "./prog 1" to test the time of multithreaded version                                                                                                                                
    {                                                                                                                                                                   
      t1 = time(0);                                                                                                                                                     
      iret1 = pthread_create(&amp;thread1, NULL, sumFrom1, (void*)&amp;si1);      
      iret2 = pthread_create(&amp;thread2, NULL, sumFrom1, (void*)&amp;si2);                                                                                                     
      pthread_join(thread1, NULL);                                                                                                                                      
      pthread_join(thread2, NULL);                                                                                                                                      
      t2 = time(0);                                                                                                                                                     
  
      printf("Thread 1 returns: %d\n",iret1);                                                                                                                           
      printf("Thread 2 returns: %d\n",iret2);                                                                                                                           
      printf("sum of 1..%d: %d\n", si1.n, si1.sum);                                                                                                                     
      printf("sum of 1..%d: %d\n", si2.n, si2.sum);                                                                                                                     
      printf("time: %d seconds", t2 - t1);                                                                                                                              
  
    }                                                                                                                                                                   
    else     // Use "./prog" to test the time of sequential version                                                                                                                                                           
    {                                                                                                                                                                   
      t1 = time(0);                                                                                                                                                     
      sumFrom1((void*)&amp;si1);                                                                                                                                            
      sumFrom1((void*)&amp;si2);                                                                                                                                            
      t2 = time(0);                                                                                                                                                     
  
      printf("sum of 1..%d: %d\n", si1.n, si1.sum);                                                                                                                     
      printf("sum of 1..%d: %d\n", si2.n, si2.sum);                                                                                                                     
      printf("time: %d seconds", t2 - t1); 
    }                                                                                             
    return 0;                                                                                         
  }   
  </code></pre>
  
  <p><strong>UPDATE1:</strong></p>
  
  <p>After a little googling on "false sharing" (Thanks, @Martin James!), I think it is the main cause. There are (at least) two ways to fix it:</p>
  
  <p>The first way is inserting a buffer zone between the two structs (Thanks, @dasblinkenlight):</p>
  
  <pre><code>my_struct_t  si1;
  char         memHolder[4096];
  my_struct_t  si2; 
  </code></pre>
  
  <p>Without <strong>-O2</strong>, the time consuming decreases from ~156s to ~38s.</p>
  
  <p>The second way is avoiding frequently updating <code>sit-&gt;sum</code>, which can be realized using a temp variable in <code>sumFrom1</code> (as @Jens Gustedt replied):</p>
  
  <pre><code>for(int sum = 0, j = 0; j &lt; nsim; j++)              
  {
    sum = 0;
    for(i = 0; i &lt;= local_sit-&gt;n; i++)
      sum += i;
  }
  local_sit-&gt;sum = sum;
  </code></pre>
  
  <p>Without <strong>-O2</strong>, the time consuming decreases from ~156s to ~35s or ~109s (It has two peaks! I don't know why.). With <strong>-O2</strong>, the time consuming stays ~8s.</p>