Why parallel processing takes more time than sequential processing ?

Question

I have a code, in that when you execute it in the parallel environment takes more time than in a sequential way.

Here is the code
https://code.sololearn.com/cCPep2DRYT3l/?ref=app
[Code is just for reference, won't actually work on sololearn code playground ]
--------------------------------------------------------------------------

Execution instruction - (Linux)
For Parallel ~$g++ Bubble.cpp -fopenmp
For Sequential ~$g++ Bubble.cpp

Output:
1) For Parallel: Execution time is 26742 ms
2) For Sequential: Execution time is 14 ms
[NOTE both gives correct output]

--------------------------------------------------------------------------

Why is there a time delay? in parallel processing, it is expected that parallel processing will execute faster. but in actual practice, sequential is executing faster.
What is the reason behind it?

Answer 1

Aaditya Deshpande I shelled out a whole 20 cents and ran your code on 16 cores on AWS, slightly modified:

https://code.sololearn.com/c9nyyPizdP79/?ref=app

sequential: 718 ms
parallel: 218 ms

So the parallel code is about 3 times as fast. I'm not sure how you are getting into half a minute territory then, whatever you are running on must really hate multithreaded code.

Answer 2

Schindlabua , Babak , ~ swim ~ , any idea about this one?

Answer 3

Thank you all I got my answer 👍
Firstly my Data set was small changed it to 50000, also clock in c++ needs to reset, so I switched to chrono library
Special thanks to Schindlabua 👍 for spending 20 cents, for me😇🙏

Answer 4

BroFarOps
「ＨＡＰＰＹ ＴＯ ＨＥＬＰ」
Morpheus
Sonic
HonFu

Answer 5

Schindlabua I think, threads here just splitting my array into a logical groups. here "first" variable is for even-odd selection of groups. threads are spawned inside a for loop and does not depend upon the previous thread.
for example:

5 1 4 2 3

|5 1| |4 2| 3 //first even --step1

1 5 2 4 3 //after swap

1 |5 2| |4 3| //first odd --depends upon step 1 result

1 2 5 3 4 //after swap

|1 2| |5 3| 4 //first even --depends upon step 2 result

1 2 3 5 4 //after swap

1 |2 3| |5 4| //first odd --depends upon step 3 result

1 2 3 4 5 --> Answer

here dependencies are present but after the completion of inner for loop
and that inner for loop gets executed in parallel.

by comparing the number of iterations with sequential bubble sort we can say that this is a better approach for sorting, then why time required is more?

Answer 6

EDIT: Sorry I completely misread your code. You're not doing a classical bubblesort but you've altered it so the inner loop increases by 2 every iteration.

It should be fine honestly, let me run some tests.