HW 1 Problem 9

From CSI 702

1. Problem Description

How can this code be made to run more efficiently?

   found = .false.
   i = 1
   do while (i <= large_number .and. .not. found)
      if (value(i) == target_value ) then
          found = .true.
      else
          i = i + 1
      endif
   enddo
   if (found) then
   ...

2. Expectation

The objective of the code is to find a value in a sea of data. First thing the data is disordered, I can not leap finding the value by the inner relationship among data. In a word, I must check data one by one. The problem is when I found the value, we should do something to make the loop stop. It will save a lot of time if the value appears at a early time. I will write a program using C++.

• Done by Qingyang

Additional Expectation. We should expect that when the code can leave the loop exactly when it locates that sought after data point, the performance gain should be directly related to where in the array that data point resides, ie. if the data is at the very front of the array, the speed-up should be siginfincant, and if the data is at the very end of the array, the performance speed up should be negligable compared with the exhaustive array approach. So, if we should assume that if we are looking for data stored randomly in the array, then the typical speed up should the average of the speed up when the data is in the first element of the array and the speed up when it's in the last element of the--with a linear speedup relationship througout the entire array.

• Done by Bob Sorensen

I disagree with the answers above. The inefficiency here is not in finding the value (although that could be improved significantly through hashing or sorting the value array), but through eliminating the superfluous check in the if statement that is inside the while statement.

• Adam Cadien

Avoiding an exhaustive search is, in effect, trying to solve the wrong problem because the algorithm in question does not perform an exhaustive search (it terminates after target_value is found). A potential inefficiency in the algorithm is the ".and. .not. found" section of the while condition, which is evaluated prior to every loop iteration. This clause in the while condition is not necessary because the loop can simply be exited with a break statement when .found. becomes true.

• Thomas Boggs

3. Code

#include <iostream>
#include <ctime>
#include <math.h>
using namespace std;

int main()
{
 long time1=clock();
 int a[900000000];
 int i,flag=0;
 for (i=0;i<900000000;i++)
   a[i]=i;
 /*  
   for(i=0;i<900000000;i++) //method(a)
   {
     if(a[i]==5)
      {
        flag=1;
        break;
      }
   }
 *//*
   for(i=0;i<900000000;i++) //method(b)
   {
     if(a[i]==5)
     flag=1;
   }
*/
   long time2=clock();
   cout << "lasting " << time2-time1 << endl;
   return 0;    
}

• Done by Qingyang

Alternate Code Snippet ---Working this issue without a BREAK statement

 /* Double nested do loop needed to stay within memory bounds of array size  */
 /* but still loop enough to get total execution time on the order of tens of seconds.  */

 /* Exhaustive Loop seach */
	for(j=0;j<max;j++) {
	  for ( i=0;i<n;i++) {
	     if( a[i] == 0) {}
	     else test=1;
	   }
       )


 /* WHILE loop with an intteral IF THEN Test */ 
       for(j=0;j<max;j++) {
 	   test=0;
	   count=0;
	   i=0;
	   while ( (test != 1) && (count < n))  {
	 	if( a[i] == 0) {	}
	 	else{ test=1;}
	 	i++;
	 	count++;
	  	}
	 }

• Done by Bob Sorensen 14:44, 1 February 2010 (EST)

Eliminating the if statement within the while loop makes the code look something like:

i=1;
do while (value(i) != target_value){
    i=i+1;
}
found = .true.;
if(i==large_number){
   found = .false.;
}

• Adam Cadien

Two variations of the search were compared with the original: one that removes the ".and. .not. found" clause of the while statement and another that converts the search to a for loop and returns from the function immediately when target_value is found.

// original algorithm
unsigned long * find_a(unsigned long * array, const unsigned long N, const unsigned long target)
{
    bool found = false;
    unsigned long i = 0;
    while (i < N && !found)
    {
	if (array[i] == target)
	    found = true;	// we could just return from here
	else i++;
    }
    if (found) return &array[i];
    else return 0;
}

// simplified 'while' condition
unsigned long * find_b(unsigned long * array, const unsigned long N, const unsigned long target)
{
    bool found = false;
    unsigned long i = 0;
    while (i < N)
    {
	if (array[i] == target)
	{
	    found = true;	// we could just return from here
	    break;
	}
	else i++;
    }
    if (found) return &array[i];
    else return 0;
}

// using 'for' loop
unsigned long * find_c(unsigned long * array, const unsigned long N, const unsigned long target)
{
    for (unsigned long i = 0; i < N; i++)
    {
	if (array[i] == target) return &array[i];
    }
    return 0;
}

