Why the sorted array values comparison take less time then non sorted array values

Question

4.00/5 (1 vote)

See more:

C++

 const unsigned arraySize = 100000;
 int data[arraySize];
 int sum = 0;

 for (unsigned c = 0; c < arraySize; ++c)
     data[c] = std::rand() % 256;

 std::sort(data, data + arraySize);

for (unsigned c = 0; c < arraySize; ++c)
{
         if (data[c] >= 128)
             sum += data[c];
 }

The above code display the result within 3.2 Sec.

Now i remove the sort method.

C++

 const unsigned arraySize = 100000;
 int data[arraySize];
 int sum = 0;

 for (unsigned c = 0; c &lt; arraySize; ++c)
     data[c] = std::rand() % 256;

for (unsigned c = 0; c < arraySize; ++c)
{
         if (data[c] >= 128)
             sum += data[c];
 }

The above code display the result within 7.2 Sec.

Posted 8-Dec-14 22:47pm

MytheenAbdul

Updated 9-Dec-14 0:10am

Aescleal

v3

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Fredrik Bornander · Accepted Answer · 2014-12-08T23:36:00

Solution 1

Branch-prediction[^].
A guess is made whether or not to branch at the if-statement, and for the sorted one most times guessing that the previous way is the way to go will be the correct guess.
Sorting makes it easy for the branch-predictor to get it right.

Posted 8-Dec-14 23:36pm

Fredrik Bornander

Comments

nv3 9-Dec-14 6:41am

What's surprising though is the additional time used for the sorting seems to take considerably less time than what is gained by branch-prediction in a single loop through the data.

And also: 7.2 sec is very slow for two trivial loops over with 100.000 iterations on any modern processor.

My suspicion: The measurement was not done correctly.

Aescleal 9-Dec-14 11:30am

I think there's probably something a bit weird with his measurements as well. My rather naff i5 can do a partial sum of 20 million ints in about 80ms. Sorting the data takes ages but halves the time taken to do the partial sum. Even better is partioning the data into two ranges and then just summing the range you want - that takes about 4ms.