216 Intermediate C Programming
int valid = 0;11
i f ( ind == 0) // no restri ction for the first number12
{13
valid = 1;14
}15
e l s e16
{17
valid = ( arr [ ind - 1] % 2) != ( val % 2) ;18
}19
i f ( valid == 1)20
{21
arr [ ind ] = val ;22
partition ( arr , ind + 1 , left - val ) ;23
}24
}25
}26
Line 18 tests whether arr[ind - 1] and val are both even or both odd. As you can see,
with only a few small changes, the program can print the solutions for the integer partition
problem under different restrictions.
14.3.4 Using gprof and gcov to Identify Performance Bottlenecks
Section 13.7 explains how to use gprof to identify opportunities for performance im-
provement. This section uses gprof to compare different ways to restrict integer partitions.
In the following program, partition1 generates only valid partitions, but partition2 gen-
erates all possible partitions and uses isValid to decide whether or not to print a given
partition. The function printPartition does nothing in this example because printing
many lines can noticeably slow down a program. Since both programs print the same re-
sult, there is no reason for examining this function. We can examine the performance of
partition1 and partition2 without the distraction of printPartition.
// co mppart i tion .c1
// part i tion using al t ernating odd and even nu m bers2
// two ways to i mplement the partition :3
// 1. check before recursive calls4
// 2. generate all partition s and check before printin g5
#in clude < stdio .h >6
#in clude < stdlib .h >7
void print Partit ion ( in t * arr , int length )8
{9
/*10
int ind ;11
for ( ind = 0; ind < length - 1; ind ++)12
{13
printf ("% d + ", arr [ ind ]) ;14
}15
printf ("% d n" , arr [ length - 1]) ;16
*/17
}18
// 1. generate only valid partiti ons19
void partitio n 1 ( i n t * arr , in t ind , in t left )20
Integer Partition 217
{21
int val ;22
i f ( left == 0)23
{24
prin t Partit ion ( arr , ind );25
return ;26
}27
for ( val = 1; val <= left ; val ++)28
{29
int valid = 0;30
i f ( ind == 0) // no restri ction for the first number31
{32
valid = 1;33
}34
e l s e35
{36
valid = ( arr [ ind - 1] % 2) != ( val % 2) ;37
}38
i f ( valid == 1)39
{40
arr [ ind ] = val ;41
partiti o n1 ( arr , ind + 1 , left - val );42
}43
}44
}45
// 2. before printing , check whether the part i tion is valid46
// check whether the numbers are alte rnating odd and even47
// return 1 if valid48
// return 0 if invalid49
int isValid ( i n t * arr , in t len )50
{51
i f ( len <= 1) // if only one number , it is valid52
{53
return 1;54
}55
int ind ;56
for ( ind = 2; ind < len ; ind += 2)57
{58
59
// invalid if they are different60
i f (( arr [ ind ] % 2) != ( arr [0] % 2) )61
{62
return 0;63
}64
}65
for ( ind = 1; ind < len ; ind += 2)66
{67
68
// invalid if they are the same69
i f (( arr [ ind ] % 2) == ( arr [0] % 2) )70
{71
218 Intermediate C Programming
return 0;72
}73
}74
return 1;75
}76
// generat e all possible partitions , including invalid77
// check before printing78
void partitio n 2 ( i n t * arr , in t ind , in t left )79
{80
int val ;81
i f ( left == 0)82
{83
i f ( isValid (arr , ind ) == 1)84
{85
prin t Partit ion ( arr , ind );86
}87
return ;88
}89
for ( val = 1; val <= left ; val ++)90
{91
arr [ ind ] = val ;92
partiti o n2 ( arr , ind + 1 , left - val );93
}94
}95
96
int main ( i n t argc , char * argv [])97
{98
i f ( argc != 2)99
{100
return EXIT _FAILUR E ;101
}102
int n = ( i n t ) strtol ( argv [1] , NULL , 10) ;103
i f (n <= 0)104
{105
return EXIT _FAILUR E ;106
}107
int * arr ;108
arr = malloc ( s i z e o f ( i nt ) * n) ;109
printf (" ----- Partiti o n 1 - -- -- n") ;110
partiti o n1 ( arr , 0, n );111
printf (" ----- Partiti o n 2 - -- -- n") ;112
partiti o n2 ( arr , 0, n );113
free ( arr );114
return EXIT _SUCCES S ;115
}116
This is the report from gprof when n is 30.
Flat profile :
Each sam ple counts as 0.01 seconds .
% cumul a tive self self total
Integer Partition 219
time seconds seconds calls s / call s/ call name
55.74 6.75 6.75 1 6.75 11.99 p a rtiti o n2
43.28 11.99 5.24 53687 0912 0.00 0.00 isValid
1.50 12.17 0.18 1 0.18 0.18 partit ion1
0.00 12.17 0.00 20 2786 0.00 0.00 print P artition
index % time self chi ldren ca lled name
< spontaneous >
[1] 100.0 0.00 12.17 main [1]
6.75 5.24 1/1 par t ition2 [2]
0.18 0.00 1/1 par t ition1 [4]
-------- - - - - - - - - --------------- - - - - - - - - - -------
107 3 741823 par t ition2 [2]
6.75 5.24 1/1 main [1]
[2] 98.5 6.75 5.24 1 + 1073741 8 23 parti tion2 [2]
5.24 0.00 536870912 / 5 3 6 870912 isValid [3]
0.00 0.00 1 0 1393/202 7 86 prin t Partition [5]
107 3 741823 par t ition2 [2]
-------- - - - - - - - - --------------- - - - - - - - - - -------
5.24 0.00 536870912 / 5 3 6 870912 p artiti on2 [2]
[3] 43.1 5.24 0.00 53687 0912 isV alid [3]
-------- - - - - - - - - --------------- - - - - - - - - - -------
308288 pa r tition 1 [4]
0.18 0.00 1/1 main [1]
[4] 1.5 0.18 0.00 1+308288 partit ion1 [4]
0.00 0.00 1 0 1393/202 7 86 prin t Partition [5]
308288 pa r tition 1 [4]
-------- - - - - - - - - --------------- - - - - - - - - - -------
0.00 0.00 1 0 1393/202 7 86 par tition 1 [4]
0.00 0.00 1 0 1393/202 7 86 par tition 2 [2]
[5] 0.0 0.00 0.00 2 02786 printPart i tion [5]
-------- - - - - - - - - --------------- - - - - - - - - - -------
This report shows that nearly 99% of the program’s execution time is taken by
partition2 (55.7%) and isValid (43.3%). Since isValid is called only by partition2, the
report shows that partition2 takes 98.5% of the time. In contrast, partition1 takes only
1.5% of the time. Why is there such a large difference? The reason is that partition2 gen-
erates many invalid partitions and then uses isValid to check before printing. In contrast,
partition1 generates only valid partitions. The latter approach reduces huge portions of
the call tree, and is thus much more efficient.
Please notice that [4] shows printPartition is called by partition1 101393 times
and by partition2 101393 times. This is expected since partition1 and partition2
should print exactly the same partitions. The function partition2 is called 1073741823
times by recursion but partition1 is called only 308288 times. The report also shows that
isValid is called 536870912 times but printPartition is called only 202786 times (by
both partition1 and partition2). This means that most of the generated partitions are
invalid and are not printed. This is another indication that partition2 generates many
invalid partitions. Notice that 55.74%, 43.28%, and 1.50% sum to 100.52%. How can it be
possible that the cumulative time is above 100%? This shows a limitation of gprof: This
tool is intended to be fast but the accuracy is not so great. Profiling code always interferes
with the normal execution of the code, and there must be a trade-off somewhere.
When we want to improve a program’s performance, then we first need to identify
the functions that take the most amount of time. We can get some help by using gprof.
220 Intermediate C Programming
After finding the functions, we need to think about whether these functions are doing
any unnecessary work. Eliminating unnecessary computation should be the first step in
improving performance. Note that this is also the principle behind qsort: It uses transitivity
to eliminate unnecessary comparisons.
We can also use gcov to find the opportunities for improving performance. This is
primarily used to examine test coverage: It helps us understand the quality of the tests.
Section 5.5 explains how to use gcov to examine test coverage. Here we show how to use
gcov to look for performance bottlenecks. To run gcov, we must add -fprofile-arcs
-ftest-coverage after gcc. The program can be executed normally. When the program
runs, two files are generated: One has .gcda extension and the other has .gcno extension.
The next step is to run the gcov command. It will generate another file whose extension
is .gcov. This is the file that we want to examine. Here are the contents of the file from a
sample run (suppose the value of n is 30).
-: 0: Source : gprofeg . c
-: 0: Graph : gpr ofeg . gcno
-: 0: Data : gprofeg . gcda
-: 0: Runs :1
-: 0: P r o grams :1
-: 1: // part i tion using alt ernating odd and even
numbers
-: 2: // two ways to i m plement the partition :
-: 3: // 1. check before recursive calls
-: 4: // 2. generate all partition s and check
before printing
-: 5:# include < stdio .h >
-: 6:# include < stdlib .h >
-: 7:
202786: 8: void pri ntPart ition ( i n t * arr , i nt length )
-: 9:{
-: 10: /*
-: 11: int ind ;
-: 12: for ( ind = 0; ind < length - 1; ind ++)
-: 13: {
-: 14: printf ("% d + " , arr [ ind ]) ;
-: 15: }
-: 16: printf ("% dn ", arr [ length - 1]) ;
-: 17: */
202786: 18:}
-: 19:
-: 20: // 1. do not generate invalid partial
partiti o ns
308289: 21: void pa r tition1 ( i n t * arr , i n t ind , i n t left )
-: 22:{
-: 23: i nt val ;
308289: 24: i f ( left == 0)
-: 25: {
101393: 26: p rintPa rtitio n ( arr , ind );
409682: 27: return ;
-: 28: }
835786: 29: fo r ( val = 1; val <= left ; val ++)
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.