CODE TUNINGtertertertrtryryryryrtytrytrtry

code tuning

1. Code Tuning

2. Code Tuning Code tuning is one way of improving a program’s performance. It is the practice of modifying correct code in ways that make it run more efficiently. Tuning refers to small-scale changes that affect a single class, a single routine, or, more commonly, a few lines of code. Tuning does not refer to large-scale design changes, or other higher-level means of improving performance.

3. Introduction to Code Tuning What is the appeal of code tuning? It’s not the most effective way to improve performance Program architecture, class design, and algorithm selection usually produce more dramatic improvements. Nor is it the easiest way to improve performance.

4. Introduction to Code Tuning Code tuning is appealing for several reasons It’s incredibly satisfying to take a routine that executes in 20 microseconds, tweak a few lines, and reduce the execution speed to 2 microseconds. Appealing for programmers. The problem with code tuning is that efficient code isn’t necessarily “better” code.

5. The Pareto Principle Also known as the 80/20 rule You can get 80 percent of the result with 20 percent of the effort. The principle applies to a lot of areas other than programming, but it definitely applies to program optimization. Barry Boehm reports that 20 percent of a program’s routines consume 80 percent of its execution time

6. Introduction to Code Tuning Knuth used a line-count profiler to discover this surprising relationship, and the implications for optimization are clear. You should measure the code to find the hot spots and then put your resources into optimizing the few percent that are used the most. Knuth profiled his line-count program and found that it was spending half its execution time in two loops. He changed a few lines of code and doubled the speed of the profiler in less than an hour.

7. Introduction to Code Tuning Jon Bentley describes a case in which a thousand-line program spent 80 percent of its time in a five-line square-root routine. By tripling the speed of the square root routine, he doubled the speed of the program

8. Code Tuning Here are some common misapprehensions about code tuning Reducing the lines of code in a high-level language improves the speed or size of the resulting machine code—false! Consider the following code that initializes a 10-element array: for i = 1 to 10 a[ i ] = i end for

9. Code Tuning Would you guess that these lines are faster or slower than the following 10 lines that do the same job? a[ 1 ] = 1 a[ 2 ] = 2 a[ 3 ] = 3 a[ 4 ] = 4 a[ 5 ] = 5 a[ 6 ] = 6 a[ 7 ] = 7 a[ 8 ] = 8 a[ 9 ] = 9 a[ 10 ] = 10

10. Code Tuning If you follow the old “fewer lines are faster ” belief, you’ll guess that the first code is faster because it has four fewer lines. Tests in Visual Basic and Java have shown that the second fragment is at least 60 percent faster than the first. Here are the numbers

11. Code Tuning Certain operations are probably faster or smaller than others—false! You should optimize as you go—false! One theory is that if you strive to write the fastest and smallest possible code as you write each routine, your program will be fast and small. This approach creates a forest-for-the-trees situation in which programmers ignore significant global optimizations because they’re too busy with micro-optimizations. A fast program is just as important as a correct one—false! It’s hardly ever true that programs need to be fast or small before they need to be correct

12. When to tune? Use a high-quality design. Make the program right. Make it modular and easily modifiable so that it’s easy to work on later. When it’s complete and correct, check the performance. If the program lumbers, make it fast and small. Don’t optimize until you know you need to.

13. Code-Tuning Techniques Logic Much of programming consists of manipulating logic. This technique describes how to manipulate logical expressions to your advantage. Stop Testing When You Know the Answer Suppose you have a statement like if ( x< 5 ) and ( x < 10 ) then ... Once you’ve determined that x is less than 5, you don’t need to perform the second half of the test.

14. Code-Tuning Techniques C++ Example of Not Stopping After You Know the Answer

15. Code-Tuning Techniques A better approach would be to stop scanning as soon as you find a negative value. Here are the approaches you could use to solve the problem: ● Add a break statement after the negativeInputFound = True line. ● If your language doesn’t have break , emulate a break with a goto that goes to the first statement after the loop. ● Change the for loop to a while loop and check for negativeInputFound as well as for incrementing the loop counter past iCount .

16. 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. It should be easy to drop through the normal case, and if there are inefficiencies, they should be in processing the uncommon cases. This principle applies to case statements and to chains of if-then- else s .

17. Code-Tuning Techniques Use Lazy Evaluation Idea: wait to compute until you’re sure you need the value Often, you never actually use the value! Example: your 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. Once an entry is computed, it can still be stored for future reference.

18. Code-Tuning Techniques Substitute Table Lookups for Complicated Expressions In some circumstances, a table lookup may 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

