Week 05

Software Development Process

1/59

Reminder of how software development runs ...

• specification   (via requirements analysis)
• design   (data structures, algorithms)
• implementation   (C code)
• testing, debugging   (code analysis)
• user testing   (if has a user interface)
• performance tuning   (if required)

Credits:

• These lecture slides are prepared by Michael Thielscher.

... Software Development Process

2/59

Tools available to assist each stage ...

• specification   (english, formal languages)
• design   (your brain ... and CS knowledge)
• implementation   (editors, IDEs, compilers)
• testing   (testing frameworks, (e.g. Check))
• debugging   debuggers (e.g. gdb))
• user testing   (usability testing methods)
• performance tuning   (profilers (e.g. prof))

Testing

Testing

4/59

A systematic process of determining whether a program

• has mistakes (bugs) in it
• handles bad inputs "reasonably"

• the program specification or detailed requirements
• an executable version of the program
• sample input data and corresponding output data
  (or a tool that applies validation rules to the output)

... Testing

5/59

Testing happens at different stages in development:

• Unit tests on behaviour of components
• System tests on overall input/output behaviour
• System integration tests on interaction of components
• User acceptance tests to find out what they don't like

A useful approach for unit testing:

• start from lowest level functions   (don't call other functions)
• test each function as it is completed   (and "tick it off")
• use only tested functions in testing higher-level functions

... Testing

6/59

Testing alone cannot establish that a program is correct.

Why not?

To show that a program is correct, we need to show

• for all possible inputs, it produces the correct output

• we can only feasibly test a small subset of possible inputs

Testing increases our confidence that the program is ok.

Well-chosen tests significantly increase our confidence.

Exercise: Testing a function

7/59

Consider the notion that an array int A[N] is ordered:

ordered(A[N]):  forall i:1..N-1,  A[i] >= A[i-1]

and some code to implement this test

ordered = 1; // assume that it *is* ordered
for (i = 1; i < N; i++) {
    if (A[i] >= A[i-1])
        /* ok ... still ordered */;
    else
        ordered = 0; // found counter-example
}
// ordered is set appropriately

Put this code in a function and write a driver to test it.

Print "Yes" if ordered, or print "No" otherwise.

Testing Strategy

8/59

Testing only increases our confidence that the program works.

Unfortunately, we tend to make the big assumption:

The only way to be absolutely sure that this is true:

• feed in every possible valid input value   (exhaustive testing)
• if each input produces the expected output, it's correct

• e.g. can't test all int arrays of size 100

... Testing Strategy

9/59

Realistic testing:

• determine classes/partitions of input data set
• choose representative input values from each class
• determine expected output for each input
• execute program using all representative inputs

• we have increased our confidence that the program works OK
• but we have not demonstrated that the program is correct

Developing Test Cases

10/59

Examples:

... Developing Test Cases

11/59

Years of (painful) experience have yielded some common bugs:

• iterating one time too many or one time too few through a loop
• using < rather than <=, or vice versa
• forgetting to handle the null/empty/zero case
• assuming that other parts of the program supply valid data
• assuming that library functions like malloc (see later) always succeed
• etc. etc. etc.

Requires you to understand the "limit points" of your program.

Making Programs Fail

12/59

Some techniques that you can use to exercise potential bugs:

• make array sizes tiny   (#define SIZE 2)
• write a special malloc that fails at random
• initialize data structures with a value other than zero
• test all possible combinations of parameter settings
• supply empty input   (empty file, no argv values)
• test on different compilers/machines/operating systems

Summary: Testing Strategies

13/59

• "Big Bang" approach
  • you write the entire program
  • then you design and run some test cases
  • generally a bad idea
• "As You Go" Testing
  • you write a small piece of code, then you test it
  • integrate it with other tested pieces and test again
  • repeat iteratively until the entire program has been constructed
• Regression Testing
  • re-run all testing after any changes to the system

Debugging

Debugging

15/59

Debugging = process of removing errors from software.

Required when observed output != expected output.

Typically ...

• not due to the software being full of errors
• is due to a small incorrect fragment of code

... Debugging

16/59

Consequences of bugs:

• compiler gives syntax/semantic error    (if you're very lucky)
• program halts with run-time error    (if you're lucky**)
• program never halts    (not lucky, but at least you know)
• program completes, but gives incorrect results    (if you're unlucky)

** but if the runtime error is due to pointer mismanagement, you're very unlucky

... Debugging

17/59

Debugging has three aspects:

• find the code that's causing the problem
• understand why it's causing the problem
• modify the code to eliminate the problem

• understanding a bug is (usually) easy once you find it
• fixing a bug is (usually) easy once you find/understand it

To fix: re-examine spec, modify code to satisfy spec.

... Debugging

18/59

The easiest bugs to find:

• the ones the compiler tells you about

• ones that are not reproducible (random)
• those involving pointers/dynamically-allocated memory

Corollary: an onlooker will find the bug quicker than you.

Debugging Strategies

19/59

The following will assist in the task of finding bugs:

• make the bug reproducible
• search for patterns in the failure
• divide and conquer (isolate the buggy region)
• write self-checking code (e.g. assert)
• write a log file (execution trace)
• draw a picture (esp. for pointer bugs)

Debuggers

20/59

Debuggers: tools to assist in finding bugs

Typically provide facilities to

• control execution of program
      (step-by-step execution, breakpoints)
• view intermediate state of program
      (values stored in data structures, control stack)

• gdb, lldb ... command-line debugger, useful for quick checks
• ddd ... visual debugger, can display dynamic data
• valgrind ... execution "harness" for pointer bugs

Exercise: Buggy Program

21/59

Spot the bugs in the following simple program:

int main(int argc, char *argv[]) {
	int i, sum;
	int a[] = {7, 4, 3};

	for (i = 1; i <= 3; i++) {
		sum += a[i];
	}
	printf(sum);
	return EXIT_SUCCESS;
}

What will we observe when it's compiled/executed?

The Debugging Process

The Debugging Process

23/59

Debugging requires a detailed understanding of program state.

The state of a program comprises:

• the location where it's current executing
• names/values of all active variables on the stack
• names/values of all data in the global/heap regions

• "at this point in the program, x==3, y==7, and z==-2"

... The Debugging Process

24/59

The real difficulty of debugging is locating the bug.

Since a bug is "code with unintended action", you need to know:

• in detail, what the code should do
• in detail, what the code actually does

The trick to effective debugging is narrowing the focus of attention.

That is, employ a search strategy that enables you to zoom in on the bug.

... The Debugging Process

25/59

When you run a buggy program, initially everything is ok.

At some point, the buggy statement is executed ...

• the program state changes from valid to incorrect
• but the program won't necessarily crash at this point

The goal: find the point at which the state becomes "corrupted"

• initially you know broadly where the problem is
• then you move to the function where the problem occurs
• the you find the precise statement with the bug

Locating the Bug

26/59

A simple search strategy for debugging is as follows:

• initially the whole program is "suspect"
• put a print statement in the middle of the suspect part of the program to display values of variables at that point
• if the values are correct, then the bug must be in the second part of the execution
• if the values are incorrect, the bug is in the first half
• now restrict your attention to just the relevant half of the program (it becomes the new "suspect part of the program")
• repeat the above steps

... Locating the Bug

27/59

At each stage you have eliminated half of the program from suspicion.

In not too many steps, you will have identified a specific buggy statement.

The problems:

• which variables to print? all? what if too many?
• how to work out where the "half-way execution point" is?

E.g.     x:int { y = x+x; } y==x2,   when intially   x==2

... Locating the Bug

28/59

A slightly smarter strategy, relying on the typical structure of programs:

• display all major data structures just after they have been initialised
  • typically requires to implement a print function for each data structure (e.g. 2d array)
• display major data structures at "strategic points" during the program's execution
• display major data structures at the end of program execution

• after the first, second, middle iterations of the main program loop
• after the keystroke that causes an interactive program to crash
• after the point where the last output from the program occurred

Examining Program State

29/59

A vital tool for debugging is a mechanism to display state.

One method: diagnostic printf statements of "suspect" variables.

Problems with this approach:

• it changes the program   (so you're not debugging quite the same thing)
• you may guess wrong about what the suspect variables are
• generally too much is printed   (e.g. printing to trace execution of a loop)

... Examining Program State

30/59

An alternative for obtaining access to program state:

• a tool that allows you to stop program execution at a certain point
• and then allows you to inspect the state (preferably selectively)

Debuggers also allow you to inspect the state of a program that has crashed due to a run-time error.

Often, this takes you straight to the point where the bug occurred.

C Program Execution

31/59

Under Unix, a C program executes either:

• to completion, producing results   (correct?)
• until the program detects an error and calls exit()
• until a run-time error halts it   (e.g. Segmentation violation)

Normal C execution environment:

... C Program Execution

32/59

C execution environment with a debugger:

Debuggers

33/59

A debugger gives control of program execution:

• normal execution   (run, cont)
• stop at a certain point   (break)
• one statement at a time   (step, next)
• examine program state   (print)

There are GUI front-ends available (e.g. xxgdb, ddd, ...).

• provide facilities such as graphical display of data structures

... Debuggers

34/59

For gdb, programs must be compiled with the gcc -g flag.

gdb takes two command line arguments:

$ gdb executable core

E.g.

$ gdb  a.out  core
$ gdb  myprog

The core argument is optional.

gdb Sessions

35/59

gdb is like a shell to control and monitor an executing C program.

Example session:

$ gcc -g -Wall -Werror -o prog prog.c
$ gdb prog
Copyright (C) 2014 Free Software Foundation, Inc...
(gdb) break 9
Breakpoint 1 at 0x100f03: file prog.c, line 9.
(gdb) run
/Users/comp1921 Starting program: ..../prog 

Breakpoint 1, main (argc=1, argv=0x7ffbc8) at prog.c:9
9               for (i = 1; i <= 3; i++ { 
(gdb) next
10              sum += a[i];
(gdb) print sum
$1 = 0
(gdb) print a[i]
$2 = 4
(gdb) print i
$3 = 1
(gdb) print a@1
$4 = {{7, 4, 3}}
(gdb) cont
...

Basic gdb Commands

36/59

quit -- quits from gdb

help [CMD] -- on-line help (gives information about CMD command)

run ARGS -- run the program

• ARGS are whatever you normally use, e.g.

  $ xyz  <  data
  

  is achieved by:

  (gdb) run  <  data
  

gdb Status Commands

37/59

where -- find which function the program was executing when it crashed.

list [LINE] -- display five lines either side of current statement.

print EXPR -- display expression values

• EXPR may use (current values of) variables.
• Special expression a@1 shows all of the array a

gdb Execution Commands

38/59

break [PROC|LINE] -- set break-point

On entry to procedure PROC (or reaching line LINE), stop execution and return control to gdb.

next -- single step (over procedures)

Execute next statement; if statement is a procedure call, execute entire procedure body.

step -- single step (into procedures)

Execute next statement; if statement is a procedure call, go to first statement in procedure body.

For more details see gdb's on-line help.

Using a Debugger

39/59

The most common time to invoke a debugger is after a run-time error.

If this produces a core file, start gdb ...

• it typically shows you the line of code causing the crash
• use where to find out who called the current function
• pay attention to parameter values in the stack
• use list to see the current function code
• display values of local variables

... Using a Debugger

40/59

Once you have an idea where the bug might be:

• set breakpoints slightly earlier in the code
• run the program again (supplying the same data)
• single-step through the suspect region of code
• check the values of suspect variables after each step

... Using a Debugger

41/59

Once you find that the value of a given variable (e.g. x) is wrong, the next step is to determine why it is wrong.

There are two possibilities:

• the statement that assigned a value to x is wrong
• the values of other variables used by that statement are wrong

if (c > 0) { x = a+b; }

If we know that

• x is wrong after this statement
• the condition and the expression correctly implement their specs

Laws of Debugging

42/59

Courtesy of Zoltan Somogyi, Melbourne University

Before you can fix it, you must be able to break it (consistently).
(non-reproducible bugs ... Heisenbugs ... are extremely difficult to deal with)

If you can't find a bug where you're looking, you're looking in the wrong place.
(taking a break and resuming the debugging task later is generally a good idea)

It takes two people to find a subtle bug, but only one of them needs to know the program.
(the second person simply asks questions to challenge the debugger's assumptions)

(In fact, sometimes the second person doesn't have to do or say anything! The process of explaining the problem is often enough to trigger a Eureka event.)

Possibly Untrue Assumptions

43/59

Debugging can be extremely frustrating when you make assumptions about the problem which turn out to be wrong.

Some things to be wary of:

• the executable comes from the source code you're reading
• the problem must be in this source file
• the problem cannot be in this source file
• code that calls a function never provides unexpected arguments
  (e.g. "this pointer will never be NULL; why would anyone pass a NULL?")
• library functions never return an error status
  (e.g. "malloc will always give the memory I ask for")

Performance Tuning

Software Development Process

45/59

Reminder of how software development runs ...

• specification   (via requirements analysis)
• design   (data structures, algorithms)
• implementation   (C code)
• testing, debugging   (code analysis)
• user testing   (if has a user interface)
• performance tuning   (if required)

Performance

46/59

Why do we care about performance?

Good performance → less hardware, happy users.

Bad performance → more hardware, unhappy users.

Generally:   performance = execution time

Other measures: memory/disk space, network traffic, disk i/o.

Execution time can be measured in two ways:

• cpu ... time your program spends in the processor
• elapsed ... wall-clock time between start and finish

... Performance

47/59

In the past, performance was a significant problem.

• much programming effort was spent on efficiency "tricks".

• execution efficiency achieved by "tweaking" code
• the understandability of the code

Knuth: "Premature optimization is the root of all evil"

Development Strategy

48/59

A pragmatic approach to efficiency:

• first, make the program simple, clear, robust and correct
• then, worry about efficiency ... if it's a problem at all

• good design is always critical
  (at design time, make sensible choice of data structures, algorithms)
• can handle efficiency at system level
  (e.g. buy a bigger machine, use compiler optimisation, ...)

... Development Strategy

49/59

Strategy for developing efficient programs:

1. Design the program well
2. Implement the program well
3. Test the program well
4. Only after you're sure it's working, measure performance
5. If (and only if) performance is inadequate, find the "hot spots"
6. Tune the code to fix these
7. Repeat measure-analyse-tune cycle until performance ok

Performance Analysis

50/59

Complexity/estimates give some idea of performance in advance.

Often, however ..

• assumptions made in estimating performance are invalid
• we overlook some frequent and/or expensive operation

Performance analysis can be:

• coarse-grained ... overview of performance characteristics
• fine-grained ... detailed description of performance

... Performance Analysis

51/59

Coarse-grained performance analysis

• devise a range of representative inputs
• measure execution time of program on each input
• can conveniently be combined with testing
  (but we only care about timing if correct result produced)

$ time ./myProg < LargeInput > /dev/null
real  0m5.064s
user  0m4.113s
sys   0m0.802s

... Performance Analysis

52/59

Decades of empirical study of program execution have shown ...

The 90/10 rule generally holds   (or 80/20 rule or ...):

Implications:

• most of the code has little impact on overall performance
• small regions of the code are bottlenecks (aka hot-spots)

Profiles

53/59

Need a method for locating hot spots (the expensive 10% of code).

An execution profile for a program is

• the total cost of performing each code block
• for one execution of the program

• a count of the number of times the block is executed
• the total execution time spent within that block

... Profiles

54/59

A profile shows how much time is spent in each code block ...

Software tools can generate profiles of program execution.

gprof: A Profiler

55/59

The gprof command displays execution profiles ...

• must compile program with the -pg flag
• executing program creates an extra gmon.out file
• gprof reads gmon.out and prints profile on stdout

Example of use:

$ gcc -pg -o xyz xyz.c
$ xyz < data > /dev/null
$ gprof xyz | less

For further usage details, man gprof.

... gprof: A Profiler

56/59

The gprof command works at the function level.

It gives a table (flat profile) containing:

• number of times each function was called
• % of total execution time spent in the function
• average execution time per call to that function
• execution time for this function and its children

It also gives a call graph, a list for each function:

• which functions called this function
• which functions were called by this function

Profile Example

57/59

Consider the following program that

• searches for words in text containing a given substring
• displays each such word once (in alphabetical order)

int main(int argc, char*argv[])
{
    char  word[MAXWORD];  // current word
    List  matches;        // list of matched words
    char  *substring;     // string to look for
    FILE  *input;         // the input file

    /* ... Check command-line args, open input file ... */

    /* Process the file - find the matching words */
    matches = NULL;
    while (getWord(input, word) != NULL) {
        if (contains(word,substring)
                 && !member(matches,word))
            matches = insert(matches,word);
    }
    printWords(matches);
    return 0;
}

... Profile Example

58/59

Flat profile for this program (xwords et data3):

  %  cumulative     self            self    total           
 time   seconds  seconds  calls  us/call  us/call  name    
 75.00     0.03     0.03  30212     0.99     0.99  getWord
 25.00     0.04     0.01  30211     0.33     0.33  contains
  0.00     0.04     0.00    489     0.00     0.00  member
  0.00     0.04     0.00    267     0.00     0.00  insert
  0.00     0.04     0.00      1     0.00 40000.00  main
  0.00     0.04     0.00      1     0.00     0.00  printWords

Note:   wc data3  →  7439 30211 188259.

... Profile Example

59/59

Call graph for the same execution (xwords et data3):

index %time   self  children    called     name
              0.00    0.04       1/1           _start [2]
[1]   100.0   0.00    0.04       1         main [1]
              0.03    0.00   30212/30212       getWord [3]
              0.01    0.00   30211/30211       contains [4]
              0.00    0.00     489/489         member [5]
              0.00    0.00     267/267         insert [6]
              0.00    0.00       1/1           printWords [7]
-----------------------------------------------
[2]   100.0   0.00    0.04                 _start [2]
              0.00    0.04       1/1           main [1]
-----------------------------------------------
              0.03    0.00   30212/30212       main [1]
[3]    75.0   0.03    0.00   30212         getWord [3]
-----------------------------------------------
              0.01    0.00   30211/30211       main [1]
[4]    25.0   0.01    0.00   30211         contains [4]
----------------------------------------------
              0.00    0.00     489/489         main [1]
[5]     0.0   0.00    0.00     489         member [5]
-----------------------------------------------
              0.00    0.00     267/267         main [1]
[6]     0.0   0.00    0.00     267         insert [6]
-----------------------------------------------
              0.00    0.00       1/1           main [1]
[7]     0.0   0.00    0.00       1         printWords [7]

Produced: 21 Aug 2017