4
\$\begingroup\$

In an effort to learn Java's support for concurrency I solved a self-imposed exercise to write a Game of Life simulator in Java, running a separate thread for each cell.

Here is my code:

import java.util.*;
import java.lang.*;

interface ICell extends Runnable {
    boolean retrieveGeneration(int generation);
    void setNeighborGeneration(int x, int y, int gen);
}

class AlwaysDead implements ICell {
    private List<List<ICell>> grid;
    private int xPos, yPos;
    
    AlwaysDead(List<List<ICell>> grid, int xPos, int yPos) {
        this.grid = grid;
        this.xPos = xPos;
        this.yPos = yPos;
    }
    
    public boolean retrieveGeneration(int generation) {
        return false;
    }
    
    public void setNeighborGeneration(int x, int y, int gen) {}
    
    public void run() {
        for(int y = yPos-1; y <= yPos+1; y++) {
            for(int x = xPos-1; x <= xPos+1; x++) {
                if(y < grid.size() && y >= 0) {
                    if(x < grid.get(y).size() && x >= 0) {
                        if(x != xPos || y != yPos) {
                            ICell c = grid.get(y).get(x);
                            int maxv = Integer.MAX_VALUE;
                            c.setNeighborGeneration(xPos, yPos, maxv);
                        }
                    }
                }
            }
        }
    }
}

class Cell implements ICell {
    private List<Boolean> isPopulated;
    private int generationOffset;
    private List<List<ICell>> grid;
    private int generationNumber;
    private int xPos, yPos;
    private List<List<Integer>> neighborGeneration;
    private int steps;
    
    Cell(List<List<ICell>> grid, int xPos, int yPos, boolean val, int steps) {
        isPopulated = new ArrayList<Boolean>();
        isPopulated.add(val);
        generationOffset = 0;
        this.grid = grid;
        generationNumber = 0;
        this.xPos = xPos;
        this.yPos = yPos;
        neighborGeneration = new ArrayList<List<Integer>>();
        for(int y = 0; y < 3; y++) {
            neighborGeneration.add(new ArrayList<Integer>());
            for(int x = 0; x < 3; x++) {
                // This means that neighborGeneration[1][1] points at this cell
                // and will have a spurious value forever and will be ignored.
                // No matter - I leave this for the sake of simplicity
                neighborGeneration.get(y).add(0);
            }
        }
        this.steps = steps;
    }
    
    private synchronized int addGeneration(boolean populated) {
        isPopulated.add(populated);
        generationNumber++;
        return generationNumber;
    }
    
    private synchronized void removeOldGeneration() {
        isPopulated.remove(0);
        generationOffset++;
    }
    
    public synchronized boolean retrieveGeneration(int generation) {
        return isPopulated.get(generation-generationOffset);
    }
    
    private Collection<ICell> neighbors() {
        Collection<ICell> ret = new ArrayList<ICell>();
        for(int x = xPos-1; x <= xPos+1; x++) {
            for(int y = yPos-1; y <= yPos+1; y++) {
                if(xPos != x || yPos != y) {
                    ret.add(grid.get(y).get(x));
                }
            }
        }
        return ret;
    }
    
    private boolean willBeAlive(boolean isAlive, int neighboringAlive) {
        if(isAlive && neighboringAlive >= 2 && neighboringAlive <= 3) {
            return true;
        } else if(!isAlive && neighboringAlive == 3) {
            return true;
        } else {
            return false;
        }
    }
            
    private int step() {
        int neighboringAlive = 0;
        for(ICell c : neighbors()) {
            if(c.retrieveGeneration(generationNumber)) {
                neighboringAlive++;
            }
        }
        boolean isAlive = retrieveGeneration(generationNumber);
        return addGeneration(willBeAlive(isAlive, neighboringAlive));
    }
    
    public synchronized void setNeighborGeneration(int x, int y, int gen) {
        neighborGeneration.get(y-yPos+1).set(x-xPos+1, gen);
        if(canProgress()) {
            notify();
        }
    }
    
    private synchronized int getMinimalNeighboursGeneration() {
        int ret = Integer.MAX_VALUE;
        for(int y = 0; y < 3; y++) {
            for(int x = 0; x < 3; x++) {
                if(x != 1 || y != 1) {
                    ret = Math.min(ret, neighborGeneration.get(y).get(x));
                }
            }
        }
        return ret;
    }
    
    private synchronized boolean canProgress() {
        return getMinimalNeighboursGeneration() >= generationNumber;
    }
    
    private synchronized void clearUnneededGenerations() {
        while(isPopulated.size() > 2) {
            removeOldGeneration();
        }
    }
    
    private void notifyNeighbors(int currentGeneration) {
        for(ICell c : neighbors()) {
            c.setNeighborGeneration(xPos, yPos, currentGeneration);
        }
    }
    
    private synchronized void waitUntilCanProgress()
    throws InterruptedException {
        while(!canProgress()) {
            wait();
        }
    }
    
