'&$%CSE 303:Concepts and Tools for Software DevelopmentDan GrossmanSpring 2007Lecture 18— Specifications; Profiling (gprof)Dan Grossman CSE303 Spring 2007, Lecture 18 1'&$%Where are We• Talked about testing, but not what (partially) correct was• Then another useful tool: a run-time profiler– In particular, gprofDan Grossman CSE303 Spring 2007, Lecture 18 2'&$%Specifying Code?We m ade a big assumption, that we know what the code is supposedto do!Oftentimes, a complete specification is at least as difficult as writingthe code. But:• It’s still worth thinking about.• Partial specifications are better than none.• Checking specificatins (at compile-time and/or run-time) is greatfor finding bugs early and “assigning blame”.Dan Grossman CSE303 Spring 2007, Lecture 18 3'&$%Full SpecificationOften tractable for very simple stuff: “Take an int x and return 0 iffthere exists ints y and z such that y ∗ z == x (where x, y, z > 0and y, z < x).”What about sorting a doubly-linked list?• Precondition: Can input be NULL? Can any prev and next fieldsbe NULL? Must it be a cycle or is “balloon” okay?• Postcondition: Sorted (how to spe cify?) – and a permutation ofthe input (no missing or new e leme nts).And there’s often more than “pre” and “post” – time/space overhead,other effects (such as printing), things that may happen in parallel.Specs should guide programming and testing! Should be declarative(“what” not “how”) to dec ouple implementation and use.Dan Grossman CSE303 Spring 2007, Lecture 18 4'&$%Pre/post and invariantPre- and post-conditions apply to any statement, not just functions• What is assumed before and guaranteed afterBecause a loop “calls itself” its body’s post-condition better imply theloop’s precondition.• A loop invariantExample: find max (next slide)Dan Grossman CSE303 Spring 2007, Lecture 18 5'&$%Pre/post and invariant// pre: arr has length len; len >= 1int max = arr[0];int i=1;while(i<len) {if(arr[i] > max)max = arr[i];++i;}// post: max >= all arr elementsloop-invariant: For all j<i, max>=arr[j].• to show it holds after the loop body, must assume it holds beforeloop body• loop-invariant plus !(i<len) after body, enough to show postDan Grossman CSE303 Spring 2007, Lecture 18 6'&$%Partial SpecificationsThe difficulty of full specs need not mean abandon all hope.Useful partial specs:• Can args be NULL?• Can args alias?• Are stack pointers allowed? Dangling pointers?• Are cycles in data structures allowed?• What is the minimum/maximum length of an array?• ...Guides callers, callees, and testers.Dan Grossman CSE303 Spring 2007, Lecture 18 7'&$%Beyond testingSpecs are useful for more than “things to think about while coding”and testing and comments.Sometimes you can check them dynamically, e.g., with assertions (allexamples true for C and Java)• Easy: argument not NULL• Harder but doable: list not cyclic• Impossible: Does the caller have other pointers to this object?Dan Grossman CSE303 Spring 2007, Lecture 18 8'&$%assert in CIn C:#include <assert.h>void f(int *x, int*y) {assert(x!=NULL);assert(x!=y);...}• A macro; ignore argument if NDEBUG defined at time of #include,else evaluate and exit with file/line number if zero.Dan Grossman CSE303 Spring 2007, Lecture 18 9'&$%assert in JavaIn Java (as of version 1.4):void f(Foo x, Foo y) {assert x != null;assert x != y : "args to f should not be pointer-equal";}• By default, ignored.• At program-start, use c omm and-line options to specify whichpackages’ assertions are enabled.Dan Grossman CSE303 Spring 2007, Lecture 18 10'&$%assert styleMany oversimply say “always” check everything you can. But:• Often not on “private” functions (caller already checked)• Unnecessary if checked statically“Disabled” in released code be cause:• executing them takes time• failures are not fixable by users anyway• assertions themselves could have bugs/vulnerabilitiesOthers say:• Should leave enabled; corrupting data on real runs is worse thanwhen debuggingDan Grossman CSE303 Spring 2007, Lecture 18 11'&$%Static checkingA stronger type system or other code-analysis tool might take aprogram and ensure• Plusses: earlier detection (“coverage” without running program),faster code• Minus: Potential “false positives” (spec couldn’t ever actually beviolated, but tool thinks so)Deep CSE322 fact: Every code-analysis tool proving a non-trivial facthas either false positives (unwarranted warning) or false negatives(missed bug) or both.Deep real-world fact: That doesn’t make them unuseful.Dan Grossman CSE303 Spring 2007, Lecture 18 12'&$%ProfilersA profiler monitors and reports (performance) information about aprogram execution.They are useful for “debugging correct programs” by learning whereprograms consume mos t tim e and/or space.“90/10 rule of programs” (and often worse for new programs) – aprofiler helps you “find the 10”.But: The tool can be misused and misleading.Dan Grossman CSE303 Spring 2007, Lecture 18 13'&$%What profilers tell youDifferent profilers profile different things.gprof, a profiler for code produced by gcc is widely available andpretty typical:• Call counts: # of times each function a calls each function b– And the simpler fact: # of times a was called• Time samples: # of times the program was executing a when“the profiler woke up to check where the program was”.Neither is quite what you want (as we’ll see later), but they’resemi-easy and semi-quick to do:• Call counts: Add code to every function call to update a tableindexed by function pairs.• Time samples: Use the processor’s timer; wake up and see wherethe program is.Dan Grossman CSE303 Spring 2007, Lecture 18 14'&$%Using gprof• Compile with -pg on the right.– When you create the .o (for call counts)– When you create the executable (for time samples)• Run the program (creates (overwrites) gmon.out)• Run gprof (on gmon.out) to get human-readable results.• Read the results (takes a little getting used to).Dan Grossman CSE303 Spring 2007, Lecture 18
View Full Document
Unlocking...