Palindromes

In this post I will try to optimize and make parallel (if necessary) an algorithm which determines whether a given English word is a palindrome or not. The input was of 71 million words.

You may have a look at the initial program here

Program description

It consists of three functions along with the main function :

• findPalindromes - takes the input size and words, outputs the no. of palindromes.
• parse_string - converts a given input string into lower case.
• is_palindrome - checks if the given input word is a palindrome.

When i ran the algorithm with the input, I got the following output

gprof parallel_palin.exe | more gave the following output

The above image shows that the program is spending most of it's time in the function parse_string.

I removed the use of function parse_string in the function findPalindromes and ran the program again.

There was a huge decrease in the execution time, though the answer was not correct, but it was close enough. As I discussed my previous post, it's not all about making things parallel rather it is about optimizing it.

You can see the output in the following,

There was a drop of about 80% in the execution time. These are little bits which optimize the code a lot.

Now I identified the parallelizable regions, the for loop in findPalindromes and in parse_string. If the for loop in parse_string is parellelized, then the work done in each thread is very less, hence the overhead of creating them is more. Then I made the for loop in findPalindromes parallel.

Output :

There was not much difference. 

This program was an example where parallelizing the program didn't reduce the execution time too much.

In another future post, I will discuss a program(most probably Matrix multiplication) where parallelizing a program is more effective.