Group:
code generation
Topic:
algorithmic complexity analysis
Topic:
code optimization
Topic:
code optimization by advice and statistics
Topic:
execution tracing
Topic:
function cost
Topic:
histogram
Topic:
program statistics
Topic:
testing testing
| |
Summary
Two statistics have been found particularly useful in measuring program performance: statement counts and procedure timings. The first, statement counts, is used for locating frequently executed code, for testing, for debugging, and for performance information. Procedure timing is used for optimization and program comparison. (cbb 5/80)
Subtopic: importance of profiling 
| Quote: system design requires 'real' implementations to test heavy loads and expansion [»birrAD4_1982]
| | Quote: every programming language processor should include a profiler; for tuning and debugging [»woolJD_1973]
| | Quote: every compiler needs a profiler for statement counts and procedure timings [»siteRL12_1978]
| | Quote: post mortem dump and execution profile are important parts of a programming system [»sattEH5_1975]
|
Subtopic: path profile
| Quote: preferential path profiling assigns compact numbers to interesting paths; indexed by array instead of hash; reduced overhead from 50% to 15% [»vaswK1_2007]
|
Subtopic: timing services
| Quote: timing services are woefully inadequate, even for computational tasks [»kernBW7_1998]
|
Subtopic: time vs. operation count
| Quote: for search, speed and character comparisons may not be related; e.g., diagram search is 386x better by comparisons and 240x to 13x better by speed [»fenwP7_2001a]
| | Quote: speed varies widely across test data, computers, compilers, and optimization level; simple measures such as comparisons may be ineffectual [»fenwP7_2001a]
| | Quote: simple algorithms often faster because easily optimized and good cache performance
| | Quote: gprof estimates child time from call frequency; inaccurate for functional programs, common design patterns in object-oriented programs, and mutual recursion [»spivJM3_2004]
|
Subtopic: counts, total time, local time
| Quote: gprof combines call graph arcs with program histogram data for elapsed time, call counts, and time per subroutine [»grahSL6_1982]
| | Quote: a profiler needs statement counts for testing and procedure times for tuning [»siteRL12_1978]
| | QuoteRef: sattEH5_1975 ;;12 gives profile of execution counts on first statement of each block and rest of block by;
| | QuoteRef: knutDE1_1971 ;;11 "profile" of execution frequency counts very useful
|
Subtopic: in situ aggregation
| Quote: DTrace's quantize() generates a power-of-two histogram, in situ; for example, frequency of write system calls by size by application [»cantB2_2006]
| | Quote: DTrace aggregates data at the source by CPU; keyed by arbitrary n-tuple; periodically aggregated across CPUs [»cantB2_2006]
|
Subtopic: memory profiling
| Quote: use adaptive profiling to identify memory leaks in long running programs; sample code segments inversely to execution frequency; a leak is a stale object that is not accessed; SWAT has a low false positive rate [»chilTM10_2004]
| | Quote: memory management statistics needed to improve algorithms and memory management strategies [»riplGD3_1978]
| | Quote: use low overhead profiling to reorganize layout for a generational garbage collector; reduces cache miss by 21-42% [»chilTM10_1998]
|
Subtopic: startup profiling
| Quote: can not charge startup costs consistently; depends on dynamically loaded code [»kernBW7_1998]
|
Subtopic: embedded programs
| Quote: MicroTool measures min/max execution time and stack requirements from interrupt rates and min/max iteration counts; annotated flowchart [»elshJL1_1991]
|
Subtopic: acyclic paths
| Quote: efficiently profile intraprocedural, acyclic paths--the longest paths that do not traverse a loop's back edge [»ballT7_2000]
| | Quote: need design for testability since seldom execute most intraprocedural, acyclic paths [»ballT7_2000]
| | Quote: go/gcc--90% of execution profile from 1000 intraprocedural paths; other SPEC95 programs in 10-100 paths [»ballT7_2000]
| | Quote: log the call context for execution profiling; record the contexts (i.e., active subroutines) and the time spent in each context [»spivJM3_2004]
| | Quote: aprof has the same overhead as gprof; both about twice as slow [»spivJM3_2004]
|
Subtopic: buffer operations
| Quote: OS6 profile showed almost all execution time spent in unpacking buffers, testing contents, and storing elsewhere [»stoyJE3_1972]
|
Subtopic: frequently used sequences
| Quote: large program frequently reuse small sequences of instructions
|
Subtopic: profile-based optimization
| Quote: use execution statistics from profiler to optimize compilation of case statements [»bierKH1_1988]
| | Quote: use execution profile data to reposition code; identify chains of basic blocks and split never executed code from procedures; 8-10% faster [»pettK6_1990]
| | Quote: hardware performance monitoring improves performance for Java virtual machines [»buytD1_2008]
|
Subtopic: estimate performance
| Quote: the CADES animator uses individual holon performance estimates to evaluate overall performance [»pearDJ7_1973]
| | Quote: FORTRAN estimated execution profile of a program by a Monte_Carlo method
|
Subtopic: profile implementation
| Quote: DTrace provides safe and heterogenous dynamic instrumentation of production systems; arbitrary actions, predicates, and in situ aggregation [»cantB2_2006]
| | Quote: DTrace providers create probes via the DTrace framework; allows tracing at any level of the system, even across protection boundaries
| | Quote: JRun instruments Java code by patching its bytecode; annotated class file format with constant pool [»mossK10_2000]
| | Quote: gprof has problems with skewed times and mutual recursion; fix by gathering complete call stacks; requires walking the stack [»grahSL6_1982]
| | Quote: gprof uses call site as primary hash key and callee address as secondary key; 5-30% overhead; no planning required [»grahSL6_1982]
| | Quote: problem of profiling under time-sharing; gprof samples the program counter to infer execution time [»grahSL6_1982]
|
Subtopic: mirror of memory
| Quote: store run-time type information in a mirror of memory, 4 bits/byte; continuation bit, type, and size; two nibbles identifies an object [»logiA4_2001]
|
Subtopic: manual profiling
| Quote: if display program trace at full speed, brightly lit lines are heavily executed [»teitT6_1981]
|
Subtopic: problems with profiling
| Quote: found surprising variations between compilers on execution time for very similar programs [»parlBN3_1975]
| Quote: gprof estimates child time from call frequency; inaccurate for functional programs, common design patterns in object-oriented programs, and mutual recursion
[»spivJM3_2004]
|
Related Topics
Group: code generation (30 topics, 593 quotes)
Topic: algorithmic complexity analysis (10 items)
Topic: code optimization (54 items)
Topic: code optimization by advice and statistics (8 items)
Topic: execution tracing (42 items)
Topic: function cost (8 items)
Topic: histogram (5 items)
Topic: program statistics (27 items)
Topic: testing testing
(13 items)
|
