Carnegie Mellon
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1
14
–
513
18
–
613
Carnegie Mellon
Design and Debugging
15-213/18-213/14-513/15-513/18-613: Introduction to Computer Systems 12th Lecture, October 8, 2020
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
2
Carnegie Mellon
Announcements Lab 3 (attacklab)
▪ Due this Thursday, Oct. 8, 11:59pm ET
Lab 4 (cachelab)
▪ Out Oct. 8, 11:59pm ET ▪ Due Oct. 20, 11:59pm ET
Written Assignment 4 peer grading ▪ Due Wed, Oct. 14, 11:59pm ET
Written Assignment 5 available on Canvas ▪ Due Wed, Oct. 14, 11:59pm ET
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
3
Carnegie Mellon
After this lecture
You will be able to:
▪ Describe the steps to debug complex code failures
▪ Identify ways to manage the complexity when programming ▪ State guidelines for communicating the intention of the code
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
4
Carnegie Mellon
Outline
Debugging
▪ Defects and Failures
▪ Scientific Debugging ▪ Tools
Design
▪ Managing complexity
▪ Communication ▪ Naming
▪ Comments
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
5
Carnegie Mellon
Defects and Infections
1. The programmer creates a defect 2. The defect causes an infection
3. The infection propagates
4. The infection causes a failure
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
6
Carnegie Mellon
Curse of Debugging
Not every defect causes a failure!
Testing can only show the presence of errors – not their absence. (Dijkstra 1972)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
7
Carnegie Mellon
Defects to Failures
Code with defects will introduce erroneous or “infected” state
▪ Correct code may propagate this state
▪ Eventually an erroneous state is observed
Some executions will not trigger the defect
▪ Others will not propagate “infected” state
Debugging sifts through
the code to find the defect
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
8
Carnegie Mellon
Explicit Debugging
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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
9
Carnegie Mellon
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
Failing Runs
Code
Problem Description
Other Runs
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
10
Hypothesis
Carnegie Mellon
Scientific Debugging
▪ 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?
Prediction
▪ Does the data refute the hypothesis?
▪ Refine the hypothesis based on the new inputs
Observation & Conclusion
Hypothesis
Experiment
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
11
Carnegie Mellon
Scientific Debugging
A set of experiments has confirmed the hypothesis ▪ This is the diagnosis of the defect
Develop a fix for the defect
Run experiments to confirm the fix
▪ Otherwise, how do you know that it is fixed?
Conclusion Diagnosis Fix Confirm
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
12
Carnegie Mellon
Code with a Bug
int fib(int n)
{
int f, f0 = 1, f1 = 1; while (n > 1) {
n = n – 1;
f = f0 + f1;
f0 = f1;
f1 = f;
}
return f; }
int main(..) {
..
for (i = 9; i > 0; i–) printf(“fib(%d)=%d\n”,
i, fib(i));
$ gcc -o fib fib.c fib(9)=55 fib(8)=34
…
fib(2)=2
fib(1)=134513905
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
13
A defect has caused a failure.
Carnegie Mellon
Constructing a Hypothesis
Specification defined the first Fibonacci number as 1 ▪ We have observed working runs (e.g., fib(2))
▪ We have observed a failing run ▪ We then read the code
fib(1) failed
Code
for (i = 9; …) while (n > 1) { int f;
// Hypothesis
Hypothesis
Result depends on order of calls Loop check is incorrect
f is uninitialized
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
14
Carnegie Mellon
Prediction
Propose a new condition or conditions
▪ What will logically happen if your hypothesis is correct? ▪ What data can be
fib(1) failed // Hypothesis ▪ // Result depends on order of calls
▪ If fib(1) is called first, it will return correctly. ▪ // Loop check is incorrect
▪ Change to n >= 1 and run again. ▪ // f is uninitialized
▪ Change to int f = 1;
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
15
Carnegie Mellon
Experiment
Identical to the conditions of a prior run
▪ Except with one condition changed Conditions
▪ Program input, using a debugger, altering the code
fib(1) failed // Hypothesis
▪ If fib(1) is called first, it will return correctly.
▪ Fails.
▪ Change to n >= 1
▪ fib(1)=2
▪ fib(0)=…
▪ Change to int f = 1;
▪ Works. Sometimes a prediction can be a fix. Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
16
Carnegie Mellon
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.
▪ 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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
17
Carnegie Mellon
Debugging Tools
Observing program state can require a variety of tools ▪ Debugger (e.g., gdb)
▪ What state is in local / global variables (if known) ▪ What path through the program was taken
▪ Valgrind
▪ Does execution depend on uninitialized variables ▪ Are memory accesses ever out-of-bounds
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
18
Carnegie Mellon
Diagnosis
A scientific hypothesis that explains current observations and makes future predictions becomes a theory
▪ We’ll call this a diagnosis
Use the diagnosis to develop a fix for the defect ▪ Avoid “post hoc, ergo propter hoc” fallacy
▪ Latin for: “After this, therefore because of this” ▪ Or correlation does not imply causation
Understand why the defect and fix relate
Once there was a program that only worked on Wednesday…
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
19
Carnegie Mellon
Fix and Confirm
Confirm that the fix resolves the failure
If you fix multiple perceived defects, which fix was for the failure?
▪ Be systematic
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
20
Carnegie Mellon
Learn
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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
21
Carnegie Mellon
Quick and Dirty
Not every problem needs scientific debugging ▪ Set a time limit: (for example)
▪ 0 – 10 minutes – Informal Debugging
▪ 10 – 60 minutes – Scientific Debugging
▪ > 60 minutes – Take a break / Ask for help
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
22
Carnegie Mellon
Code Smells
Common ways in which code is likely to have bugs, either already or in the future
Use of uninitialized variables Unused values
Unreachable code
Duplicated code
Bloated functions/methods Memory leaks
Interface misuse
Null pointers
Etc
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
23
Carnegie Mellon
Quiz Time!
Check out:
https://canvas.cmu.edu/courses/10968
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
24
Carnegie Mellon
Outline
Debugging
▪ Defects and Failures
▪ Scientific Debugging ▪ Tools
Design
▪ Managing complexity
▪ Communication ▪ Naming
▪ Comments
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
25
Carnegie Mellon
Design
A good design needs to achieve many things: ▪ Performance
▪ Availability
▪ Modifiability, portability
▪ Scalability
▪ Security
▪ Testability
▪ Usability
▪ Cost to build, cost to operate
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
26
Carnegie Mellon
Design
Good Design does:
Complexity Management & Communication
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
27
Carnegie Mellon
Complexity
There are well known limits to how much complexity a human can manage easily.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
28
Carnegie Mellon
Complexity Management
However, patterns can be very helpful…
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
29
Carnegie Mellon
Complexity Management
Many techniques have been developed to help manage complexity:
Separation of concerns Modularity
Reusability
Extensibility
DRY
Abstraction
Information Hiding …
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
30
Carnegie Mellon
Managing Complexity
Given the many ways to manage complexity ▪ Design code to be testable
▪ Try to reuse testable chunks
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
31
Carnegie Mellon
Complexity Example
Split a cache access into three+ testable components ▪ State all of the steps that a cache access requires
Convert address into tag, set index, block offset
Look up the set using the set index
Check if the tag matches any line in the set If so, hit
If not a match, miss, then
Find the LRU block
Evict the LRU block
Read in the new line from memory
Update LRU
Update dirty if the access was a store
▪ Which steps depend on the operation being a load or a store? Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
32
Carnegie Mellon
Complexity Example
Split a cache access into three+ testable components ▪ State all of the steps that a cache access requires
Convert address into tag, set index, block offset
Look up the set using the set index
Check if the tag matches any line in the set If so, hit
If not a match, miss, then
Find the LRU block
Evict the LRU block
Read in the new line from memory
Update LRU
Update dirty if the access was a store
▪ Which steps depend on the operation being a load or a store? Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
33
Carnegie Mellon
Designs need to be testable
Testable design
▪ Testing versus Contracts
▪ These are complementary techniques
Testing and Contracts are
▪ Acts of design more than verification ▪ Acts of documentation
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
34
Carnegie Mellon
Testing Example
For your cache simulator, you can write your own traces ▪ Write a trace to test for a cache hit
L 50, 1 L 50, 1
▪ Write a trace to test dirty bytes in cache S 100, 1
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
35
Carnegie Mellon
Communication
When writing code, the author is communicating with: The machine
Other developers of the system
Code reviewers
Their future self
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
36
Carnegie Mellon
Communication
There are many techniques that have been developed around code communication:
Tests
Naming
Comments
Commit Messages Code Review
Design Patterns
…
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
37
Carnegie Mellon
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
38
Naming
Carnegie Mellon
Avoid deliberately meaningless names:
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
39
Carnegie Mellon
Naming is understanding
“If you don’t know what a thing should be called, you cannot know what it is.
If you don’t know what it is, you cannot sit down and write the code.” – Sam Gardiner
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
40
Carnegie Mellon
Better naming practices
1. Start with meaning and intention
2. Use words with precise meanings (avoid “data”, “info”, “perform”)
3. Prefer fewer words in names
4. Avoid abbreviations in names
5. Use code review to improve names
6. Read the code out loud to check that it sounds okay
7. Actually rename things
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
41
Carnegie Mellon
Naming guidelines – Use dictionary words
Only use dictionary words and abbreviations that appear in a dictionary.
▪ For example: FileCpy -> FileCopy
▪ Avoid vague abbreviations such as acc, mod, auth, etc..
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
42
Carnegie Mellon
Avoid using single-letter names Single letters are unsearchable
▪ Give no hints as to the variable’s usage Exceptions are loop counters
▪ Especially if you know why i, j, etc were originally used
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
43
Carnegie Mellon
Limit name character length
“Good naming limits individual name length, and reduces the need for specialized vocabulary” – Philip Relf
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
44
Carnegie Mellon
Limit name word count
Keep names to a four word maximum
Limit names to the number of words that people can read at a glance.
Which of each pair do you prefer? a1) arraysOfSetsOfLinesOfBlocks
a2) cache
b1) evictedData
b2) evictedDataBytes
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
45
Carnegie Mellon
Describe Meaning Use descriptive names.
Avoid names with no meaning: a, foo, blah, tmp, etc
There are reasonable exceptions:
void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
46
Carnegie Mellon
Use a large vocabulary Be more specific when possible:
▪ Person -> Employee
What is size in this binaryTree?
struct binaryTree {
int size;
…
};
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
47
Carnegie Mellon
Use problem domain terms
Use the correct term in the problem domain’s language.
▪ Hint: as a student, consider the terms in the assignment In cachelab, consider the following:
line element
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
48
Carnegie Mellon
Use opposites precisely
Consistently use opposites in standard pairs
▪ first/end -> first/last
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
49
Carnegie Mellon
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
50
Comments
Carnegie Mellon
Don’t Comments
▪ Don’t say what the code does
▪ because the code already says that ▪ Don’t explain awkward logic
▪ improve the code to make it clear ▪ Don’t add too many comments
▪ it’s messy, and they get out of date
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
51
Carnegie Mellon
Awkward Code
Imagine someone (TA, employer, etc) has to read your code
▪ Would you rather rewrite or comment the following?
(*(void **)((*(void **)(bp)) + DSIZE)) = (*(void **)(bp + DSIZE));
▪ How about? bp->prev->next = bp->next;
▪ Both lines update program state in the same way.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
52
Carnegie Mellon
Do Comments
Answer the question: why the code exists
When should I use this code?
When shouldn’t I use it?
What are the alternatives to this code?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
53
Carnegie Mellon
Why does this exist?
Explain why a magic number is what it is.
// Each address is 64-bit, which is 16 + 1 hex characters const int MAX_ADDRESS_LENGTH = 17;
When should this code be used? Is there an alternative?
unsigned power2(unsigned base, unsigned expo){
unsigned i;
unsigned result = 1; for(i=0;i
▪ The commit messages are your record of your work ▪ Communicating to your future self
▪ Describe in one line what you did
“Parses command line arguments”
“fix bug in unique tests, race condition not solved” “seg list finished, performance is …”
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
58
Carnegie Mellon
Summary
Programs have defects
▪ Be systematic about finding them
Programs are more complex than humans can manage
▪ Write code to be manageable
Programming is not solitary, even if you are communicating with a grader or a future self
▪ Be understandable in your communication
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
59
Carnegie Mellon
Acknowledgements
Some debugging content derived from:
▪ http://www.whyprogramsfail.com/slides.php
Some code examples for design are based on:
▪ “The Art of Readable Code”. Boswell and Foucher. 2011. Lecture originally written by
▪ Michael Hilton and Brian Railing
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
60