Lab 03: Timing Tests and Randomized Comparison Tests

Prerequisites to running the code.

Instructions: https://fa22.datastructur.es/materials/lab/lab03/

Solution: https://github.com/tomthestrom/cs61b/tree/master/lab03

The lab deals with writing timing and randomized tests, comparing their outputs and finding and fixing a tiny bug.

Timing Tests for List61B #

Timing the construction of an AList with a bad resize strategy

As discussed in lecture, a multiplicative resizing strategy will result in fast add operations / good performance, whereas an additive resizing strategy will result in slow add operations / bad performance. In this part of the lab, we’ll show how we can demonstrate this empirically.

In the timingtest package, we’ve provided the AList class created in lecture with the bad resizing strategy below:

public void addLast(Item x) {
    if (size == items.length) {
        resize(size + 1);
    }

    items[size] = x;
    size = size + 1;
}

Your goal for this part of the lab is to write code that tabulates the amount of time needed to create a AList of various sizes using the addLast method above. The output of this timing test will look something like this:

Timing table for addLast
           N     time (s)        # ops  microsec/op
------------------------------------------------------------
        1000         0.00         1000         0.20
        2000         0.01         2000         0.20
        4000         0.01         4000         1.20
        8000         0.04         8000         4.30
       16000         0.10        16000        10.00
       32000         0.50        32000        49.70
       64000         1.15        64000       114.80
      128000         3.74       128000       374.30

Solution:

class TimeAList

/**
 * Returns a table with rows at N breakpoints from startingN to MAX_N for addLast operation of AList
 */
public static void timeAListConstruction() {
    //starting nr of ops
    int startingN = Math.multiplyExact(1, 1000);
    //max nr of ops
    int MAX_N = Math.multiplyExact(128, 1000);

    AList<Integer> Ns = new AList<>();
    AList<Double> times = new AList<>();
    AList<Integer> opCounts = new AList<>();
    /**
     * for MAX_N = 128 runs 8 times - br points:
     * 1 000 / 2 000/ 4 000/ 8 000/ 16 000/ 32 000 /64 000 /128 000
     */
    for (int n = startingN; n <= MAX_N; n *= 2) {
        AList<Integer>timedA = new AList<>();
        Stopwatch sw = new Stopwatch();

        int opCount;
        /**
         * Fill ArrayList timedA with ints from 0 to N
         * */
        for (opCount = 0; opCount < n; opCount += 1) {
            timedA.addLast(opCount);
        }
        //stop Stopwatch
        times.addLast(sw.elapsedTime());

        Ns.addLast(n);
        opCounts.addLast(opCount);
    }

    printTimingTable(Ns, times, opCounts);
}

Output - of the timing test - AList with a bad resize strategy:

    N     time (s)        # ops  microsec/op
    1000         0.00         1000         1.00
    2000         0.00         2000         1.50
    4000         0.01         4000         2.25
    8000         0.03         8000         3.50
   16000         0.07        16000         4.38
   32000         0.23        32000         7.13
   64000         0.65        64000        10.17
  128000         2.38       128000        18.57

Timing the construction of an AList with a good resize strategy

Now modify the AList class so that the resize strategy is multiplicative instead of additive and rerun timeAListConstruction. Your AList objects should now be constructed nearly instantly, even for N = 128,000, and each add operation should only take a fraction of a microsecond.

Solution:

AList - addLast - modified resize to be multiplicative:

/** Inserts X into the back of the list. */
public void addLast(Item x) {
    if (size == items.length) {
        resize(size * 2);
    }

    items[size] = x;
    size = size + 1;
}

Output - of the timing test - AList with a good resize strategy:

           N     time (s)        # ops  microsec/op
------------------------------------------------------------
        1000         0.00         1000         0.00
        2000         0.00         2000         0.00
        4000         0.00         4000         0.25
        8000         0.00         8000         0.00
       16000         0.00        16000         0.06
       32000         0.00        32000         0.06
       64000         0.00        64000         0.03
      128000         0.00       128000         0.02

Timing the getLast method of SLList #

Suppose we want to compute the time per operation for getLast for an SLList and want to know how this runtime depends on N. To do this, we need to follow the procedure below:

1. Create an SLList.

2. Add N items to the SLList.

3. Start the timer.

4. Perform M getLast operations on the SLList.

5. Check the timer. This gives the total time to complete all M operations.

Solution:

class TimeSLList

