ONJava.com -- The Independent Source for Enterprise Java
oreilly.comSafari Books Online.Conferences.

advertisement

AddThis Social Bookmark Button

Micro-Tuning Step-by-Step
Pages: 1, 2, 3, 4

Profiling

There are a large number of commercial, shareware, and open source profilers available, including several that come with the Sun SDK (with version 1.4 I've seen -prof, -Xprof, -Xrunhprof, -Xaprof, and -Xhprof). A list of profilers is available.



I won't cover how to use any particular profiler in this article. Each profiler has its own documentation, and the Sun profilers are documented in my book, Java Performance Tuning. Ideally, you should use a profiler that can take a snapshot of the test loop itself, and not include all of the setup for the test in the profile. If you use a profiler that can't take snapshots, (e.g., the SDK profilers), you should ensure that the test loop takes significantly longer than the time to set up the test (e.g., loading the data sets), so that the profile is dominated by the test loop.

Applying a profiler to the original test shows that for Dataset 1 and Dataset 2, the largest amount of time taken by the test -- more than a third of the time -- is in creating strings in the Integer.toString() method. For Dataset 3, the largest amount of time is spent in creating exceptions, taking some two-thirds of the runtime.

In fact, the toString() calls are completely redundant since we have the integer in string format already available as the argument to the method, and we can avoid creating the exception by testing for non-digits in the string (as explained in the earlier "Dataset 3" section). Making these changes gives us the following method:

public boolean checkInteger(String testInteger)
{
  for (int i = 0; i < testInteger.length(); i++)
    if (!Character.isDigit(testInteger.charAt(i)))
      return false;
  try
  {
    Integer theInteger = new Integer(testInteger);//fails if not  a number
    return
      (testInteger != "") && //not empty
      (theInteger.intValue() > 10) && //greater than ten
      ((theInteger.intValue() >= 2) && 
           (theInteger.intValue() <= 100000)) && //2>=X<=100000
      (testInteger.charAt(0) == '3'); //first digit is 3               
  }
  catch (NumberFormatException err)
  {
    return false;
  }     
}

Re-running our test using this code produces the results listed in Table 4.

Table 4: After eliminating toString() calls

  Dataset 1 Dataset 2 Dataset 3
Baseline 100% 84.1% 540.0%
Eliminating toString() calls 51.9% 40.7% 34.7%

Comparing Table 4 with the measurements from the restructured algorithm in Table 3, we can see that most of the speedup from restructuring the algorithm actually came from eliminating the toString() calls. That is one of the advantages of profiling: the actual bottlenecks are determined, rather than having to guess at possible speedups.

Round Two

Tuning is an iterative process. You normally find one bottleneck, make changes that improve performance, test those changes, and then start again. In the last section, we independently applied three different methodologies for eliminating bottlenecks from the application. The second methodology, analyzing the algorithm, produced the best result. This is quite typical. Algorithm changes usually provide the best speedup. Unfortunately, it can be quite difficult to analyze an algorithm and determine what approach provides the same functionality and is generically faster, i.e., faster in every applicable case. Algorithm analysis can provide the best speedup, but is the most difficult tuning methodology to apply.

The first methodology we tried, examining the code for the causes of the differences in speed between two variations of test runs (which in our case was caused by different input parameters), is not as difficult as full algorithm analysis. (Note that this methodology is not restricted to analyzing speed with different data sets; you can also use it to analyze small variations in code that produce different speeds). This methodology is very useful in reducing unexpected speed variations in applications. The difficulty comes more in developing the alternative tests than in analyzing the results for the differences. Had I not tested for non-numeric strings as parameters, there would have been no useful analysis possible.

The last methodology we tried, profiling, is the easiest to use. Profiling is the "brute force" methodology. You can always turn to it in the absence of any alternative, and it almost always provides something that can be speeded up. The law of diminishing returns kicks in after a while, however, leaving you with bottlenecks that are not worth speeding up, because the potential speedup is too small for the effort required.

Our three methodologies in the last section gave us three different changes. The last, the profile-suggested changes, were completely subsumed by the changes obtained using the other two methodologies. The method resulting from algorithm analysis is almost complete on its own, as it handles most non-numeric strings efficiently. Unfortunately, it doesn't handle cases where a non-numeric string like "3xyz" is passed as a parameter, so we also need the looped digit test. (I didn't include any non-numeric strings starting with "3" in the test data, so the effect did not show up in the tests). Combining the two improvements efficiently requires that I move the first two tests before the looped digit test and, since we've now already tested the first character, the subsequent loop only needs to start at the second character of the string:

public boolean checkInteger(String testInteger)
{
  if (testInteger.equals("")) return false;
  if (testInteger.charAt(0) != '3') return false;
  for (int i = 1; i < testInteger.length(); i++)
    if (!Character.isDigit(testInteger.charAt(i)))
      return false;
  try
  {
    Integer theInteger = new Integer(testInteger);//fails if not  a number
    return
      (theInteger.intValue() > 29) &&
      (theInteger.intValue() <= 40000);
  }
  catch (NumberFormatException err)
  {
    return false;
  }     
}

Re-running our test using this code produces the results in Table 5, which summarizes all measurements to this point.

Table 5: Combining the first round tunes

  Dataset 1 Dataset 2 Dataset 3
Baseline 100% 84.1% 540.0%
With looped digit test 114.8% 66.1% 51.4%
Restructured algorithm 46.6% 39.9% 29.8%
Eliminating toString() calls 51.9% 40.7% 34.7%
Restructured algorithm with looped digit test 54.2% 41.6% 33.2%

Table 5 seems to show that we are now worse off than simply using the code that eliminated the toString() calls! But that code didn't correctly handle the empty string case, which would throw an exception. Moving the empty string case to the top of the method and using the equals() method takes us back to preferring our most recent code.

Pages: 1, 2, 3, 4

Next Pagearrow