title: Why is my parallel code slower than serial?
body: <p><strong>Issue</strong></p>
  
  <p>Hello everyone, I have got a program (from the net) that I intend to speed up by converting it into its parallel version with the use of <code>pthreads</code>. But surprisingly though, it runs <strong>slower</strong> than the serial version. Below is the program:</p>
  
  <pre><code># include &lt;stdio.h&gt;
  
  //fast square root algorithm
  double asmSqrt(double x) 
  {
    __asm__ ("fsqrt" : "+t" (x));
    return x;
  }
  
  //test if a number is prime
  bool isPrime(int n)
  {   
      if (n &lt;= 1) return false;
      if (n == 2) return true;
      if (n%2 == 0) return false;
  
      int sqrtn,i;
      sqrtn = asmSqrt(n);
  
      for (i = 3; i &lt;= sqrtn; i+=2) if (n%i == 0) return false;
      return true;
  }
  
  //number generator iterated from 0 to n
  int main()
  {
      n = 1000000; //maximum number
      int k,j;
  
      for (j = 0; j&lt;= n; j++)
      {
          if(isPrime(j) == 1) k++;
          if(j == n) printf("Count: %d\n",k);
      }
      return 0;
  }
  </code></pre>
  
  <p><strong>First attempt for parallelization</strong></p>
  
  <p>I let the <code>pthread</code> manage the <code>for loop</code></p>
  
  <pre><code># include &lt;stdio.h&gt;
  .
  .
  
  int main()
  {
      .
      .
      //-----&gt;pthread code here&lt;----
      for (j = 0; j&lt;= n; j++)
      {
          if(isPrime(j) == 1) k++;
          if(j == n) printf("Count: %d\n",k);
      }
      return 0;
  }
  </code></pre>
  
  <p>Well, it runs slower than the serial one</p>
  
  <p><strong>Second attempt</strong></p>
  
  <p>I divided the <code>for loop</code> into <strong>two threads</strong> and run them in parallel using <code>pthreads</code></p>
  
  <p>However, it still runs slower, I am intending that it may run about twice as fast or well faster. But its not!</p>
  
  <p>These is my parallel code by the way:</p>
  
  <pre><code># include &lt;stdio.h&gt;
  # include &lt;pthread.h&gt;
  # include &lt;cmath&gt;
  
  # define NTHREADS 2
  
  pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
  int k = 0;
  
  double asmSqrt(double x) 
  {
    __asm__ ("fsqrt" : "+t" (x));
    return x;
  }
  
  struct arg_struct
  {
      int initialPrime;
      int nextPrime;
  };
  
  bool isPrime(int n)
  {   
      if (n &lt;= 1) return false;
  
      if (n == 2) return true;
  
      if (n%2 == 0) return false;
  
      int sqrtn,i;
      sqrtn = asmSqrt(n);
  
      for (i = 3; i &lt;= sqrtn; i+=2) if (n%i == 0) return false;
  
      return true;
  }
  
  void *parallel_launcher(void *arguments)
  {
      struct arg_struct *args = (struct arg_struct *)arguments;
  
      int j = args -&gt; initialPrime;
      int n = args -&gt; nextPrime - 1;
  
      for (j = 0; j&lt;= n; j++)
      {
          if(isPrime(j) == 1)
          {
              printf("This is prime: %d\n",j);
  pthread_mutex_lock( &amp;mutex1 );
              k++;
  pthread_mutex_unlock( &amp;mutex1 );
          }
  
          if(j == n) printf("Count: %d\n",k);
      }
  pthread_exit(NULL);
  }
  
  int main()
  {
      int f = 100000000;
      int m;
  
      pthread_t thread_id[NTHREADS];
      struct arg_struct args;
  
      int rem = (f+1)%NTHREADS;
      int n = floor((f+1)/NTHREADS);
  
      for(int h = 0; h &lt; NTHREADS; h++)
      {
          if(rem &gt; 0)
          {
              m = n + 1;
              rem-= 1;
          }
          else if(rem == 0)
          {
              m = n;
          }
  
          args.initialPrime = args.nextPrime;
          args.nextPrime = args.initialPrime + m;
  
          pthread_create(&amp;thread_id[h], NULL, &amp;parallel_launcher, (void *)&amp;args);
          pthread_join(thread_id[h], NULL);
      }
     // printf("Count: %d\n",k);
      return 0;
  }
  </code></pre>
  
  <p><strong>Note:</strong>
  OS: Fedora 21 x86_64,
  Compiler: gcc-4.4,
  Processor: Intel Core i5 (2 physical core, 4 logical),
  Mem: 6 Gb,
  HDD: 340 Gb,</p>