public static void timeGetLast() {
    //starting nr of ops
    int startingN = Math.multiplyExact(1, 1000);
    //max nr of ops
    int MAX_N = Math.multiplyExact(128, 1000);

    int MAX_OP_COUNT = Math.multiplyExact(1, 10000);

    AList<Integer> Ns = new AList<>();
    AList<Double> times = new AList<>();
    AList<Integer> opCounts = new AList<>();

    /**
     * for MAX_N = 128 runs 8 times - br points:
     * 1 000 / 2 000/ 4 000/ 8 000/ 16 000/ 32 000 /64 000 /128 000
     * Fills SLList with N items
     * Calls getLast() of the SLList MAX_OP_COUNT times
     */
    for (int n = startingN; n <= MAX_N; n *= 2) {
        SLList<Integer> timedSLL = new SLList<>();

        int opCount;

        /**
         * Fill SLList timedSLL with stuffing (ints from 0 to N)
         * */
        for (int stuffing = 0; stuffing < n; stuffing += 1) {
            timedSLL.addLast(stuffing);
        }

        Stopwatch sw = new Stopwatch();
        // call getLast() MAX_OP_COUNT times
        for (opCount = 0; opCount < MAX_OP_COUNT; opCount += 1) {
            timedSLL.getLast();
        }
        //stop Stopwatch
        times.addLast(sw.elapsedTime());

        Ns.addLast(n);
        opCounts.addLast(opCount);
    }

    printTimingTable(Ns, times, opCounts);
}

Output of the timing test - SLList getLast() - 1000 times for various sizes of SLList:

           N     time (s)        # ops  microsec/op
------------------------------------------------------------
        1000         0.02        10000         1.90
        2000         0.03        10000         3.30
        4000         0.07        10000         6.60
        8000         0.15        10000        14.90
       16000         0.29        10000        28.80
       32000         0.58        10000        57.90
       64000         1.11        10000       111.30
      128000         2.66        10000       265.90

Obviously not a great output for retrieving the last item - this implementation of SLList goes over all the items to reach the last one.

Randomized Comparison Tests

Simple Comparison Test #

The goal of the rest of this lab is to find the bug in BuggyAList - a resizing AList. For our comparison, we're using a non-resizing, simple version of AList, called AListNoResizing that has an underlying array with a hardcoded size of 1000 .

Write a test called testThreeAddThreeRemove in TestBuggyAList that adds the same value to both the correct and buggy AList implementations, then checks that the results of three subsequent removeLast calls are the same.

Solution:

testThreeAddThreeRemove

/*
 * Simple comparison test
 * Test compares the results from performing the same operation on 2 classes:
 *  Class AListNoResizing vs TestBuggyAList
 */
@Test
public void testThreeAddThreeRemove() {
    AListNoResizing<Integer> ALNR = new AListNoResizing<>();
    BuggyAList<Integer> BAL = new BuggyAList<>();

    int testVal1 = 3;
    int testVal2 = 4;
    int testVal3 = 5;

    ALNR.addLast(testVal1);
    ALNR.addLast(testVal2);
    ALNR.addLast(testVal3);

    BAL.addLast(testVal1);
    BAL.addLast(testVal2);
    BAL.addLast(testVal3);


    assertEquals(ALNR.removeLast(), BAL.removeLast());
    assertEquals(ALNR.removeLast(), BAL.removeLast());
    assertEquals(ALNR.removeLast(), BAL.removeLast());
}

The test passed - it's not strong enough to identify the bug in BuggyAList

Randomized Function Calls #

Next we were encouraged to write a randomized test and use the debugger to find the bug, I came up with the following test suite:

Solution:

@Test
public void randomizedTest() {
    AListNoResizing<Integer> L = new AListNoResizing<>();
    BuggyAList<Integer> BL = new BuggyAList<>();


    int N = 500;
    for (int i = 0; i < N; i += 1) {
        int operationNumber = StdRandom.uniform(0, 4);

        // if operation can't be executed proceed to the next iteration
        if (L.size() == 0 && SizeNonZeroOperation.get(operationNumber)) {
            continue;
        }

        switch (operationNumber) {
            case 0 -> {
                int randVal = StdRandom.uniform(0, 100);
                L.addLast(randVal);
                BL.addLast(randVal);
            }
            case 1 -> {
                int sizeL = L.size();
                int sizeBL = BL.size();
                assertEquals(sizeL, sizeBL);
            }
            case 2 -> {
                int lastValL = L.getLast();
                int lastValBL = BL.getLast();
                assertEquals(lastValL, lastValBL);
            }
            case 3 -> {
                int lastValL = L.removeLast();
                int lastValBL = BL.removeLast();;
                assertEquals(lastValL, lastValBL);
            }
            default -> System.out.println("Operation nr " + operationNumber + " not implemented.");
        }
    }
}

Fixing the bug

Actually the bug lied an incorrect argument to the resize method

Original:

public Item removeLast() {
    if ((size < items.length / 4) && (size > 4)) {
        resize(size / 4);
    }
    Item x = getLast();
    items[size - 1] = null;
    size = size - 1;
    return x;
}

Solution:

public Item removeLast() {
    if ((size < items.length / 4) && (size > 4)) {
        resize(items.length / 4);
    }
    Item x = getLast();
    items[size - 1] = null;
    size = size - 1;
    return x;
}

Reasoning:

size != items.length, items is the underlying array, whose length only changes on resize, while size is an attribute that represents the number of elements in the array.