Massachusetts Institute of Technology
Department of Electrical Engineering and Computer Science
6.087: Practical Programming in C
IAP 2010
Problem Set 3 – Solutions
Control flow. Functions. Variable scope. Static and global variables. I/O: printf and scanf. File
I/O. Character arrays. Error handling. Labels and goto.
Out: Wednesday, January 13, 2010. Due: Friday, January 15, 2010.
Problem 3.1
Code profiling and registers. In this problem, we will use some basic code profiling to examine
the effects of explicitly declaring variables as registers. Consider the fibonacci sequence generating
function fibonacci in prob1.c, which is reproduced at the end of this problem set (and can be
downloaded from Stellar). The main() function handles the code profiling, calling fibonacci()
many times and measuring the average processor time.
(a) First, to get a baseline (without any explicitly declared registers), compile and run prob1.c.
Code profiling is one of the rare cases where using a debugger like gdb is discouraged, because
the debugger’s overhead can impact the execution time. Also, we want to turn off compiler
optimization. Please use the following commands to compile and run the program:
dweller@dwellerpc:~$ gcc -O0 -Wall prob1.c -o prob1.o
dweller@dwellerpc:~$ ./prob1.o
Avg. execution time: 0.000109 msec ← example output
dweller@dwellerpc:~$
How long does a single iteration take to execute (on average)?
Answer: On my 64-bit machine (results may differ slightly for 32-bit machines), the original
fibonacci() function took 0.000109 msec on average.
(b) Now, modify the fibonacci() function by making the variables a, b, and c register variables.
Recompile and run the code. How long does a single iteration take now, on average? Turn
in a printout of your modified code (the fibonacci() function itself would suffice).
Answer: Here’s the modified fibonacci() function for part (b):
void f i b o n a c c i ( )
{
/∗ h e r e a r e t h e v a r i a b l e s t o s e t a s r e g i s t e r s ∗/
r e g i s t e r unsigned i n t a = 0 ;
r e g i s t e r unsigned i n t b = 1 ;
r e g i s t e r unsigned i n t c ;
int n ;
/∗ do not e d i t below t h i s l i n e ∗/
results buffer [0] = a;
results buffer [1] = b;
f o r ( n = 2 ; n < NMAX; n++) {
c = a + b;
1
, r e s u l t s b u f f e r [ n ] = c ; /∗ s t o r e code i n r e s u l t s b u f f e r ∗/
a = b;
b = c;
}
}
On my 64-bit machine (results may differ slightly for 32-bit machines), the modified function
took 0.000111 msec on average.
(c) Modify the fibonacci() function one more time by making the variable n also a register
variable. Recompile and run the code once more. How long does a single iteration take with
all four variables as register variables?
Answer: Here’s the modified fibonacci() function for part (c):
void f i b o n a c c i ( )
{
/∗ h e r e a r e t h e v a r i a b l e s t o s e t a s r e g i s t e r s ∗/
r e g i s t e r unsigned i n t a = 0 ;
r e g i s t e r unsigned i n t b = 1 ;
r e g i s t e r unsigned i n t c ;
r e g i s t e r i nt n ;
/∗ do not e d i t below t h i s l i n e ∗/
results buffer [0] = a;
results buffer [1] = b;
f o r ( n = 2 ; n < NMAX; n++) {
c = a + b;
r e s u l t s b u f f e r [ n ] = c ; /∗ s t o r e code i n r e s u l t s b u f f e r ∗/
a = b;
b = c;
}
}
On my 64-bit machine (results may differ slightly for 32-bit machines), the further modified
fibonacci() function took 3.4e-05 msec on average.
(d) Comment on your observed results. What can you conclude about using registers in your
code?
Answer: The observed results suggest that storing some variables in a register vs. in memory
may or may not impact performance. In particular, storing a, b, and c in registers do not
appear to improve the performance at all, while storing n in a register improves performance
by a factor of 3.
Problem 3.2
We are writing a simple searchable dictionary using modular programming. First, the program
reads a file containing words and their definitions into an easily searchable data structure. Then,
the user can type a word, and the program will search the dictionary, and assuming the word is
found, outputs the definition. The program proceeds until the user chooses to quit.
We split the code into several files: main.c, dict.c, and dict.h. The contents of these files are
described briefly below.
2
Department of Electrical Engineering and Computer Science
6.087: Practical Programming in C
IAP 2010
Problem Set 3 – Solutions
Control flow. Functions. Variable scope. Static and global variables. I/O: printf and scanf. File
I/O. Character arrays. Error handling. Labels and goto.
Out: Wednesday, January 13, 2010. Due: Friday, January 15, 2010.
Problem 3.1
Code profiling and registers. In this problem, we will use some basic code profiling to examine
the effects of explicitly declaring variables as registers. Consider the fibonacci sequence generating
function fibonacci in prob1.c, which is reproduced at the end of this problem set (and can be
downloaded from Stellar). The main() function handles the code profiling, calling fibonacci()
many times and measuring the average processor time.
(a) First, to get a baseline (without any explicitly declared registers), compile and run prob1.c.
Code profiling is one of the rare cases where using a debugger like gdb is discouraged, because
the debugger’s overhead can impact the execution time. Also, we want to turn off compiler
optimization. Please use the following commands to compile and run the program:
dweller@dwellerpc:~$ gcc -O0 -Wall prob1.c -o prob1.o
dweller@dwellerpc:~$ ./prob1.o
Avg. execution time: 0.000109 msec ← example output
dweller@dwellerpc:~$
How long does a single iteration take to execute (on average)?
Answer: On my 64-bit machine (results may differ slightly for 32-bit machines), the original
fibonacci() function took 0.000109 msec on average.
(b) Now, modify the fibonacci() function by making the variables a, b, and c register variables.
Recompile and run the code. How long does a single iteration take now, on average? Turn
in a printout of your modified code (the fibonacci() function itself would suffice).
Answer: Here’s the modified fibonacci() function for part (b):
void f i b o n a c c i ( )
{
/∗ h e r e a r e t h e v a r i a b l e s t o s e t a s r e g i s t e r s ∗/
r e g i s t e r unsigned i n t a = 0 ;
r e g i s t e r unsigned i n t b = 1 ;
r e g i s t e r unsigned i n t c ;
int n ;
/∗ do not e d i t below t h i s l i n e ∗/
results buffer [0] = a;
results buffer [1] = b;
f o r ( n = 2 ; n < NMAX; n++) {
c = a + b;
1
, r e s u l t s b u f f e r [ n ] = c ; /∗ s t o r e code i n r e s u l t s b u f f e r ∗/
a = b;
b = c;
}
}
On my 64-bit machine (results may differ slightly for 32-bit machines), the modified function
took 0.000111 msec on average.
(c) Modify the fibonacci() function one more time by making the variable n also a register
variable. Recompile and run the code once more. How long does a single iteration take with
all four variables as register variables?
Answer: Here’s the modified fibonacci() function for part (c):
void f i b o n a c c i ( )
{
/∗ h e r e a r e t h e v a r i a b l e s t o s e t a s r e g i s t e r s ∗/
r e g i s t e r unsigned i n t a = 0 ;
r e g i s t e r unsigned i n t b = 1 ;
r e g i s t e r unsigned i n t c ;
r e g i s t e r i nt n ;
/∗ do not e d i t below t h i s l i n e ∗/
results buffer [0] = a;
results buffer [1] = b;
f o r ( n = 2 ; n < NMAX; n++) {
c = a + b;
r e s u l t s b u f f e r [ n ] = c ; /∗ s t o r e code i n r e s u l t s b u f f e r ∗/
a = b;
b = c;
}
}
On my 64-bit machine (results may differ slightly for 32-bit machines), the further modified
fibonacci() function took 3.4e-05 msec on average.
(d) Comment on your observed results. What can you conclude about using registers in your
code?
Answer: The observed results suggest that storing some variables in a register vs. in memory
may or may not impact performance. In particular, storing a, b, and c in registers do not
appear to improve the performance at all, while storing n in a register improves performance
by a factor of 3.
Problem 3.2
We are writing a simple searchable dictionary using modular programming. First, the program
reads a file containing words and their definitions into an easily searchable data structure. Then,
the user can type a word, and the program will search the dictionary, and assuming the word is
found, outputs the definition. The program proceeds until the user chooses to quit.
We split the code into several files: main.c, dict.c, and dict.h. The contents of these files are
described briefly below.
2
