Performance and Test, Spring 2008 : Episode 7.2

Spring 2008

Description

Schedule

Resources

Lecture [test 4]: Friday, March 14, 9:00—11:00, Room 2A20(!)

Subject : Summary of testing principles covered so far. Software tools for supporting software development and testing. CVS, Ant, Debugger, Profiler, Coverage, Logging. Slides available here (after the lecture.) Code examples used can be found here (after the lecture.)

Text : Read the installation instructions from the Resources page and install the tools. If you observe problems you can get help at the lab session.

Comment : This lecture gives a summary of the principles discussed so far and describes tools for software development. The tools will be: CVS (for software version management), Ant (for automatic software building), and a coverage tool EclEmma.

Lab Session, Friday, March 28, 11:30—14:30

In this lab session you should work on the exercises below.

Exercise T.10 is meant to familiarize you with using CVS.(As you can also get CVS help from sysadm this should be perhaps not be your highest priority at the lab session)

Exercise T.12 and T.15 is meant to familiarize you with the Ant build system.

Exercise T.11 is a combined tutorial in profiling as well as understanding how asymptotic performance relates to real performance.

Exercise T.13 asks you to construct a framework for testing sorting algorithms.

Exercise T.14 asks you to implement a timing framework which can also be used in place of a profiler if TPTP is causing problems.

Any exercises leftover from previous sessions (this is the chance to catch up)

Exercise T.10 (CVS Intro)

In this exercise you will start using CVS. You should perform it while running Eclipse.

1. Login into your ITU account with ssh to ssh.itu.dk. (Or log onto the domain and go to your home directory on the server "H:".)
2. Create a new directory "cvs". This is going to be your CVS repository.
3. Switch to Eclipse. Proceed as in the lab installation instructions: Click Window->Open Perspective->Other...
   Choose CVS Repository Exploring
   Right click in the CVS repositories view and choose 'New’. Enter the following:
   
   Hostname: ssh.itu.dk
   Repository path: /import/home/username/cvs
   User: your linux username
   Password: Your linux password
   Connection: extssh
   
   Note that these setting will also allow you to access the CVS repository from home.
4. Explore the empty repository. Go to the Java perspective. Start a new java project, create a java-file (for instance Hello World, or Numbers to be used in the next exercise). Add the project and the file to the repository. Right click in the Project Explorer view and select Team->Share Project
5. Commit your file.
6. Update the project.
7. Change something in the java file.
8. Commit again.
9. Switch to the CVS Repository Exploring perspective. Browse down the HEAD-part of the tree until your java-file is opened. See that it now has version 1.2. Right-click and select Show History for the file. Double-click on the different versions in the history window and see the different version. Position the mouse on version 1.1, right-click and select CompareCurrent with 1.1 and see the differences as generated by the diff tool.
10. Go back to the Java perspective. Make a couple of revisions more and repeat the CVS Repository Exploration above until you are comfortable with the functionality.
11. Take a look in /import/home/username/cvs (H:\cvs) on the ITU server and see what files are in there.

Exercise T.11 Timing / Profiling

For this exercise make sure you have installed TPTP in Eclipse, see the lab installation instructions. If you have problems getting TPTP to work correctly either download the trial version of AppPerfect and use that for profiling or do exercise T.14 first and use the resulting timing framework instead of a profiler. Consider the java program Numbers:

1. What is the program doing?
2. What is the theoretical time complexity of layout(a) and layout2(a) expressed as O(f(n)), where n is the length of a? Which one is expected to be the most efficient?

Hint 1: When performing string concatenation with + as in r + " " + a[i] the contents of the strings r, " " and a[i] are copied to a new string. How long does copying take?
Hint 2: When using append on a StringBuilder object r, strings are put into a list structure and not copied until the contents is really required as a String as for instance in println( r ), where r.toString() is called before printing.
3. Follow the instructions on how to run TPTP and use it to measure the actual runtime for the calls to layout and layout2. Note down the runtimes. Try with other values for the size of the array a. Try for example: 1000, 2000, 5000, 7500. Write down all the runtimes. What do you observe about the difference in runtime between the two versions of layout?
4. Use the measured runtimes above and plot them in a chart against n. Determine if the measured times coincide with predictions.
5. Make an estimate of the values of the actual hidden constants in the big-O complexity of layout and layout2.

