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).