The Computer Language
Benchmarks Game

chameneos-redux Java program

source code

/* The Computer Language Benchmarks Game
   http://benchmarksgame.alioth.debian.org/

   contributed by Michael Barker
*/


import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;


/**
 * This implementation uses the java.util.concurrent.atomic library
 * i.e. (compare and set) to avoid locking.  Real threads are used, but
 * are set up as a thread pool and meeting requests are pushed onto a
 * queue that feeds the thread pool.
 */
public final class chameneosredux {

    enum Colour {
        blue,
        red,
        yellow
    }

    private static Colour doCompliment(final Colour c1, final Colour c2) {
        switch (c1) {
        case blue:
            switch (c2) {
            case blue:
                return Colour.blue;
            case red:
                return Colour.yellow;
            case yellow:
                return Colour.red;
            }
        case red:
            switch (c2) {
            case blue:
                return Colour.yellow;
            case red:
                return Colour.red;
            case yellow:
                return Colour.blue;
            }
        case yellow:
            switch (c2) {
            case blue:
                return Colour.red;
            case red:
                return Colour.blue;
            case yellow:
                return Colour.yellow;
            }
        }

        throw new RuntimeException("Error");
    }

    static final class MeetingPlace {

        private final AtomicInteger meetingsLeft;
        private final AtomicReference<Creature> creatureRef = new AtomicReference<Creature>();

        public MeetingPlace(final int meetings) {
            meetingsLeft = new AtomicInteger(meetings);
        }

        public void meet(final Creature incoming) {
            Colour newColour = null;
            Creature first = null;
            Creature next = null;
            do {
                first = creatureRef.get();
                next = incoming;
                if (first != null) {
                    newColour = doCompliment(incoming.colour, first.colour);
                    next = null;
                }
            } while (!creatureRef.compareAndSet(first, next));

            if (first != null) {
                final int meetings = meetingsLeft.decrementAndGet();
                if (meetings >= 0) {
                    first.setColour(incoming.id, newColour);
                    incoming.setColour(first.id, newColour);
                } else {
                    first.complete();
                    incoming.complete();
                }
            }
        }
    }

    static final class Dispatcher implements Runnable {
        private final BlockingQueue<Creature> q;

        public Dispatcher(final BlockingQueue<Creature> q) {
            this.q = q;
        }

        public void run() {
            try {
                while (true) {
                    q.take().run();
                }
            } catch (final InterruptedException e) {
            }
        }
    }

    static final class Creature {

        private final int id;
        private final MeetingPlace place;
        private final BlockingQueue<Creature> q;
        private final CountDownLatch latch;
        private int count = 0;
        private int sameCount = 0;
        private Colour colour;

        public Creature(final MeetingPlace place, final Colour colour,
                        final BlockingQueue<Creature> q, final CountDownLatch latch) {
            this.id = System.identityHashCode(this);
            this.place = place;
            this.latch = latch;
            this.colour = colour;
            this.q = q;
        }

        public void complete() {
            latch.countDown();
        }

        public void setColour(final int id, final Colour newColour) {
            this.colour = newColour;
            count++;
            sameCount += 1 ^ Integer.signum(abs(this.id - id));
            q.add(this);
        }

        private int abs(final int x) {
            final int y = x >> 31;
            return (x ^ y) - y;
        }

        public void run() {
            place.meet(this);
        }

        public int getCount() {
            return count;
        }

        @Override
        public String toString() {
            return String.valueOf(count) + getNumber(sameCount);
        }
    }