Exercise T.12 (Ant Intro)

In this exercise you should start using Ant. Do the exercise with Eclipse running.

1. Pick a project you have in Eclipse (or make a new one). It should include at least one java file to be compiled. If it is already compiled, remove the .class file from the directory or make a change in the java file and save it without recompiling.
2. Right-click on the project. Select New->File. Name the file build.xml. Click Finish. Notice that the icon now includes an ant. It is an ant build file.
3. Fill in the contents of build.xml with this build.xml example file.
4. Pick the down-arrow to the right of the green-circled right-arrow with a little box beneath. Pick Run As->Ant Build.
5. You should see the two targets being built by seeing: [javac] and [echo]. If you do not see javac your JAVA_HOME and PATH is not set correctly. If so, follow the instructions under entry "B" in the middle coloumn of this page. On my machine the right name for JAVA_HOME was c:\Program Files\Java\jdk1.5.0_06. Restart Eclipse and try again. If it still does not work, ask for assistance.
6. Rerun the ant build. This time only the Hello World target generates output. This is because Ant has determined that the .class file is up to date (because the .java file(s) has not been changed) and therefore recompilation is unnecessary.
7. Change a java-file and try again to see that the java compiler is invoked.

Exercise T.13 (Testing of Sorting Algorithms)

In this exercise we develop a little framework for testing sorting algorithms.

1. Construct a new class SortTester. Write a static method
   int[] randomArray(int n, int seed)
   for generating a pseudo-random array of length n of integers in the interval [0;9999]. The pseudo-random sequence of numbers is initialized with the seed given as second argument. A seed is used in order to be able to repeat the same sequence in another run. The returned array is allowed to contain duplicate entries. Hint: Look in class Random for a proper pseudo-random number generator. Math.random() does not take any seed as argument.
2. Add to SortTester a static method
   boolean sameElements(int[] a, int[] b)
   for efficiently checking that two not necessarily sorted arrays of integers in the interval [0;9999] contain exactly the same elements. (Remember there might be duplicate values.)
3. Add to SortTester another static method
   boolean ordered(int[] a)
   that checks whether the array a is sorted.
4. Using the class SortTester write and execute unit tests for InsertionSort and QuickSort (see e.g. exercise T.8) that ensures that the sorting algorithms are correct in the sense that they do sort the elements in the supplied array making them ordered and not loosing or adding elements.
5. Pick another of the sorting methods in the book and repeat the tests. How reusable is your code?
6. (Performance) Performance test the three sorting algorithms on the same sets of random arrays (use TPTP or do T.14 to obtain a timing framework). Draw curves showing runtime as a function of the length of the array. Does your measurements meet expectations?

Exercise T.14 (Timing of Algorithms)

In this exercise you will implement a class that can be used in measuring the execution time of algorithms.

1. Construct a class Clock with methods
   void start()
   and
   int timeElapsed().
   The first method starts the clock and the second returns the time in milliseconds elapsed since the call to start(). Use System.nanoTime() to implement the methods.
2. Add a method cpuTimeElapsed() that returns the CPU time in milliseconds elapsed since the call to start(). Use an object of type ThreadMXBean to measure this time. (Look at the slides from the lecture for inspiration.)
3. Experiment with the Clock class by measuring runtime for some of the algorithms you have implemented in earlier exercises. Try for different sizes of input to the algorithms. Check whether the observed complexity matches expectations.

Exercise T.15 (Regression Test)

In this exercise you will construct a regression test for the FifteenPuzzle. The exercise assumes that you already have a project FifteenPuzzle with appropriate unit tests from earlier exercises. If not, make this first.

1. Write an Ant build script to perform all the tests. You might get inspiration from this example.
2. Execute the script.
3. Try to deliberately introduce a bug in FifteenPuzzle, rerun the script and see how it fails.

Last updated Mar 25, 2008 09:19 Dan Witzner Hansen, Kristian Støvring