    public void run() {
        for(int i = 0; i < steps; i++) {
            int newGeneration = step();
            notifyNeighbors(newGeneration);
            clearUnneededGenerations();
            try {
                waitUntilCanProgress();
            } catch(InterruptedException e) {
                // What am I supposed to do here??
                // I can't make run() throw InterruptedException
            }
        }
    }
}

public class GameOfLife {
    static int steps = 10000;

    public static void main(String[] args)
    throws InterruptedException {
        List<List<ICell>> grid = inputToGrid(initialData());
        List<Thread> threads = new ArrayList<Thread>();
        for(int y = 0; y < grid.size(); y++) {
            for(int x = 0; x < grid.get(y).size(); x++) {
                Thread cell = new Thread(grid.get(y).get(x));
                threads.add(cell);
                cell.start();
            }
        }
        for(Thread cell: threads) {
            cell.join();
        }
        printGrid(grid);
        return;
    }
    
    public static void printGrid(List<List<ICell>> grid) {
        for(int y = 1; y < grid.size()-1; y++) {
            for(int x = 1; x < grid.get(y).size()-1; x++) {
                if(grid.get(y).get(x).retrieveGeneration(steps)) {
                    System.out.print("▒");
                } else {
                    System.out.print(" ");
                }
            }
            System.out.println("");
        }
    }
    
    public static List<List<ICell>> inputToGrid(int[][] input) {
        List<List<ICell>> ret = new ArrayList<List<ICell>>();
        int ySiz = input.length;
        int xSiz = input[0].length;
        ret.add(new ArrayList<ICell>());
        for(int x = 0; x < xSiz+2; x++) {
            ret.get(0).add(new AlwaysDead(ret, x, 0));
        }
        for(int y = 0; y < ySiz; y++) {
            ret.add(new ArrayList<ICell>());
            ret.get(y+1).add(new AlwaysDead(ret, 0, y+1));
            for(int x = 0; x < xSiz; x++) {
                boolean val = input[y][x]==1;
                ret.get(y+1).add(new Cell(ret, x+1, y+1, val, steps));
            }
            ret.get(y+1).add(new AlwaysDead(ret, xSiz+1, y+1));
        }
        ret.add(new ArrayList<ICell>());
        for(int x = 0; x < xSiz+2; x++) {
            ret.get(ySiz+1).add(new AlwaysDead(ret, x, ySiz+1));
        }
        return ret;
    }

    public static int[][] initialData() {
        int ret[][] = {
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}        };
        return ret;
    }
}

Since I'm trying to learn concurrency (preparing for an exam...) I would be especially interested to know if there is any obscure interleaving that could lead to a deadlock, or to two concurrent writes and subsequently to data corruption, and the likes. (Of course I tried to design the program to make this not possible) In practice I don't observe such problems, but this doesn't mean there can be none in theory.

I understand that in this particular case concurrency doesn't help performance-wise, but still I'm kind of surprised that program is so slow. Running 10k steps of simulation on an 80x23 grid takes minutes on my laptop. (If I ditch concurrency, have only a single thread and run the simulation sequentially, 10k steps on the same board takes only a few seconds).

(The sample input is just a Gosper gun)

Comments?

Improve this question
\$\endgroup\$
3
  • \$\begingroup\$ On my phone (late night), but just want to point out that, as you mentioned, using a single thread for each cell is not viable for even a 4x2 grid (I assume a processor with 8 logical threads) because you encounter a problem with 1. cache locality (how close data is together in memory for cache optimization), and 2. the context switches between threads (these are relatively expensive as you are essentially saving the state of one thread, and reloading another state over and over). I hope you will get a good review on this, seems interesting. \$\endgroup\$
    – Expert Thinker El Rey
    Aug 29, 2020 at 1:25
  • 1
    \$\begingroup\$ What you're seeing is why multi-threading beyond the (physical) CPU cores is not feasible. Hyperthreading and similar technologies do help, but nothing beats physical cores. With that grid you have 1840 threads trying to get one of, in the best case, 8 cores. That means you're looking at 230 threads per core. Swapping threads or processes in the CPU is expensive. Not "expensive" in the sense of "you know, my calculator app should receive highest process priority", but expensive in the sense you're seeing here. You're basically stalling the CPU with all the context swaps it has to perform. \$\endgroup\$
    – Bobby
    Aug 29, 2020 at 8:50
  • \$\begingroup\$ Ironically, you might get better performance on something like a 1995 Java 1.0 Sun JVM with Green Threads. I don't know how context switches are implemented in that JVM, but Green Threads can have many orders of magnitude more efficient context switching than native threads. If you try the same exercise with a language with a saner concurrency model, e.g. make each cell a Clojure Agent, you'd probably also see better performance. \$\endgroup\$
    – Jörg W Mittag
    Aug 29, 2020 at 14:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.