Class 16 — Wednesday, October 21

Monday’s Matrix, finished in your seat. Then two threads at once: one count they both add to, why it comes out short, and synchronized.

The A7 presentation comes first. Then Monday’s Matrix, in your seat; after the break, two threads at once.

  1. Why the editor refuses Matrix<Fraction> — predict first
  2. The Matrix, in your seat: getting in, then the tasks
  3. Two threads, one count — predict first
  4. One thread at a time
  5. Which of these needs synchronized? — predict first
  6. Each thread its own half

Your seat opens from a link inside the quiz Class 15 seats, in your ordinary browser this time: no LockDown. Your work goes to your repository for this class, cmsc-230-c15- and your GitHub name, which is there already: nothing to accept.

1. Why the editor refuses Matrix<Fraction>

Keyboards down.

The Matrix from A3, holding T instead of double. Its header says what a T must be able to do:

public final class Matrix<T extends Addition<T> & Multiplication<T>> {

Addition and Multiplication are two interfaces from a real library, Apache Commons Numbers, and the & means both. The first test in MatrixTest makes a matrix of fractions:

Matrix<Fraction> a = new Matrix<>(new Fraction[][] {{f(1, 10), f(1, 5)}, {f(1, 3), f(1, 6)}});

The editor underlines Matrix<Fraction>. What does Fraction not say yet, and what has to be written before the tests can run?

Fraction can add and multiply already, but it does not say that it is an Addition<Fraction> or a Multiplication<Fraction>, so the bound keeps it out. Between them the two interfaces ask for six methods. Fraction has two, add and multiply; the other four are zero(), one(), negate() and reciprocal(). zero() is the one multiply needs: A3’s started each sum from 0.0, and there is no 0 for a T, so a T has to hand over a zero of its own. That is task 1.

2. The Matrix, in your seat

2.1 Getting in

Pairs. In your ordinary browser.

Start the quiz Class 15 seats. It has no questions, only two links at its top. Open my seat lands you in an editor with the files already there, saved as you type. Submit my files sends what is in your seat to your repository on GitHub; press it as often as you like, and at the end it is done for you anyway. Leave the quiz open while you work.

If you worked in your seat on Monday, or pushed Monday’s work from your own computer, it is in your seat now.

The README.md in the seat is the task list, and test/MatrixTest.java is the tests, run from the arrow beside class MatrixTest. The status bar says Java: Ready once the editor has loaded the project. The tests do not run until task 1 is done. Sit with your pair at one seat; the other seat can hold the README.

2.2 The tasks

The Matrix from A3, holding T instead of double, and the Fraction from A2 and A4, finished. The README in the seat has each task in full, and each of tasks 1 to 3 ends with a test of your own: the value worked out by hand, then assertEquals, at the bottom of MatrixTest.

  1. Make Fraction an Addition<Fraction> and a Multiplication<Fraction>: it has add and multiply already; write zero(), one(), negate() and reciprocal(), one line each. The tests run, and 1/10 plus 2/10 is 3/10, exactly, where 0.1 + 0.2 is not 0.3. Your test: a fraction times its reciprocal is one.
  2. Write add: the same shape or DimensionMismatchException, then each cell’s add of its twin. Your test: adding zeros changes nothing.
  3. Write multiply: a row of this against a column of that, each sum started from a cell’s zero(). Your test: a 2-by-1 times a 1-by-2.
  4. Ask the editor about Matrix<Double>: a number, and still refused.

Then the spares in the README: Real, a class of one double that is an Addition<Real> and a Multiplication<Real>; and magnitude().

Done when every test in MatrixTest is green, yours too.

3. Two threads, one count

Keyboards down. Write your prediction in the Journal before it runs: one line.

Every program so far has done one thing after another, in one thread: the one that runs main. A program can start more, and they run at the same time. new Thread(() -> { ... }) makes a thread for the code between the braces, start() sets it running beside this one, and join() waits until it has finished.

Two threads, each adding 1 to the same count, 100,000 times:

// a count that two threads share
public class Counter {
    private int count;
    public void increment() {
        count++;
    }
    public int get() {
        return count;
    }
}
public class Race {
    public static void main(String[] args) throws InterruptedException {
        Counter counter = new Counter();
        Thread first = new Thread(() -> {
            for (int i = 0; i < 100_000; i++) {
                counter.increment();
            }
        });
        Thread second = new Thread(() -> {
            for (int i = 0; i < 100_000; i++) {
                counter.increment();
            }
        });
        first.start();
        second.start();
        first.join();
        second.join();
        System.out.println(counter.get());
    }
}

What does it print?

Each () -> { ... } is a lambda: a piece of code handed to someone else to run, here the thread. It can use the variables around it, counter here, as long as nothing assigns them again.

Thread’s constructor takes a Runnable, an interface with one method to write, run, and a lambda is short for a class that implements it: a field for what it uses, and run, its body the lambda’s. The () before the arrow is run’s list of parameters, which is empty.

// adds 1 to its counter, 100,000 times
public class Adder implements Runnable {
    private final Counter counter;