19. Code-Tuning Techniques Loops Because loops are executed many times, the hot spots in a program are often inside loops. The techniques make the loop itself faster. Un-switching Switching refers to making a decision inside a loop every time it’s executed. If the decision doesn’t change while the loop is executing, you can unswitch the loop by making the decision outside the loop. Usually this requires turning the loop inside out, putting loops inside the conditional rather than putting the conditional inside the loop. Here’s an example of a loop before unswitching:

20. Code-Tuning Techniques C++ Example of a Switched Loop In this code, the test if ( sumType == SUMTYPE_NET ) is repeated through each iteration even though it’ll be the same each time through the loop. You can rewrite the code for a speed gain this way:

21. Code-Tuning Techniques C++ Example of an Unswitched Loop

22. Code-Tuning Techniques Jamming Jamming, or “fusion,” is the result of combining two loops that operate on the same set of elements. The gain lies in cutting the loop overhead from two loops to one. For i = 0 to employeeCount - 1 employeeName ( i ) = "" Next ... For i = 0 to employeeCount - 1 employeeEarnings ( i ) = 0 Next

23. Code-Tuning Techniques When you jam loops, you find code in two loops that you can combine into one. Usually, that means the loop counters have to be the same. In this example, both loops run from to employeeCount - 1 , so you can jam them.

24. Code-Tuning Techniques Unrolling Do more work inside loop for fewer iterations for ( i =0; i <n; i ++) { a[ i ] = i ; } for ( i =0; i <(n-1); i +=2) { a[ i ] = i ; a[i+1] = i+1; } if ( i == n-1) a[n-1] = n-1;

25. Code-Tuning Techniques Minimizing Interior Work Move repeated computation outside One key to writing effective loops is to minimize the work done inside a loop. If you can evaluate a statement or part of a statement outside a loop so that only the result is used inside the loop, do so. It’s good programming practice, and, in some cases, it improves readability

26. Code-Tuning Techniques Sentinel Values When you have a loop with a compound test, you can often save time by simplifying the test. If the loop is a search loop, one way to simplify the test is to use a sentinel value, a value that you put just past the end of the search range and that’s guaranteed to terminate the search.

27. Code-Tuning Techniques each iteration of the loop tests for !found and for i < count . The purpose of the !found test is to determine when the desired element has been found. The purpose of the i < count test is to avoid running past the end of the array. Inside the loop, each value of item[] is tested individually, so the loop really has three tests for each iteration.

28. Code-Tuning Techniques

29. Code-Tuning Techniques 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. Following is an example of a nested loop that can be improved.

30. Code-Tuning Techniques Reduce overhead by calling fewer loops for (i=0; i<100; i++) // 100 for (j=0; j<10; j++ ) // 1000 dosomething ( i,j ); 1100 loop iterations for (j=0; j<10; j++ ) // 10 for (i=0; i<100; i++) // 1000 dosomething ( i,j ); 1010 loop iterations

31. Code-Tuning Techniques Strength Reduction Reducing strength means replacing an expensive operation such as multiplication with a cheaper operation such as addition Replace multiplication involving loop index by addition for (i=0; i<n; i++) a[i] = i*conversion; sum = 0; // or: a[0] = 0; for (i=0; i<n; i++) { // or: for (i=1; i<n; i++) a[i] = sum; // or: a[i] = sum += conversion; // a[i-1]+conversion; }

32. Code-Tuning Techniques Data Transformations Use Integers Rather Than Floating-Point Numbers 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. 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

33. Code-Tuning Techniques Minimize Array References In addition to minimizing accesses to doubly or triply dimensioned arrays, it’s often advantageous to minimize array accesses, period. A loop that repeatedly uses one element of an array is a good candidate for the application of this technique.

34. 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 You can use algebraic identities to replace costly operations with cheaper ones. For example, the following expressions are logically equivalent: not a and not B not (a or B) If you choose the second expression instead of the first, you can save a not operation

35. Code-Tuning Techniques Use Strength Reduction Strength reduction means replacing an expensive operation with a cheaper one. Here are some possible substitutions Replace multiplication with addition. Replace exponentiation with multiplication. Replace longlong integers with long s or int s (but watch for performance issues associated with using native-length vs. non-native–length integers) 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 .

36. Code-Tuning Techniques Be Wary of System Routines System routines are expensive and provide accuracy that’s often wasted. Typical system math routines, for example, are designed to put an astronaut on the moon within ± 2 feet of the target. If you don’t need that degree of accuracy, you don’t need to spend the time to compute it either. Precompute Results A common low-level design decision is the choice of whether to compute results on the fly or compute them once, save them, and look them up as needed. If the results are used many times, it’s often cheaper to compute them once and look them up the rest of the time.

37. Code-Tuning Techniques Eliminate Common Subexpressions If you find an expression that’s repeated several times, assign it to a variable and refer to the variable rather than re-computing the expression in several places.

38. Chapter 25 and 26