Code optimization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
 

## Debugging


- A systematic approach to debugging. 
  - The programmer creates a defect 
  - The defect causes an infection 
  - The infection propagates 
  - The infection causes a failure
- Not every defect causes a failure!
- Testing can only show the presence of errors - not their absence. 
  - In other words, if you pass every tests, it means that your program has yet to fail. 
  It does not mean that your program is correct. 



- Stating the problem
  - Describe the problem aloud or in writing
  - A.k.a. `Rubber duck` or `teddy bear` method
- Often a comprehensive problem description is sufficient to solve the failure



:::::{tab-set} 
::::{tab-item} Bad Fib

- A bad implementation of Fibonacci sequence

<script src="https://gist.github.com/linhbngo/d1e9336a82632c528ea797210ed0f553.js?file=bad_fib.c"></script>

- Specification defined the first Fibonacci number as 1. 
- Compile and run the following `bad_fib.c` program:
- `fib(1)` returns an incorrect result. Why?

~~~bash
$ gcc -o bad_fib bad_fib.c
$ ./bad_fib
~~~
 
::::
::::{tab-item} Scientific debugging

- Before debugging, you need to construct a hypothesis as to the defect.
  - Propose a possible defect and why it explains the failure conditions
- `Ockham’s Razor`: given several hypotheses, pick the simplest/closest to current work





<figure
  
>
  <picture>
    <!-- Auto scaling with imagemagick -->
    <!--
      See https://www.debugbear.com/blog/responsive-images#w-descriptors-and-the-sizes-attribute and
      https://developer.mozilla.org/en-US/docs/Learn/HTML/Multimedia_and_embedding/Responsive_images for info on defining 'sizes' for responsive images
    -->
    
      
        <source
          class="responsive-img-srcset"
          
            srcset="/assets/img/courses/csc231/06-optimization/01-480.webp 480w,/assets/img/courses/csc231/06-optimization/01-800.webp 800w,/assets/img/courses/csc231/06-optimization/01-1400.webp 1400w,"
            type="image/webp"
          
          
            sizes="95vw"
          
        >
      
    
    <img
      src="/assets/img/courses/csc231/06-optimization/01.png"
      
      
        width="50%"
      
      
        height="auto"
      
      
      
        alt="Scientific debugging"
      
      
      
        data-zoomable
      
      
        loading="lazy"
      
      onerror="this.onerror=null; $('.responsive-img-srcset').remove();"
    >
  </picture>

  
</figure>


- Make predictions based on your hypothesis
  - What do you expect to happen under new conditions
  - What data could confirm or refute your hypothesis
- How can I collect that data?
  - What experiments?
  - What collection mechanism?
- Does the data refute the hypothesis?
  - Refine the hypothesis based on the new inputs
::::
::::{tab-item} SD: Bad Fib!
- Constructing a hypothesis: 
  - `while (n 1)`: did we mess up the loop in fib?
  - `int f`: did we forget to initialize `f`?
- Propose a new condition or conditions
  - What will logically happen if your hypothesis is correct?
  - What data can be 
  - fib(1) failed		// Hypothesis
    - Loop check is incorrect: Change to n >= 1 and run again.
    - f is uninitialized: Change to int f = 1;
- Experiment
  - Only change one condition at a time. 
  - fib(1) failed		// Hypothesis
    - Change to `n >= 1`: ???
    - Change to `int f = 1`: Works.  Sometimes a prediction can be a fix.
::::
::::{tab-item} Brute force

- Strict compilation flags: `-Wall`, `-Werror`. 
- Include optimization flags (**capital letter o**): `-O3` or `-O0`. 

~~~bash
$ gcc -Wall -Werror -O3 -o bad_fib bad_fib.c
~~~
 
- Use `valgrind`, memory analyzer. 

~~~bash
$ gcc -Wall -Werror -o bad_fib bad_fib.c
$ valgrind ./bad_fib
~~~
::::
::::{tab-item} Observation

- What is the observed result?
  - Factual observation, such as `Calling fib(1) will return 1.`
  - The conclusion will interpret the observation(s)
- Don’t interfere.
  - Sometimes `printf()` can interfere
  - Like quantum physics, sometimes observations are part of the experiment
- Proceed systematically.
  - Update the conditions incrementally so each observation relates to a specific change
- Do NOT ever proceed past first bug.
::::
:::::




- Common failures and insights
  - Why did the code fail?
  - What are my common defects?
- Assertions and invariants
  - Add checks for expected behavior
  - Extend checks to detect the fixed failure
- Testing
  - Every successful set of conditions is added to the test suite


- Not every problem needs scientific debugging
- Set a time limit: (for example)
  - 0 minutes – -Wall, valgrind
  - 1 – 10 minutes – Informal Debugging
  - 10 – 60 minutes – Scientific Debugging
  - 60 minutes – Take a break / Ask for help