Assignment 01: How Fast is Your Computer?

testing the performance of your computer

Due: Friday, February 11th at 5:00pm (Submission via Gradescope)

Overview

Modern computers are really fast. In this assignment, you will get a sense of how quickly your computer can perform elementary operations. Your experiments will acquaint you with basic tools we’ll use through the class to measure the running time of code. Additionally, they will give some empirical justification for assumptions we make later in the class about running time analysis.

Background

At their core, computers are quite limited in the operations they can perform. The elementary instructions include reading values from memory, writing values to memory, performing basic arithmetic operations, and “branching” operations (i.e., if-then-else operations).

  1. Creating and initializing an array
  2. Accessing the elements in an array
  3. Performing basic arithmetic operations, such as +
  4. Performing basic logical operations, and branching based on the outcome, such as if(condition){...}

Code

Download the following zip archive to get started:

The archive includes two tools—the RunTimer and CSVWriter classes—that you will use throughout the semester to test and record running times of your programs.

Your Task

Your main task is to complete the implementation of Timing.java and use it to test the running times of four basic operations on your computer. The tests for two of the operations (creating and accessing elements in arrays) have already been completed. You should complete the following methods:

  • testArithmetic: Measure the typical time to perform arithmetic operations for various dataset (array) sizes. For each array size, the method creates 3 arrays of that size. The first two are initialized with random values. Each entry in the third array should be the sum of the corresponding entries in the first two arrays. The total elapsed time to perform this sum should be measured, and the average time per operation recorded in a csv file.

  • testLogic: Measure the typical time to perform arithmetic operations for various dataset (array) sizes. For each array size, the method creates 3 arrays of that size. The first two are initialized with random values. Each entry in the third array should be the minimum of the corresponding entries in the first two arrays. The total elapsed time to perform this sum should be measured, and the average time per operation recorded in a csv file.

    Note: to find the min of two values, you should write your own logical test with an if statement. Do not use Math.min() (unless you wish to compare the performance of your own code to Math.min()).

Questions

  1. For each method in Timing.java, generate a plot of the running times measured in that method. Does the running time per operation appear to grow with the size of the array? If so, how quickly?

  2. Consider the (provided) implementation of testArrayAccess. It contains the following inner loop:

    1
2
3
4
5
6
7

     for (int i = 0; i < numAccesses; i++) {
     int index = r.nextInt(size);

     rt.start();
     val = arr[index];
     rt.stop();
 }

    We can modify where the RunTimer call is made, so that only one call (rather than numAccesses calls) are made to the start/stop methods, as follows:

    1
2
3
4
5
6
7

     rt.start();	
 for (int i = 0; i < numAccesses; i++) {
     int index = r.nextInt(size);

     val = arr[index];
 }
 rt.stop();

    Which version of the method would you expect to give a more accurate measurement of the running of the line val = arr[index]? Which version of the method (typically) gives a smaller value? Is that what you expected? Why or why not?

What to Submit

You should submit the following documents to Gradescope:

  • Your completed Timing.java
  • A document in PDF format, responses.pdf including your responses to the questions above, along with supporting evidence (e.g., tables or graphs of running times).

Evaluation

Your submission will receive a score out of 10 points, broken down as follows:

  • 5 points for Timing.java
    • code compiles, runs, and produces sensible output
    • code is well organized and documented with comments
  • 5 points for the responses to the questions above