title: Why is nested for loop not faster with multiple threads using OpenMP?
body: <p>I wrote a function with following 5 parameters:</p>
  <ol>
  <li>array of lines of a text;</li>
  <li>array of some words;</li>
  <li>number of lines (around 40k);</li>
  <li>number of words (about 4-5);</li>
  <li>number of threads to be created (k, tried many values such that 2&lt;k&lt;20).</li>
  </ol>
  <p>The function searches for the given words in a <code>for</code> loop, scanning every line for one word in each iteration (outer for).</p>
  <p>The inner <code>for</code> loop:</p>
  <ul>
  <li>loops through the lines;</li>
  <li>checks if the line contains the given word;</li>
  <li>counts the word's occurrence in the line;</li>
  <li>prints a message if the word was found in the line;</li>
  <li>increases the total occurrence of the word in the whole text with its occurrence in the line.</li>
  </ul>
  <p>I wrote it as a serial program first and then tried to parallelize it using OpenMP, and compare the time it takes for each to analyze the whole text.
  Unfortunately I'm not able to improve the time of the parallel program compared to that of the serial version.</p>
  <p>For measuring the time I use the following functions:</p>
  <pre><code>double ClockCounter;
  
  void start()
  {
          ClockCounter = omp_get_wtime();
  }
  
  void stop()
  {
          ClockCounter = omp_get_wtime() - ClockCounter;
          printf(&quot;Elapsed time: %f\n&quot;, ClockCounter);
  }
  
  </code></pre>
  <p>And the text analyzing function:</p>
  <pre><code>void analyze_text(char **lines, char *words[], size_t nr_lines, int nr_words, int k) {
          int i, total_word_count, word_occurence;
          start();
  #       pragma omp parallel for num_threads(k) \
          default(none) shared(total_word_count, word_occurence) private(i, j, nr_words, nr_lines, word_occurence, counter)
          for (i=0; i&lt;nr_words; i++) {
                  total_word_count = 0;
                  size_t j;
                  printf(&quot;The word is: %s.\nSEARCHING...\n&quot;, words[i]);
  //#             pragma omp parallel for num_threads(k) \
  //              default(none) shared(total_word_count) private(j, nr_lines, word_occurence, counter)
                  for (j=0; j&lt;nr_lines; j++) {
                          char *line = NULL;
                          line = (char *) malloc (strlen(lines[j]) + 1);
                          strcpy(line, lines[j]);
                          word_occurence = 0;
                          if (strstr(line, words[i]) != NULL) {
                                  printf(&quot;Word found at line %ld, position(s): &quot;, j);
                                  char *found_word = NULL;
                                  found_word = (char *) malloc (strlen(words[i]) +1);
                                  char delim[] = &quot; -&quot;;
                                  char *ptr = strtok(line, delim);
                                  int counter =  0;
                                  while (ptr != NULL) {
                                          counter++;
                                          strncpy(found_word, ptr, strlen(words[i]));
                                          found_word[strlen(found_word)] = '\0';
                                          if (strcmp(words[i], found_word) == 0) {
                                                  word_occurence++;
                                                  printf(&quot;%d &quot;, counter);
                                          }
                                          ptr =  strtok(NULL, delim);
  
                                  }
                                  printf(&quot;\nline[%3zu]: %s\n&quot;, j, lines[j]);
                          }
                          total_word_count += word_occurence;
                  }
                  printf(&quot;The word appears %d times in the text in total.\n\n&quot;, total_word_count);
          }
          stop();
  }
  </code></pre>
  <p>As you can see, I tried only parallelizing the inner <code>for</code> loop too but I got no improvement with that either.
  Since the nested <code>for</code> loops are a bit messy, I'm not sure where and how to declare the parallel for directive, nor do I know how to correctly set the variables either to shared or to private.</p>
  <p>The sequential version looks exactly the same but without the omp directive being declared.</p>
  <p>Time (~=) with the sequential version:</p>
  <pre><code>Elapsed time: 0.025583
  </code></pre>
  <p>Time (~=) with the parallel version (k=2, 4, 6, 8, always the same):</p>
  <pre><code>Elapsed time: 0.025690
  </code></pre>
  <p>Can somebody please explain to me what I am missing here?</p>