    public Adder(Counter counter) {
        this.counter = counter;
    }

    public void run() {
        for (int i = 0; i < 100_000; i++) {
            counter.increment();
        }
    }
}

and in main, Thread first = new Thread(new Adder(counter));.

Not 200000. Three runs in a seat printed

182482
198281
184843

a different number each time, and every one short. count++ looks like one step and is three: read the count, add one, write it back. When the two threads take turns in between, one of them writes over the other’s work:

first thread second thread count
reads 41 41
reads 41 41
writes 42 42
writes 42 42

Two additions, and the count went up by one. This is a race: what comes out depends on which thread gets there first, and that is different every run.

4. One thread at a time

Pairs, in your seat. Counter and Race go in src, beside Matrix.java; a test goes in test.

4.1 Make the count right

Mark increment synchronized:

public synchronized void increment() {

A thread that calls a synchronized method of an object while another thread is inside a synchronized method of the same object waits until that one is done. So the read, the add and the write happen together, one thread at a time. Run Race three times.

Your test: a new file, test/CounterTest.java: four threads, each a lambda adding 1 to one Counter 100,000 times; start all four, join all four, and assertEquals(400_000, counter.get()).

Done when it is green, and goes red, most runs, when you take synchronized off again (then put it back).

4.2 Forget the joins (if you are done)

Take the two join lines out of Race. Before you run it: what does it print now, and why? Run it a few times, then put them back.

Anywhere Java expects an interface with one method to write, a lambda can stand instead of a class:

  • A comparator, such as ByDenominator in A4, without its own file:

    Arrays.sort(fractions, (a, b) -> Integer.compare(a.getDenominator(), b.getDenominator()));
  • A priority queue’s order, as in ShortestFirst in A6:

    PriorityQueue<String> queue = new PriorityQueue<>((a, b) ->
            a.length() != b.length() ? Integer.compare(a.length(), b.length()) : a.compareTo(b));
  • Removing while walking, Prune in A5, without the iterator:

    matrices.removeIf(m -> m.magnitude() > 10);
  • Counting words, as in A5, one line for each word:

    counts.merge(word, 1, (old, one) -> old + one);
  • A test that expects an exception, in place of try, fail and catch:

    assertThrows(NoSuchElementException.class, () -> chain.removeFirst());

5. Which of these needs synchronized?

Keyboards down.

Three programs, each with two threads:

  1. Each thread adds 1 to the same Counter, 100,000 times: section 3.
  2. Each thread adds up its own half of one array into a field of its own, and main adds the two fields together after both joins.
  3. Each thread reads every number in one array that nobody changes, and prints the largest.

Which of them need synchronized to give the right answer, and why?

Only the first. There, two threads change the same field. In the second, each thread writes only its own field, and main reads them after the joins, when both threads have finished. In the third, nothing changes at all. Two threads need synchronized where they change the same thing, or where one changes what the other reads. Give each thread its own part to write, and there is nothing to lock.

6. Each thread its own half

Pairs, in your seat. 6.1, then 6.2 if you are done.

6.1 A sum in two halves

A new class in src, HalfSum implements Runnable, the way The same work, as a class in section 3 writes one: a class this time, not a lambda, because the work keeps a result of its own for main to read after the join. Four fields: an int[], the first place of its half, the place after its last, and a long sum, its result. run adds up its half into sum. Then a main: an array of 10,000,000 numbers, i % 7 in place i; two HalfSums, from 0 up to the middle and from the middle up to the end; a thread for each; start both, join both, and print the two sums added together beside the total of one ordinary loop over the array.

Your test: test/HalfSumTest.java: the two halves of an array of 1 to 100 add up to 5050.

Done when the two totals your main prints are the same, and your test is green.

6.2 Any number of parts

A main that splits the same array into 4 parts, or any number of parts: part i of n runs from i * length / n up to (i + 1) * length / n. Keep the threads in a List<Thread>, start them all, then join them all.

Your test: 3 parts of an array of 10 numbers, where the parts are not all the same length, add up to what one loop gives.

6.3 Primes in parts, against the clock

A prime has no divisor to stop at early, so the bigger the numbers, the longer a count of primes takes. This test tries every divisor up to the square root:

// whether n is prime: no divisor from 2 up to its square root
static boolean isPrime(int n) {
    if (n < 2) {
        return false;
    }
    for (int d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            return false;
        }
    }
    return true;
}

A new class, PrimeCount implements Runnable, counts the primes in its part, from one number up to another, and times itself: long start = System.nanoTime(); at the start of run, and (System.nanoTime() - start) / 1_000_000 at the end is its time in milliseconds, kept in a field. Then a main counts the primes below 3,000,000 in 1, 2 and 4 parts, three runs each, and prints the count, the time for all of it, each part’s own time, and Runtime.getRuntime().availableProcessors(): how many threads the computer your seat runs on lets you run at once.

Do two parts take half as long as one? Which part takes longest, and why?

Your test: the primes below 100 number 25, counted in one part and in three.