Code Tuning Strategies and Techniques

Publish in

Documents

5 views

Please download to get full document.

View again

of 45
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Code Tuning Strategies and Techniques. CS524 – Software Engineering Azusa Pacific University Dr. Sheldon X. Liang. Mike Rickman. Code Tuning Strategies and Techniques. Overview Performance and Code Tuning Introduction to Code Tuning Common Sources of Inefficiency Measurement Iteration
Transcript
Code Tuning Strategies and TechniquesCS524 – Software EngineeringAzusa Pacific UniversityDr. Sheldon X. LiangMike RickmanCode Tuning Strategies and Techniques
  • Overview
  • Performance and Code Tuning
  • Introduction to Code Tuning
  • Common Sources of Inefficiency
  • Measurement
  • Iteration
  • Code-Tuning Techniques
  • Checklist & Summary
  • Performance Overview
  • “More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason— including blind stupidity” —W. A. Wulf
  • Users more interested in program throughput than raw performance.
  • Clean, usable user interface
  • Robust software
  • Performance and Code Tuning
  • When efficiency is chosen as priority, consider the following:
  • Program requirements
  • Are the requirements stating performance realistic?
  • Analyze performance level versus cost.
  • Program design
  • Modular system design provides easier tuning
  • Set goals for individual components
  • Use of sub-systems can improve performance
  • Class and routine design
  • Choice of data types
  • Choice of algorithms
  • Performance and Code Tuning cont.
  • Operating-system interactions
  • Inefficient operating system routines
  • Compiler generated system calls
  • Code compilation
  • Good compilers optimize code speed
  • Hardware
  • New hardware may be cheaper than optimizing code
  • Code tuning (Lastly)
  • Practice of modifying correct code in ways that make it run more efficiently
  • Introduction to Code Tuning
  • Code Tunings Appeal
  • It’s fun, it’s cool, and it makes me look smart
  • Pareto Principle (80/20 Rule)
  • Know what to tune
  • Go after the big problems and ignore the little ones
  • Measure Twice – Cut once
  • Measure performance to know what needs to be improved
  • Introduction to Code Tuning
  • More lines of code = less efficient - FALSE
  • You should optimize as you go – FALSE
  • Make it work correctly first
  • What do you want to tune for?
  • Code Size versus Speed
  • Use a worker thread
  • The appearance of performance
  • Introduction to Code Tuning
  • When to tune
  • Jackson's Rules of Optimization: Rule 1. Don't do it. Rule 2 (for experts only). Don't do it yet—that is, not until you have a perfectly clear and unoptimized solution. —M. A. Jackson
  • Use compiler optimization
  • Write clear code
  • Let the compiler to the optimizing
  • Common Sources of Inefficiency
  • Input / Output Operations
  • In memory operation much faster than disk access
  • Organize and minimize I/O operations
  • Paging
  • Operation that causes the operating system to swap pages of memory is much slower than an operation that works on only one page of memory
  • for ( column = 0; column < MAX_COLUMNS; column++ ) { for ( row = 0; row < MAX_ROWS; row++ ) { table[ row ][ column ] = BlankTableElement(); }} for ( row = 0; row < MAX_ROWS; row++ ) { for ( column = 0; column < MAX_COLUMNS; column++ ) { table[ row ][ column ] = BlankTableElement(); }} Common Sources of Inefficiency
  • System calls
  • Calls to system routines are often expensive.
  • Context Switch
  • Possible Solutions
  • Write your own services.
  • Avoid going to the system.
  • Work with the system vendor to make the call faster.
  • Interpreted languages
  • Interpreted languages exact significant performance penalties
  • If performance matters, don’t use them
  • Measurement
  • Measure your code to find the hot spots
  • You don’t know if or how much your improving if you don’t measure
  • Measurement needs to be precise
  • QueryPerformanceCounter – Windows
  • Only measure the code your tuning
  • Iteration
  • Iteration
  • Multiple techniques may be necessary
  • Cumulative effect of tuning
  • Code-Tuning Techniques
  • Logic
  • Stop Testing When You Know the Answer
  • negativeInputFound = false;for ( i = 0; i < count; i++ ) { if ( input[ i ] < 0 ) { negativeInputFound = true; break; }}
  • Consider order of evaluation
  • if ( 5 < x ) and ( x < 10 ) then ...
  • Code-Tuning Techniques
  • Order Tests by Frequency
  • Arrange tests so that the one that's fastest and most likely to be true is performed first
  • Select inputCharacter Case "A" To "Z", "a" To "z“ ProcessAlpha( inputCharacter ) Case " “ ProcessSpace( inputCharacter ) Case ",", ".", ":", ";", "!", "?“ ProcessPunctuation( inputCharacter ) Case "0" To "9“ ProcessDigit( inputCharacter ) Case "+", "=" ProcessMathSymbol( inputCharacter ) Case Else ProcessError( inputCharacter )End Select Code-Tuning Techniques
  • Compare Performance of Similar Logic Structures
  • Test from case statement versus if-then-else logic.
  • This example illustrates the difficulty of performing any sort of "rule of thumb" to code tuning
  • There is simply no reliable substitute for measuring results.
  • Code-Tuning Techniques
  • Substitute Table Lookups for Complicated Expressions
  • A table lookup might be quicker than traversing a complicated chain of logic.
  • The point of a complicated chain is usually to categorize something and then to take an action based on its category.
  • Suppose you want to assign a category number to something based on which of three groups— Groups A, B, and C—it falls into:
  • Code-Tuning Techniques
  • Substitute Table Lookups for Complicated Expressions
  • if ( ( a && !c ) || ( a && b && c ) ) { category = 1;}else if ( ( b && !a ) || ( a && c && !b ) ) { category = 2;}else if ( c && !a && !b ) { category = 3;}else { category = 0;}Code-Tuning Techniques
  • Substitute Table Lookups for Complicated Expressions
  • // define categoryTable static int categoryTable[ 2 ][ 2 ][ 2 ] = { <-- 1 // !b!c !bc b!c bc 0, 3, 2, 2, // !a 1, 2, 1, 1 // a }; ... category = categoryTable[ a ][ b ][ c ];
  • Although the definition of the table is hard to read, if it's well documented it won't be any harder to read than the code for the complicated chain of logic was.
  • If the definition changes, the table will be much easier to maintain than the earlier logic would have been. Here are the performance results:
  • Code-Tuning Techniques
  • Use Lazy Evaluation
  • Program contains a table of 5000 values
  • Generates the whole table at startup time, and then uses it as the program executes.
  • If the program uses only a small percentage of the entries in the table, it might make more sense to compute them as they're needed rather than all at once.
  • Code-Tuning Techniques
  • Loops
  • Unswitching
  • EX1 tests sumType every iteration.
  • for ( i = 0; i < count; i++ ) { if ( sumType == SUMTYPE_NET ) { netSum = netSum + amount[ i ]; } else { grossSum = grossSum + amount[ i ]; } }
  • EX2 only tests sumType once.
  • if ( sumType == SUMTYPE_NET ) { for ( i = 0; i < count; i++ ) { netSum = netSum + amount[ i ]; } } else { for ( i = 0; i < count; i++ ) { grossSum = grossSum + amount[ i ]; } } Code-Tuning Techniques
  • Loops
  • Jamming
  • Jamming is the result of combining two loops that operate on the same set of elements
  • For i = 0 to employeeCount – 1
  • employeeName( i ) = “”
  • Next
  • For i = 0 to employeeCount – 1
  • employeeEarnings( i ) = 0
  • next
  • For i = 0 to employeeCount – 1
  • employeeName( i ) = “”
  • employeeEarnings( i ) = 0
  • Next
  • Code-Tuning Techniques
  • Loops
  • Unrolling
  • The goal of loop unrolling is to reduce the amount of loop housekeeping
  • i = 0;
  • while ( i < count ) {
  • a[ i ] = i; i = i + 1;
  • }
  • i = 0;while ( i < count - 1 ) { a[ i ] = i; a[ i + 1 ] = i + 1; i = i + 2;}// These lines pick up the case that might fall through the cracks if the loop went by twos instead of by ones.if ( i == count ) { a[ count - 1 ] = count - 1;}Code-Tuning Techniques
  • Loops
  • Minimizing the Work Inside Loops
  • One key to writing effective loops is to minimize the work done inside a loop
  • for ( i = 0; i < rateCount; i++ ) { netRate[ i ] = baseRate[ i ] * rates->discounts->factors->net;}quantityDiscount = rates->discounts->factors->net; for ( i = 0; i < rateCount; i++ ) { netRate[ i ] = baseRate[ i ] * quantityDiscount;}Code-Tuning Techniques
  • Loops
  • Sentinel Values
  • Use of a sentinel is the search loop that checks both whether it has found the value it's seeking and whether it has run out of values.
  • found = FALSE; i = 0; while ( ( !found ) && ( i < count ) ) { if ( item[ i ] == testValue ) { found = TRUE; } else { i++; } } if ( found ) { ... Code-Tuning Techniques
  • Loops
  • Sentinel Values
  • In this example, a sentinel value is a value that you put just past the end of the search range that's guaranteed to terminate the search.
  • // set sentinel value, preserving the original valueinitialValue = item[ count ]; item[ count ] = testValue; i = 0; while ( item[ i ] != testValue ) { i++;} // check if value was found if ( i < count ) { ... Remember to allow space for the sentinel value at the end of the array Code-Tuning Techniques
  • Loops
  • Putting the Busiest Loop on the Inside
  • When you have nested loops, think about which loop you want on the outside and which you want on the inside
  • for ( column = 0; column < 100; column++ ) { for ( row = 0; row < 5; row++ ) { sum = sum + table[ row ][ column ]; }}
  • By merely switching the inner and outer loops, you can change the total number of iterations from 600 to 505.
  • Code-Tuning Techniques
  • Loops
  • Strength Reduction
  • Reducing strength means replacing an expensive operation such as multiplication with a cheaper operation such as addition
  • For i = 0 to saleCount – 1 commission( i ) = (i + 1) * revenue * baseCommission * discountNextincrementalCommission = revenue * baseCommission * discountcumulativeCommission = incrementalCommissionFor i = 0 to saleCount – 1 commission( i ) = cumulativeCommission cumulativeCommission = cumulativeCommission + incrementalCommissionNext Code-Tuning Techniques
  • Data Transformation
  • Changes in data types can be a powerful aid in reducing program size and improving execution speed
  • Integer addition and multiplication tend to be faster than floating point.
  • Changing a loop index from a floating point to an integer, for example, can save time
  • Dim x As SingleFor x = 0 to 99 a( x ) = 0Next Code-Tuning Techniques
  • Use the Fewest Array Dimensions Possible
  • Conventional wisdom maintains that multiple dimensions on arrays are expensive.
  • If you can structure your data so that it's in a one-dimensional array rather than a two-dimensional or three-dimensional array, you might be able to save some time
  • Code-Tuning Techniques
  • Minimize Array References
  • Advantageous to minimize array accesses
  • The reference to discount[ discountType ] doesn't change when discountLevel changes in the inner loop
  • for ( discountType = 0; discountType < typeCount; discountType++ ) { for ( discountLevel = 0; discountLevel < levelCount; discountLevel++ ) { rate[ discountLevel ] = rate[ discountLevel ] * discount[ discountType ]; }} Code-Tuning Techniques
  • Minimize Array References
  • Move discount [discountType] out of the inner loop so that you'll have only one array access per execution of the outer loop
  • for ( discountType = 0; discountType < typeCount; discountType++ ) { thisDiscount = discount[ discountType ]; for ( discountLevel = 0; discountLevel < levelCount; discountLevel++ ) { rate[ discountLevel ] = rate[ discountLevel ] * thisDiscount; }} Code-Tuning Techniques
  • Use Supplementary Indexes
  • Using a supplementary index means adding related data that makes accessing a data type more efficient
  • Example
  • In C, strings are terminated by a byte that's set to 0
  • In Visual Basic string format, a length byte hidden at the beginning of each string indicates how long the string is
  • Which is faster at determining a string length?
  • Use this concept for determining length of an variable-length data
  • Code-Tuning Techniques
  • Use Caching
  • Caching means saving a few values in such a way that you can retrieve the most commonly used values more easily than the less commonly used values
  • You can cache the results of time-consuming computations too
  • public double Hypotenuse( double sideA, double sideB ) { // check to see if the triangle is already in the cache if ( ( sideA == cachedSideA ) && ( sideB == cachedSideB ) ) { return cachedHypotenuse; } // compute new hypotenuse and cache it cachedHypotenuse = Math.sqrt( ( sideA * sideA ) + ( sideB * sideB ) ); cachedSideA = sideA; cachedSideB = sideB; return cachedHypotenuse; } Code-Tuning Techniques
  • Expressions
  • Much of the work in a program is done inside mathematical or logical expressions.
  • Complicated expressions tend to be expensive
  • Exploit Algebraic Identities
  • Use algebraic identities to replace costly operations with cheaper ones.
  • The following expressions are logically equivalent:
  • not a and not bnot (a or b) Code-Tuning Techniques
  • Use Strength Reduction
  • Strength reduction means replacing an expensive operation with a cheaper one
  • Replace multiplication with addition.
  • Replace exponentiation with multiplication.
  • Replace longlong integers with longs or ints
  • Replace floating-point numbers with fixed-point numbers or integers.
  • Replace double-precision floating points with single-precision numbers.
  • Replace integer multiplication-by-two and division-by-two with shift operations.
  • Code-Tuning Techniques
  • Initialize at Compile Time
  • If you're using a named constant or a magic number in a routine call, that's a clue that you could pre-compute the number
  • unsigned int Log2( unsigned int x ) { return (unsigned int) ( log( x ) / log( 2 ) ); }
  • Replace log(2) with a constant
  • Code-Tuning Techniques
  • Use the Correct Type of Constants
  • Use named constants and literals that are the same type as the variables they're assigned to.
  • A good compiler does the type conversion at compile time
  • But don’t take the chance
  • Code-Tuning Techniques
  • Precompute Results
  • A common low-level design decision is the choice of whether to compute results on the fly or compute them once and look them up as needed.
  • Code Size versus Memory Use
  • Compute a lookup table once when program execution begins, using it every time thereafter
  • Store results in a data file or embed them in a program.
  • Code-Tuning Techniques
  • Eliminate Common Subexpressions
  • If an expression is repeated several times, assign it to a variable rather than re-computing in several places.
  • payment = loanAmount / (( 1.0 - Math.pow( 1.0 + ( interestRate / 12.0 ), -months ) ) / ( interestRate / 12.0 ) );
  • interestRate / 12.0 could be a variable
  • Code-Tuning Techniques
  • Routines
  • Good routine decomposition is best for well tuned code
  • Small, well-defined routines save space
  • Take the place of doing jobs separately in multiple places
  • You can re-factor code in one routine and thus improve every routine that calls it
  • Small routines are relatively easy to rewrite in a low-level language
  • Code-Tuning Techniques
  • Routines
  • Rewrite Routines Inline
  • Code executes “in-place” versus calling a routine
  • Less advantage with newer compilers and computers
  • Recoding in a Low-Level Language
  • If you're coding in C++, the low-level language might be assembler.
  • If you're coding in Python, the low-level language might be C.
  • Code-Tuning Techniques
  • Checklist
  • Improve Both Speed and Size
  • Substitute table lookups for complicated logic.
  • Jam loops.
  • Use integer instead of floating-point variables.
  • Initialize data at compile time.
  • Use constants of the correct type.
  • Precompute results.
  • Eliminate common sub-expressions.
  • Translate key routines to a low-level language.
  • Code-Tuning Techniques
  • Checklist
  • Improve Speed Only
  • Stop testing when you know the answer.
  • Order tests in case statements and if-then-else chains by frequency.
  • Compare performance of similar logic structures.
  • Use lazy evaluation.
  • Unswitch loops that contain if tests.
  • Unroll loops.
  • Minimize work performed inside loops.
  • Use sentinels in search loops.
  • Put the busiest loop on the inside of nested loops.
  • Code-Tuning Techniques
  • Checklist
  • Improve Speed Only (cont.)
  • Reduce the strength of operations performed inside loops.
  • Change multiple-dimension arrays to a single dimension.
  • Minimize array references.
  • Augment data types with indexes.
  • Cache frequently used values.
  • Exploit algebraic identities.
  • Reduce strength in logical and mathematical expressions.
  • Be wary of system routines.
  • Rewrite routines inline.
  • Summary of the Approach to Code Tuning
  • Develop the software by using well-designed code that's easy to understand and modify.
  • If performance is poor,
  • Save a working version of the code so that you can get back to the "last known good state."
  • Measure the system to find hot spots.
  • Determine whether the weak performance comes from inadequate design, data types, or algorithms and whether code tuning is appropriate. If code tuning isn't appropriate, go back to step 1.
  • Tune the bottleneck identified in step (c).
  • Measure each improvement one at a time.
  • If an improvement doesn't improve the code, revert to the code saved in step (a). (Typically, more than half the attempted tunings will produce only a negligible improvement in performance or degrade performance.)
  • Repeat from step 2.
  • Related Search
    Related Documents
    View more...
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks