Software Design (CSC-223 97F)

[News] [Basics] [Syllabus] [Outlines] [Assignments] [Studies] [Examples] [Readings] [Projects] [API]

Outline of Class 29: Efficiency, Timing, and Profiling

Miscellaneous

• I won't be around tomorrow (Tuesday).
• I will be in all day Wednesday and back again Wednesday evening (7:30 to 10:00 or so).
• I'm trying to determine what topics need to be covered.
• How many of you don't know about regular expressions and `grep`?
• How many of you don't know about associative arrays?
• As in most recent outlines, there is probably too much here, and we'll cover some of these issues on Wednesday.

Yet Another "Improvement" to the Present Value Method

• To give us a little more experience with methods of improving programs (and why they sometimes fail), we're going to make one more improvement to the present value method.
• In particular, we're going to consider the possibility of using a better primitive type for our computations.

Using Integers

• It is arguable that floats and doubles are inappropriate for present value computations.
• Why? Because we don't care about more than two positions after the decimal point and because we do want complete accuracy for those positions.
• Of course, a number of criminals have made lots of money by taking advantage of fractions of a cent in computations.
• In addition, most computers can do integer computations much faster than floating point computations.
• So, what do we do? For the initial version of our solution, it's pretty simple. Each "year" we multiply by the interest + 100%, expressed as a whole number and then divide by 100 (as in "per cent").
• For this to work correctly, we need to store the initial investment in cents, rather than in dollars.
```/** Definition and preconditions as before. */
public static long presentValue(long investment, int rate, int years) {
int modified_rate = 100 + rate;	// For computation
// Each year, update the investment by the interest
for(int i = 0; i < years; ++i) {
investment = investment * modified_rate / 100;
// Note that "investment *= modified-rate / 100" won't work.
} // for
return investment;
} // presentValue
```
• Hmmm ... now we're dealing with division by 100. Is that really a good idea? Probably not, unless we can do clever bit shifting. Is there another way to do it?
• Note that this suggests that no matter how long we invest small amounts of money (e.g., 1 cent), we'll never end up with more money.
• Note also that we'll get different results than we'll get in the double computation. Which is more accurate?
• The double computation says that \$5.00 is worth \$6.719... after ten years at 3%.
• The long computation says that \$5.00 is worth \$6.66 after ten years at 3%.
• The double computation says that \$5.00 is worth \$96.093... after 100 years at 3%.
• The long computation says that \$5.00 is worth \$92.89... after 100 years at 3%.
• Would it be possible to continue the efficient exponentiation in the same way?
• Moral: Not all improvements are easy or even improvements.

Timing

• In analyzing our improvements, we need a way to time various parts of our programs.
• How should we time our functions / commands / etc.?
• We'll need to consider:
• Specificity -- can we time particular parts of our program
• Accuracy -- how correct are our numbers
• External effects -- for example, what if our program goes to sleep or blocks on input?
• We can use `/bin/time` or `/time`.
• These normally give a host of detailed information and aren't affected by programs going to sleep.
• But they give a relatively coarse-grained view of the world.
• We can use system calls to determine the current time.
• This allows us to do fairly fine-grained analyses.
• However, it also makes us subject to system effects.
• We can use a profiler to gather data. The accuracy of the profiler will determine the rest.

Programs That Time Themselves

• While it is possible to have a program time itself, it is important that you be careful in thinking about how to time a method.
• In Java, `System.currentTimeMillis()` is a relatively efficient way of getting "the number of milliseconds since (some standard date, probably January 1, 1970 G.S.T.).
• There are others, but most involve creating objects, so there's more overhead involved.
• Here's an example of how one might test a method and print out both results of the function and time the function took.
```before = System.currentTimeMillis();
System.out.println("The result of our complicated function is " +
complicateFunction(alpha,beta,gamma));
after = System.currentTimeMillis();
System.out.println("That computation took " +
(after-before) + " milliseconds.");
```
• However, this not a good strategy. Why not?

Profiling

• In addition to timing our various operations, it helps to know how many times each line (or method or ...) is executed.
• Profilers can help give this type of information.
• Using profilers normally slows down your program (because it takes time to compute the profiling information).
• Some profilers also require you to recompile with special flags set.
• Many (but not all) language implementations provide profilers.

Profiling Java

• In the JDK, you can profile a Java program with
`% java_g -prof Class`
• This saves the profiling data in a file called `java.prof`.
• You can specify where to save the profiling data using `% java_g -prof:prof-file Class`
• As with many things in the JDK, the profile format is not well documented.
• The first part of the file tells you about the methods that are called (and where they're called from). For each callee/caller pair, you'll find
• A count of the number of times the call was made.
• The callee.
• The caller.
• The total time (in milliseconds, I believe) spent on the calls.
• The last half of the file has some information about the exceptions and signals in the program, as well as the I/O (which is, in some sense, signal-based). It is less useful for our purposes.
• Mr. Schnell has installed a simple tool for viewing these results. I'll admit that I haven't figured out how to use it, but perhaps he'll give a demo.
• The information in the file doesn't give you a lot of help if you care about finer-grained detail than the method level. It also gives more information than you might care about (e.g., you might only care about your own methods).

Outlines: prev next 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

[News] [Basics] [Syllabus] [Outlines] [Assignments] [Studies] [Examples] [Readings] [Projects] [API]

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.