    private static void run(final int n, final Colour...colours) {
        final int len = colours.length;
        final MeetingPlace place = new MeetingPlace(n);
        final Creature[] creatures = new Creature[len];
        final BlockingQueue<Creature> q = new ArrayBlockingQueue<Creature>(len);
        final CountDownLatch latch = new CountDownLatch(len - 1);

        for (int i = 0; i < len; i++) {
            System.out.print(" " + colours[i]);
            creatures[i] = new Creature(place, colours[i], q, latch);
        }

        System.out.println();
        final Thread[] ts = new Thread[len];
        for (int i = 0, h = ts.length; i < h; i++) {
            ts[i] = new Thread(new Dispatcher(q));
            ts[i].setDaemon(true);
            ts[i].start();
        }

        for (final Creature creature : creatures) {
            q.add(creature);
        }

        try {
            latch.await();
            for (final Thread t : ts) {
                t.interrupt();
            }
            for (final Thread t : ts) {
                t.join();
            }
        } catch (final InterruptedException e1) {
            System.err.println("Existing with error: " + e1);
        }

        int total = 0;
        for (final Creature creature : creatures) {
            System.out.println(creature);
            total += creature.getCount();
        }
        System.out.println(getNumber(total));
        System.out.println();
    }

    public static void main(final String[] args){
        chameneosredux.program_main(args,true);
    }

    public static void program_main(final String[] args, final boolean isWarm) {

        int n = 600;
        try {
            n = Integer.parseInt(args[0]);
        } catch (final Exception e) {
        }

        printColours();
        System.out.println();
        run(n, Colour.blue, Colour.red, Colour.yellow);
        run(n, Colour.blue, Colour.red, Colour.yellow, Colour.red, Colour.yellow,
               Colour.blue, Colour.red, Colour.yellow, Colour.red, Colour.blue);
    }

    private static final String[] NUMBERS = {
        "zero", "one", "two", "three", "four", "five",
        "six", "seven", "eight", "nine"
    };

    private static String getNumber(final int n) {
        final StringBuilder sb = new StringBuilder();
        final String nStr = String.valueOf(n);
        for (int i = 0; i < nStr.length(); i++) {
            sb.append(" ");
            sb.append(NUMBERS[Character.getNumericValue(nStr.charAt(i))]);
        }

        return sb.toString();
    }

    private static void printColours() {
        printColours(Colour.blue, Colour.blue);
        printColours(Colour.blue, Colour.red);
        printColours(Colour.blue, Colour.yellow);
        printColours(Colour.red, Colour.blue);
        printColours(Colour.red, Colour.red);
        printColours(Colour.red, Colour.yellow);
        printColours(Colour.yellow, Colour.blue);
        printColours(Colour.yellow, Colour.red);
        printColours(Colour.yellow, Colour.yellow);
    }

    private static void printColours(final Colour c1, final Colour c2) {
        System.out.println(c1 + " + " + c2 + " -> " + doCompliment(c1, c2));
    }


}
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
java 9.0.1
Java(TM) SE Runtime Environment (build 9.0.1+11)
Java HotSpot(TM) 64-Bit Server VM (build 9.0.1+11, mixed mode)


Wed, 25 Oct 2017 21:28:54 GMT

MAKE:
mv chameneosredux.java chameneosredux.java
mv: 'chameneosredux.java' and 'chameneosredux.java' are the same file
/home/dunham/benchmarksgame/nanobench/makefiles/u64q.programs.Makefile:337: recipe for target 'chameneosredux.java_run' failed
make: [chameneosredux.java_run] Error 1 (ignored)
/opt/src/jdk-9.0.1/bin/javac -d .  chameneosredux.java

1.28s to complete and log all make actions

COMMAND LINE:
/opt/src/jdk-9.0.1/bin/java   chameneosredux 6000000

PROGRAM OUTPUT:
blue + blue -> blue
blue + red -> yellow
blue + yellow -> red
red + blue -> yellow
red + red -> red
red + yellow -> blue
yellow + blue -> red
yellow + red -> blue
yellow + yellow -> yellow

 blue red yellow
4081836 zero
3988933 zero
3929231 zero
 one two zero zero zero zero zero zero

 blue red yellow red yellow blue red yellow red blue
1050110 zero
1268696 zero
1246999 zero
1218404 zero
1211894 zero
1103099 zero
1281296 zero
1100201 zero
1368975 zero
1150326 zero
 one two zero zero zero zero zero zero