• Thomas Boggs

I used a similar technique to remove the unneccessary if statement in the while loop. I had to run through 1,000 iterations where large_number=2,000,000.

int main()
{
    bool found;
    int i;
    const long large_number = 2000000;
    int value[large_number];
    int target_value = 1;
    value[large_number-1]=1;

    for(int j=0;j<1000;j++)
    {
        i=1;
        found = false;
        while((i<=large_number)&&(found == false))
        {
            if (value[i] == target_value)
            {
                found = true;
            }else{
                i++;
            }
        }
    }
    return 0;
}

int main()
{
    bool found;
    int i;
    const long large_number = 2000000;
    int value[large_number];
    int target_value = 1;
    value[large_number-1]=1;

    for(int j=0;j<1000;j++)
    {
        i=1;
        found = true;
        while((value[i] != target_value) && (i < large_number))
        {
            i++;
        }

        if(i==large_number) found=false;
    }
    return 0;
}

• Done by Stefan Novak

4. Profile and Timing

Because of the nature of this problem it is difficult to do a proper timing analysis. The program runs in about 0.6 seconds for both cases when the loop 10 million checks long, so its easiest just to run it a bunch of times and average out the results. Optimization flags had no noticeable affect.

4.1. The Alternate Interpretation of the Problem Test Results

For this test--the advantage of jumping out of a loop exactly when the answer is found--the program searched though array of length 100k and looped through that 50k times to get results on the order of tens of seconds.

For the baseline test of always going through the entire loop in a simple FOR loop:

Wall clock time is 16 seconds

CPU time is 15.5 seconds

• For case when the 'found' data is 1000th element in the array with the test controlled by a WHILE loop

Wall clock time is 0 seconds

CPU time is 0.203 seconds

• For case when the 'found' data is 10,000th element in the array

Wall clock time is 2 seconds

CPU time is 2.171 seconds

• For case when the 'found' data is 100,000th element in the array ie--the last element

Wall clock time is 22 seconds

CPU time is 21.657 seconds

Note that this execution took longer than the simple exhaustive loop search as in the first case. It would seem that the use of an if-else construct within the while loop adds significant overhead to the point where it is not worth doing this way.

Done by Bob Sorensen

The original and two modified versions were tested at various compiler optimization levels and the variation in run time was less than 0.01% for a search requiring 10 million loop iterations, with results averaged over 1,000 trials. It appears that the simple boolean check in the while statement has negligible impact on performance and the while and for loops are almost equally efficient.

• Thomas Boggs

4.2. Running gprof

The code submitted by Stefan, was compiled in standard form along with O1, O2, and O3 optimization flags. After each run, the code was profiled using gprof with the below results.

5. Results

It's clear that method(a) will run much faster. In the case that I put the flag value at the head of the array, I assume method(b) will take much longer time.

The test result proved my assumption. Method (a) took about 5.54sec. At the same time, method (b) is as long as 17.37sec. It surly tells us to make a break immediately we get what we want in a loop.

• Done by Qingyang

The increase in speed is barely noticeable even on a loop that is 10 million long and optimization turned off my optimized code ran consistently faster by 0.08 seconds which accounts for roughly a speed up of about 20%. I'm content with these results since most of the time will be spent indexing the enormous 'value' array and not checking the while case statement.

• Adam Cadien

Performance increases can be expected when leaving a loop upon finding a specific piece of data, rather than searching the entire loop exhaustively. (No surprise) Indeed, the closer to the front of the array the sought after data resides, the better the performance improvement. However, one needs to carefully contruct such a situtation--such as using using a WHILE loop--as introducing an additional test condition inside the loop may--particularily in cases where the sought after data is near the end of the array--result in degraded performance.

• Done by Bob Sorensen

It appears to be difficult to achieve any significant improvement over the original algorithm, even at various compiler optimization levels. The superfluous additional boolean check in the while clause does not seem to require enough processing time relative to the time required for the loop logic to make a difference. While it has been noted that avoiding an exhaustive search improves algorithm performance, the algorithm in question does not use an exhaustive search so that improvement can not be made.

• Thomas Boggs

In my experiences, it appears that Code B runs slightly faster than Code A, however, Code A experiences better code optimization. This is attributed to some additional optimizations the the compiler is able to do given Code A's structure.

• Done by Stefan Novak

6. Contributors

• Qingyang
• Thomas Boggs
• Bob Sorensen
• Adam Cadien