From CSI 702

1. Problem 8

1.1. Description

How can this code be written more efficiently?

   select case (number)
      case (rarely true)
         do useful stuff here
      case (sometimes true)
         do something else useful here
      case (usually true)
         do the normal thing here
   end select

1.2. Expectation

The increase in efficiency possible by rearranging the order of the case statements depends on the relative rarity of the cases. However, it is hypothesized that case statements are efficient enough that reorganization will not provide significant speedup. Also, compiler settings will not have a significant impact on performance.

1.3. Problem Modifications

A c case statement was not flexible enough to perform the test, so the below implementation uses an if-else form.

1.4. Code

#include <stdio.h>
 #include <stdlib.h>
 #include <math.h>
 
 #define NUM_REPS 1000000000
 
 float frand( float );
 
 void caseOne( long );
 void caseTwo( long );
 
 int main( int argc , char* argv[] )
 {
 	if ( argc < 2 )
 	{
 		printf("Usage: problem2 [1|2]\n");
 		exit(-1);
 	}
 
 	int caseNum = atoi( *++argv );
 
 	if ( caseNum == 1 )
 	{
 		caseOne( NUM_REPS );
 	}
 	else if ( caseNum == 2 )
 	{
 		caseTwo( NUM_REPS );
 	}
 	else
 	{
 		printf("Usage: problem2 [1|2]\n");
 		exit(-1);
 	}
 
 	exit(0);
 }
 
 // return a random float value between 0 and max
 float frand( float max )
 {
         return (float) rand( ) / (float) RAND_MAX * max ;
 }
 
 void caseOne( long reps )
 {
 	long i;
 	long count[] = { 0, 0, 0 };
 
 	for ( i = 0 ; i < reps ; i++ )
 	{
 		if ( i % 999997 == 0 )
 		{
 			count[0]++;
 		}
 		else if ( i % 999 == 0 )
 		{
 			count[1]++;
 		}
 		else if ( i % 2 == 0 )
 		{
 			count[2]++;
 		}
 	}
 
 	printf("%ld %ld %ld\n", count[0], count[1], count[2]);
 }
 
 void caseTwo( long reps )
 {
 	long i;
 	long count[] = { 0, 0, 0};
 
 	for ( i = 0 ; i < reps ; i++ )
 	{
 		if ( i % 2 == 0 )
 		{
 			count[0]++;
 		}
 		else if ( i % 999 == 0 )
 		{
 			count[1]++;
 		}
 		else if ( i % 999997 == 0 )
 		{
 			count[2]++;
 		}
 	}
 
 	printf("%ld %ld %ld\n", count[0], count[1], count[2]);
 }

1.5. Profile and Timing

Profiling and timing results were taken for case 1 and case 2 using the unix time command and gprof. The above code was compiled using no gcc compiler optimization flags, -O1, -O2, and -O3. Results from the trials are graphed below. The time values are taken from the cumulative seconds results from gprof timing output.

Full text output for the various runs is also available:

Case 1 No Flags

Case 2 No Flags

Case 1 -O1

Case 2 -O1

Case 1 -O2

Case 2 -O2

Case 1 -O3

Case 2 -O3

Note: The wiki does not allow external image links (as far as I can tell). However, the following is the Google Chart API URL to generate the above chart:

http://chart.apis.google.com/chart?chs=600x400&cht=lxy&chdl=Code%201|Code%202&chco=FF0000,00FF00&chg=33,25&chm=o,FF0000,0,-1,10.0|o,00FF00,1,-1,10.0&chtt=Problem%208%20Timing&chxt=x,y,x,y&chxl=0:|None|-01|-02|-O3|1:|0.0|15.0|30.0|2:||Compiler%20Option||3:||Time%20%28sec%29|&chd=t:-1|29.66,4.06,3.90,3.88|-1|14.75,2.55,2.48,2.48&chds=0,30

1.6. Comments

As expected, the version with the most common case listed first in the if-else clause performed better (about a two times speedup). However, this only held true at low compiler optimization levels. Even with -O1, most of the advantage of careful ordering of clauses had been negated by compiler optimizations.

1.7. References

1.8. Contributors

Geoffrey Ulman