# HG changeset patch # User Marcel Hlopko # Date 1415218534 -3600 # Node ID e7f75a252b17e04dfdd3695824f38d1888571164 # Parent 68c5970ac0c689425e942b1e20d650601c98c104 Move calipel-java from separate project into jv-calipel diff -r 68c5970ac0c6 -r e7f75a252b17 java/.hgignore --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/.hgignore Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,3 @@ +target +.idea +calipel-java.iml diff -r 68c5970ac0c6 -r e7f75a252b17 java/README.md --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/README.md Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,3 @@ +# calipel-java + +This is a Java implementation for [jv-calipel](https://bitbucket.org/janvrany/jv-calipel) - a lightweight benchmarking framework. Check jv-calipel wiki for details on how to use the framework. diff -r 68c5970ac0c6 -r e7f75a252b17 java/pom.xml --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/pom.xml Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,28 @@ + + + 4.0.0 + + cz.cvut.fit.swing + calipel-java + 0.1 + + + + + commons-cli + commons-cli + 1.2 + + + + com.googlecode.json-simple + json-simple + 1.1.1 + + + + + + \ No newline at end of file diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/Main.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/Main.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,61 @@ +package cz.cvut.fit.swing.calipel; + +import cz.cvut.fit.swing.calipel.core.BenchmarkRunner; +import cz.cvut.fit.swing.calipel.core.BenchmarkSuite; +import cz.cvut.fit.swing.calipel.core.Configuration; +import cz.cvut.fit.swing.calipel.printer.JsonPrinter; +import cz.cvut.fit.swing.calipel.printer.Printer; +import cz.cvut.fit.swing.calipel.printer.StdOutPrinter; +import org.apache.commons.cli.*; + + +public class Main { + + public static void main(String[] args) { + Options options = describeAllowedOptions(); + try { + CommandLine cmd = parseCmdLineOptions(args, options); + processCmdLineOptions(options, cmd); + } catch (ParseException e) { + System.err.println("Parsing failed. Reason: " + e.getMessage()); + printHelp(options); + } + } + + private static Options describeAllowedOptions() { + Options options = new Options(); + + options.addOption("h", "help", false, "print this message"); + options.addOption("a", "arguments", true, "specify which benchmarks to run"); + options.addOption("j", "json", false, "use json printer"); + return options; + } + + private static CommandLine parseCmdLineOptions(String[] args, + Options options) throws ParseException { + CommandLineParser parser = new GnuParser(); + return parser.parse(options, args); + } + + private static void processCmdLineOptions(Options options, CommandLine cmd) { + Printer printer = new StdOutPrinter(); + Configuration configuration = new Configuration(); + + if (cmd.hasOption("h")) { + printHelp(options); + } else if (cmd.hasOption("n")) { + configuration.setNumOfTries(Integer.parseInt(cmd.getOptionValue("n"))); + } else if (cmd.hasOption("j")) { + printer = new JsonPrinter(); + } + + BenchmarkSuite benchmarks = new BenchmarkSuite(cmd.getOptionValue("a").split(","), configuration); + BenchmarkRunner runner = new BenchmarkRunner(benchmarks, printer, configuration); + runner.start(); + } + + private static void printHelp(Options options) { + HelpFormatter formatter = new HelpFormatter(); + formatter.printHelp("calipel-java ", options); + } +} diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/benchmarks/BenchmarkMicro.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/benchmarks/BenchmarkMicro.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,76 @@ +package cz.cvut.fit.swing.calipel.benchmarks; + +// $Id: Ary.java,v 1.3 2013-09-06 00:41:36 vrany Exp $ +// http://www.bagley.org/~doug/shootout/ + +// this program is modified from: +// http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html +// Timing Trials, or, the Trials of Timing: Experiments with Scripting +// and User-Interface Languages by Brian W. Kernighan and +// Christopher J. Van Wyk. + +import java.util.HashMap; + +@SuppressWarnings("unused") +public class BenchmarkMicro { + + @SuppressWarnings("unused") + public void ary() { + int n = 1000000; + int i; + int j; + int k; + int x[] = new int[n]; + int y[] = new int[n]; + + for (i = 0; i < n; i++) + x[i] = i + 1; + for (k = 0; k < 1000; k++) + for (j = n - 1; j >= 0; j--) + y[j] += x[j]; + } + + @SuppressWarnings("unused") + public void hsh() { + int n = 1000000; + int i, c; + + HashMap ht = new HashMap(); + c = 0; + for (i = 1; i <= n; i++) + ht.put(Integer.toString(i, 16), new Integer(i)); + for (i = 1; i <= n; i++) { + if (ht.containsKey(Integer.toString(i, 10))) { + c++; + } + } + } + + @SuppressWarnings("unused") + public void strcat() { + int n = 1000000; + String hello = "hello\n"; + StringBuffer stringBuffer = new StringBuffer(32); + for (int i = 0; i < n; i++) { + stringBuffer.append(hello); + } + } + + @SuppressWarnings("unused") + public void ackermann(int num) { + ackRecursive(3, num); + } + + private int ackRecursive(int m, int n) { + if (m == 0) { + return n + 1; + } else { + if (n == 0) { + return ackRecursive(m - 1, 1); + } else { + return ackRecursive(m - 1, ackRecursive(m, n - 1)); + } + } + } +} + diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/benchmarks/DeltaBlue.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/benchmarks/DeltaBlue.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,986 @@ +package cz.cvut.fit.swing.calipel.benchmarks; + +/* + * CL_SUN_COPYRIGHT_JVM_BEGIN + * If you or the company you represent has a separate agreement with both + * CableLabs and Sun concerning the use of this code, your rights and + * obligations with respect to this code shall be as set forth therein. No + * license is granted hereunder for any other purpose. + * CL_SUN_COPYRIGHT_JVM_END +*/ + +/* + * @(#)DeltaBlue.java 1.6 06/10/10 + * + * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License version + * 2 only, as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License version 2 for more details (a copy is + * included at /legal/license.txt). + * + * You should have received a copy of the GNU General Public License + * version 2 along with this work; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA + * 02110-1301 USA + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa + * Clara, CA 95054 or visit www.sun.com if you need additional + * information or have any questions. + * + */ +/* + + This is a Java implemention of the DeltaBlue algorithm described in: + "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver" + by Bjorn N. Freeman-Benson and John Maloney + January 1990 Communications of the ACM, + also available as University of Washington TR 89-08-06. + + This implementation by Mario Wolczko, Sun Microsystems, Sep 1996, + based on the Smalltalk implementation by John Maloney. + +*/ + +import java.util.ArrayList; + +/* +Strengths are used to measure the relative importance of constraints. +New strengths may be inserted in the strength hierarchy without +disrupting current constraints. Strengths cannot be created outside +this class, so pointer comparison can be used for value comparison. +*/ + +class Strength { + + private int strengthValue; + private String name; + + private Strength(int strengthValue, String name) { + this.strengthValue = strengthValue; + this.name = name; + } + + public static boolean stronger(Strength s1, Strength s2) { + return s1.strengthValue < s2.strengthValue; + } + + public static boolean weaker(Strength s1, Strength s2) { + return s1.strengthValue > s2.strengthValue; + } + + public static Strength weakestOf(Strength s1, Strength s2) { + return weaker(s1, s2) ? s1 : s2; + } + + public static Strength strongest(Strength s1, Strength s2) { + return stronger(s1, s2) ? s1 : s2; + } + + // for iteration + public Strength nextWeaker() { + switch (strengthValue) { + case 0: + return weakest; + case 1: + return weakDefault; + case 2: + return normal; + case 3: + return strongDefault; + case 4: + return preferred; + case 5: + return strongPreferred; + + case 6: + default: + System.err.println("Invalid call to nextStrength()!"); + System.exit(1); + return null; + } + } + + // Strength constants + public final static Strength required = new Strength(0, "required"); + public final static Strength strongPreferred = new Strength(1, "strongPreferred"); + public final static Strength preferred = new Strength(2, "preferred"); + public final static Strength strongDefault = new Strength(3, "strongDefault"); + public final static Strength normal = new Strength(4, "normal"); + public final static Strength weakDefault = new Strength(5, "weakDefault"); + public final static Strength weakest = new Strength(6, "weakest"); + + public void print() { + System.out.print("strength[" + Integer.toString(strengthValue) + "]"); + } +} + + +//------------------------------ variables ------------------------------ + +// I represent a constrained variable. In addition to my value, I +// maintain the structure of the constraint graph, the current +// dataflow graph, and various parameters of interest to the DeltaBlue +// incremental constraint solver. + +class Variable { + + public int value; // my value; changed by constraints + public ArrayList constraints; // normal constraints that reference me + public Constraint determinedBy; // the constraint that currently determines + // my value (or null if there isn't one) + public int mark; // used by the planner to mark constraints + public Strength walkStrength; // my walkabout strength + public boolean stay; // true if I am a planning-time constant + public String name; // a symbolic name for reporting purposes + + + private Variable(String name, int initialValue, Strength walkStrength, + int nconstraints) { + value = initialValue; + constraints = new ArrayList(nconstraints); + determinedBy = null; + mark = 0; + this.walkStrength = walkStrength; + stay = true; + this.name = name; + } + + public Variable(String name, int value) { + this(name, value, Strength.weakest, 2); + } + + public Variable(String name) { + this(name, 0, Strength.weakest, 2); + } + + public void print() { + System.out.print(name + "("); + walkStrength.print(); + System.out.print("," + value + ")"); + } + + // Add the given constraint to the set of all constraints that refer to me. + public void addConstraint(Constraint c) { + constraints.add(c); + } + + // Remove all traces of c from this variable. + public void removeConstraint(Constraint c) { + constraints.remove(c); + if (determinedBy == c) determinedBy = null; + } + + // Attempt to assign the given value to me using the given strength. + public void setValue(int value, Strength strength) { + EditConstraint e = new EditConstraint(this, strength); + if (e.isSatisfied()) { + this.value = value; + DeltaBlue.planner.propagateFrom(this); + } + e.destroyConstraint(); + } + +} + + +//------------------------ constraints ------------------------------------ + +// I am an abstract class representing a system-maintainable +// relationship (or "constraint") between a set of variables. I supply +// a strength instance variable; concrete subclasses provide a means +// of storing the constrained variables and other information required +// to represent a constraint. + +abstract class Constraint { + + public Strength strength; // the strength of this constraint + + protected Constraint() { + } // this has to be here because of + // Java's constructor idiocy. + + protected Constraint(Strength strength) { + this.strength = strength; + } + + // Answer true if this constraint is satisfied in the current solution. + public abstract boolean isSatisfied(); + + // Record the fact that I am unsatisfied. + public abstract void markUnsatisfied(); + + // Normal constraints are not input constraints. An input constraint + // is one that depends on external state, such as the mouse, the + // keyboard, a clock, or some arbitrary piece of imperative code. + public boolean isInput() { + return false; + } + + // Activate this constraint and attempt to satisfy it. + protected void addConstraint() { + addToGraph(); + DeltaBlue.planner.incrementalAdd(this); + } + + // Deactivate this constraint, remove it from the constraint graph, + // possibly causing other constraints to be satisfied, and destroy + // it. + public void destroyConstraint() { + if (isSatisfied()) DeltaBlue.planner.incrementalRemove(this); + removeFromGraph(); + } + + // Add myself to the constraint graph. + public abstract void addToGraph(); + + // Remove myself from the constraint graph. + public abstract void removeFromGraph(); + + // Decide if I can be satisfied and record that decision. The output + // of the choosen method must not have the given mark and must have + // a walkabout strength less than that of this constraint. + protected abstract void chooseMethod(int mark); + + // Set the mark of all input from the given mark. + protected abstract void markInputs(int mark); + + // Assume that I am satisfied. Answer true if all my current inputs + // are known. A variable is known if either a) it is 'stay' (i.e. it + // is a constant at plan execution time), b) it has the given mark + // (indicating that it has been computed by a constraint appearing + // earlier in the plan), or c) it is not determined by any + // constraint. + public abstract boolean inputsKnown(int mark); + + // Answer my current output variable. Raise an error if I am not + // currently satisfied. + public abstract Variable output(); + + // Attempt to find a way to enforce this constraint. If successful, + // record the solution, perhaps modifying the current dataflow + // graph. Answer the constraint that this constraint overrides, if + // there is one, or nil, if there isn't. + // Assume: I am not already satisfied. + // + public Constraint satisfy(int mark) { + chooseMethod(mark); + if (!isSatisfied()) { + if (strength == Strength.required) { + DeltaBlue.error("Could not satisfy a required constraint"); + } + return null; + } + // constraint can be satisfied + // mark inputs to allow cycle detection in addPropagate + markInputs(mark); + Variable out = output(); + Constraint overridden = out.determinedBy; + if (overridden != null) overridden.markUnsatisfied(); + out.determinedBy = this; + if (!DeltaBlue.planner.addPropagate(this, mark)) { + System.out.println("Cycle encountered"); + return null; + } + out.mark = mark; + return overridden; + } + + // Enforce this constraint. Assume that it is satisfied. + public abstract void execute(); + + // Calculate the walkabout strength, the stay flag, and, if it is + // 'stay', the value for the current output of this + // constraint. Assume this constraint is satisfied. + public abstract void recalculate(); + + protected abstract void printInputs(); + + protected void printOutput() { + output().print(); + } + + public void print() { + int i, outIndex; + + if (!isSatisfied()) { + System.out.print("Unsatisfied"); + } else { + System.out.print("Satisfied("); + printInputs(); + System.out.print(" -> "); + printOutput(); + System.out.print(")"); + } + System.out.print("\n"); + } + +} + + +//-------------unary constraints------------------------------------------- + +// I am an abstract superclass for constraints having a single +// possible output variable. +// +abstract class UnaryConstraint extends Constraint { + + protected Variable myOutput; // possible output variable + protected boolean satisfied; // true if I am currently satisfied + + protected UnaryConstraint(Variable v, Strength strength) { + super(strength); + myOutput = v; + satisfied = false; + addConstraint(); + } + + // Answer true if this constraint is satisfied in the current solution. + public boolean isSatisfied() { + return satisfied; + } + + // Record the fact that I am unsatisfied. + public void markUnsatisfied() { + satisfied = false; + } + + // Answer my current output variable. + public Variable output() { + return myOutput; + } + + // Add myself to the constraint graph. + public void addToGraph() { + myOutput.addConstraint(this); + satisfied = false; + } + + // Remove myself from the constraint graph. + public void removeFromGraph() { + if (myOutput != null) myOutput.removeConstraint(this); + satisfied = false; + } + + // Decide if I can be satisfied and record that decision. + protected void chooseMethod(int mark) { + satisfied = myOutput.mark != mark + && Strength.stronger(strength, myOutput.walkStrength); + } + + protected void markInputs(int mark) { + } // I have no inputs + + public boolean inputsKnown(int mark) { + return true; + } + + // Calculate the walkabout strength, the stay flag, and, if it is + // 'stay', the value for the current output of this + // constraint. Assume this constraint is satisfied." + public void recalculate() { + myOutput.walkStrength = strength; + myOutput.stay = !isInput(); + if (myOutput.stay) execute(); // stay optimization + } + + protected void printInputs() { + } // I have no inputs + +} + + +// I am a unary input constraint used to mark a variable that the +// client wishes to change. +// +class EditConstraint extends UnaryConstraint { + + public EditConstraint(Variable v, Strength str) { + super(v, str); + } + + // I indicate that a variable is to be changed by imperative code. + public boolean isInput() { + return true; + } + + public void execute() { + } // Edit constraints do nothing. + +} + +// I mark variables that should, with some level of preference, stay +// the same. I have one method with zero inputs and one output, which +// does nothing. Planners may exploit the fact that, if I am +// satisfied, my output will not change during plan execution. This is +// called "stay optimization". +// +class StayConstraint extends UnaryConstraint { + + // Install a stay constraint with the given strength on the given variable. + public StayConstraint(Variable v, Strength str) { + super(v, str); + } + + public void execute() { + } // Stay constraints do nothing. + +} + + +//-------------binary constraints------------------------------------------- + + +// I am an abstract superclass for constraints having two possible +// output variables. +// +abstract class BinaryConstraint extends Constraint { + + protected Variable v1, v2; // possible output variables + protected byte direction; // one of the following... + protected static byte backward = -1; // v1 is output + protected static byte nodirection = 0; // not satisfied + protected static byte forward = 1; // v2 is output + + protected BinaryConstraint() { + } // this has to be here because of + // Java's constructor idiocy. + + protected BinaryConstraint(Variable var1, Variable var2, Strength strength) { + super(strength); + v1 = var1; + v2 = var2; + direction = nodirection; + addConstraint(); + } + + // Answer true if this constraint is satisfied in the current solution. + public boolean isSatisfied() { + return direction != nodirection; + } + + // Add myself to the constraint graph. + public void addToGraph() { + v1.addConstraint(this); + v2.addConstraint(this); + direction = nodirection; + } + + // Remove myself from the constraint graph. + public void removeFromGraph() { + if (v1 != null) v1.removeConstraint(this); + if (v2 != null) v2.removeConstraint(this); + direction = nodirection; + } + + // Decide if I can be satisfied and which way I should flow based on + // the relative strength of the variables I relate, and record that + // decision. + // + protected void chooseMethod(int mark) { + if (v1.mark == mark) + direction = + v2.mark != mark && Strength.stronger(strength, v2.walkStrength) + ? forward : nodirection; + + if (v2.mark == mark) + direction = + v1.mark != mark && Strength.stronger(strength, v1.walkStrength) + ? backward : nodirection; + + // If we get here, neither variable is marked, so we have a choice. + if (Strength.weaker(v1.walkStrength, v2.walkStrength)) + direction = + Strength.stronger(strength, v1.walkStrength) ? backward : nodirection; + else + direction = + Strength.stronger(strength, v2.walkStrength) ? forward : nodirection; + } + + // Record the fact that I am unsatisfied. + public void markUnsatisfied() { + direction = nodirection; + } + + // Mark the input variable with the given mark. + protected void markInputs(int mark) { + input().mark = mark; + } + + public boolean inputsKnown(int mark) { + Variable i = input(); + return i.mark == mark || i.stay || i.determinedBy == null; + } + + // Answer my current output variable. + public Variable output() { + return direction == forward ? v2 : v1; + } + + // Answer my current input variable + public Variable input() { + return direction == forward ? v1 : v2; + } + + // Calculate the walkabout strength, the stay flag, and, if it is + // 'stay', the value for the current output of this + // constraint. Assume this constraint is satisfied. + // + public void recalculate() { + Variable in = input(), out = output(); + out.walkStrength = Strength.weakestOf(strength, in.walkStrength); + out.stay = in.stay; + if (out.stay) execute(); + } + + protected void printInputs() { + input().print(); + } + +} + + +// I constrain two variables to have the same value: "v1 = v2". +// +class EqualityConstraint extends BinaryConstraint { + + // Install a constraint with the given strength equating the given variables. + public EqualityConstraint(Variable var1, Variable var2, Strength strength) { + super(var1, var2, strength); + } + + // Enforce this constraint. Assume that it is satisfied. + public void execute() { + output().value = input().value; + } + +} + + +// I relate two variables by the linear scaling relationship: "v2 = +// (v1 * scale) + offset". Either v1 or v2 may be changed to maintain +// this relationship but the scale factor and offset are considered +// read-only. +// +class ScaleConstraint extends BinaryConstraint { + + protected Variable scale; // scale factor input variable + protected Variable offset; // offset input variable + + // Install a scale constraint with the given strength on the given variables. + public ScaleConstraint(Variable src, Variable scale, Variable offset, + Variable dest, Strength strength) { + // Curse this wretched language for insisting that constructor invocation + // must be the first thing in a method... + // ..because of that, we must copy the code from the inherited + // constructors. + this.strength = strength; + v1 = src; + v2 = dest; + direction = nodirection; + this.scale = scale; + this.offset = offset; + addConstraint(); + } + + // Add myself to the constraint graph. + public void addToGraph() { + super.addToGraph(); + scale.addConstraint(this); + offset.addConstraint(this); + } + + // Remove myself from the constraint graph. + public void removeFromGraph() { + super.removeFromGraph(); + if (scale != null) scale.removeConstraint(this); + if (offset != null) offset.removeConstraint(this); + } + + // Mark the inputs from the given mark. + protected void markInputs(int mark) { + super.markInputs(mark); + scale.mark = offset.mark = mark; + } + + // Enforce this constraint. Assume that it is satisfied. + public void execute() { + if (direction == forward) + v2.value = v1.value * scale.value + offset.value; + else + v1.value = (v2.value - offset.value) / scale.value; + } + + // Calculate the walkabout strength, the stay flag, and, if it is + // 'stay', the value for the current output of this + // constraint. Assume this constraint is satisfied. + public void recalculate() { + Variable in = input(), out = output(); + out.walkStrength = Strength.weakestOf(strength, in.walkStrength); + out.stay = in.stay && scale.stay && offset.stay; + if (out.stay) execute(); // stay optimization + } +} + + +// ------------------------------------------------------------ + + +// A Plan is an ordered list of constraints to be executed in sequence +// to resatisfy all currently satisfiable constraints in the face of +// one or more changing inputs. + +class Plan { + + private ArrayList v; + + public Plan() { + v = new ArrayList(); + } + + public void addConstraint(Constraint c) { + v.add(c); + } + + public int size() { + return v.size(); + } + + public Constraint constraintAt(int index) { + return v.get(index); + } + + public void execute() { + for (int i = 0; i < size(); ++i) { + Constraint c = constraintAt(i); + c.execute(); + } + } + +} + + +// ------------------------------------------------------------ + +// The DeltaBlue planner + +class Planner { + + int currentMark = 0; + + // Select a previously unused mark value. + private int newMark() { + return ++currentMark; + } + + public Planner() { + currentMark = 0; + } + + // Attempt to satisfy the given constraint and, if successful, + // incrementally update the dataflow graph. Details: If satifying + // the constraint is successful, it may override a weaker constraint + // on its output. The algorithm attempts to resatisfy that + // constraint using some other method. This process is repeated + // until either a) it reaches a variable that was not previously + // determined by any constraint or b) it reaches a constraint that + // is too weak to be satisfied using any of its methods. The + // variables of constraints that have been processed are marked with + // a unique mark value so that we know where we've been. This allows + // the algorithm to avoid getting into an infinite loop even if the + // constraint graph has an inadvertent cycle. + // + public void incrementalAdd(Constraint c) { + int mark = newMark(); + Constraint overridden = c.satisfy(mark); + while (overridden != null) { + overridden = overridden.satisfy(mark); + } + } + + + // Entry point for retracting a constraint. Remove the given + // constraint and incrementally update the dataflow graph. + // Details: Retracting the given constraint may allow some currently + // unsatisfiable downstream constraint to be satisfied. We therefore collect + // a list of unsatisfied downstream constraints and attempt to + // satisfy each one in turn. This list is traversed by constraint + // strength, strongest first, as a heuristic for avoiding + // unnecessarily adding and then overriding weak constraints. + // Assume: c is satisfied. + // + public void incrementalRemove(Constraint c) { + Variable out = c.output(); + c.markUnsatisfied(); + c.removeFromGraph(); + ArrayList unsatisfied = removePropagateFrom(out); + Strength strength = Strength.required; + do { + for (int i = 0; i < unsatisfied.size(); ++i) { + Constraint u = unsatisfied.get(i); + if (u.strength == strength) + incrementalAdd(u); + } + strength = strength.nextWeaker(); + } while (strength != Strength.weakest); + } + + // Recompute the walkabout strengths and stay flags of all variables + // downstream of the given constraint and recompute the actual + // values of all variables whose stay flag is true. If a cycle is + // detected, remove the given constraint and answer + // false. Otherwise, answer true. + // Details: Cycles are detected when a marked variable is + // encountered downstream of the given constraint. The sender is + // assumed to have marked the inputs of the given constraint with + // the given mark. Thus, encountering a marked node downstream of + // the output constraint means that there is a path from the + // constraint's output to one of its inputs. + // + public boolean addPropagate(Constraint c, int mark) { + ArrayList todo = new ArrayList(); + todo.add(c); + while (!todo.isEmpty()) { + Constraint d = todo.get(0); + todo.remove(0); + if (d.output().mark == mark) { + incrementalRemove(c); + return false; + } + d.recalculate(); + addConstraintsConsumingTo(d.output(), todo); + } + return true; + } + + + // The given variable has changed. Propagate new values downstream. + public void propagateFrom(Variable v) { + ArrayList todo = new ArrayList(); + addConstraintsConsumingTo(v, todo); + while (!todo.isEmpty()) { + Constraint c = todo.get(0); + todo.remove(0); + c.execute(); + addConstraintsConsumingTo(c.output(), todo); + } + } + + // Update the walkabout strengths and stay flags of all variables + // downstream of the given constraint. Answer a collection of + // unsatisfied constraints sorted in order of decreasing strength. + // + protected ArrayList removePropagateFrom(Variable out) { + out.determinedBy = null; + out.walkStrength = Strength.weakest; + out.stay = true; + ArrayList unsatisfied = new ArrayList(); + ArrayList todo = new ArrayList(); + todo.add(out); + while (!todo.isEmpty()) { + Variable v = todo.get(0); + todo.remove(0); + for (int i = 0; i < v.constraints.size(); ++i) { + Constraint c = v.constraints.get(i); + if (!c.isSatisfied()) + unsatisfied.add(c); + } + Constraint determiningC = v.determinedBy; + for (int i = 0; i < v.constraints.size(); ++i) { + Constraint nextC = v.constraints.get(i); + if (nextC != determiningC && nextC.isSatisfied()) { + nextC.recalculate(); + todo.add(nextC.output()); + } + } + } + return unsatisfied; + } + + // Extract a plan for resatisfaction starting from the outputs of + // the given constraints, usually a set of input constraints. + // + protected Plan extractPlanFromConstraints(ArrayList constraints) { + ArrayList sources = new ArrayList(); + for (int i = 0; i < constraints.size(); ++i) { + Constraint c = constraints.get(i); + if (c.isInput() && c.isSatisfied()) + sources.add(c); + } + return makePlan(sources); + } + + // Extract a plan for resatisfaction starting from the given source + // constraints, usually a set of input constraints. This method + // assumes that stay optimization is desired; the plan will contain + // only constraints whose output variables are not stay. Constraints + // that do no computation, such as stay and edit constraints, are + // not included in the plan. + // Details: The outputs of a constraint are marked when it is added + // to the plan under construction. A constraint may be appended to + // the plan when all its input variables are known. A variable is + // known if either a) the variable is marked (indicating that has + // been computed by a constraint appearing earlier in the plan), b) + // the variable is 'stay' (i.e. it is a constant at plan execution + // time), or c) the variable is not determined by any + // constraint. The last provision is for past states of history + // variables, which are not stay but which are also not computed by + // any constraint. + // Assume: sources are all satisfied. + // + protected Plan makePlan(ArrayList sources) { + int mark = newMark(); + Plan plan = new Plan(); + ArrayList todo = sources; + while (!todo.isEmpty()) { + Constraint c = todo.get(0); + todo.remove(0); + if (c.output().mark != mark && c.inputsKnown(mark)) { + // not in plan already and eligible for inclusion + plan.addConstraint(c); + c.output().mark = mark; + addConstraintsConsumingTo(c.output(), todo); + } + } + return plan; + } + + protected void addConstraintsConsumingTo(Variable v, ArrayList coll) { + Constraint determiningC = v.determinedBy; + ArrayList cc = v.constraints; + for (int i = 0; i < cc.size(); ++i) { + Constraint c = cc.get(i); + if (c != determiningC && c.isSatisfied()) + coll.add(c); + } + } + +} + +//------------------------------------------------------------ + +public class DeltaBlue { + + public static Planner planner; + + public void run() { + int iterations = 1000; + String options = ""; + + + for (int j = 0; j < iterations; ++j) { + chainTest(100); + projectionTest(100); + } + } + + + // This is the standard DeltaBlue benchmark. A long chain of + // equality constraints is constructed with a stay constraint on + // one end. An edit constraint is then added to the opposite end + // and the time is measured for adding and removing this + // constraint, and extracting and executing a constraint + // satisfaction plan. There are two cases. In case 1, the added + // constraint is stronger than the stay constraint and values must + // propagate down the entire length of the chain. In case 2, the + // added constraint is weaker than the stay constraint so it cannot + // be accomodated. The cost in this case is, of course, very + // low. Typical situations lie somewhere between these two + // extremes. + // + private void chainTest(int n) { + planner = new Planner(); + + Variable prev = null, first = null, last = null; + + // Build chain of n equality constraints + for (int i = 0; i <= n; i++) { + String name = "v" + Integer.toString(i); + Variable v = new Variable(name); + if (prev != null) + new EqualityConstraint(prev, v, Strength.required); + if (i == 0) first = v; + if (i == n) last = v; + prev = v; + } + + new StayConstraint(last, Strength.strongDefault); + Constraint editC = new EditConstraint(first, Strength.preferred); + ArrayList editV = new ArrayList(); + editV.add(editC); + Plan plan = planner.extractPlanFromConstraints(editV); + for (int i = 0; i < 100; i++) { + first.value = i; + plan.execute(); + if (last.value != i) + error("Chain test failed!"); + } + editC.destroyConstraint(); + } + + + // This test constructs a two sets of variables related to each + // other by a simple linear transformation (scale and offset). The + // time is measured to change a variable on either side of the + // mapping and to change the scale and offset factors. + // + private void projectionTest(int n) { + planner = new Planner(); + + Variable scale = new Variable("scale", 10); + Variable offset = new Variable("offset", 1000); + Variable src = null, dst = null; + + ArrayList dests = new ArrayList(); + + for (int i = 0; i < n; ++i) { + src = new Variable("src" + Integer.toString(i), i); + dst = new Variable("dst" + Integer.toString(i), i); + dests.add(dst); + new StayConstraint(src, Strength.normal); + new ScaleConstraint(src, scale, offset, dst, Strength.required); + } + + change(src, 17); + if (dst.value != 1170) error("Projection test 1 failed!"); + + change(dst, 1050); + if (src.value != 5) error("Projection test 2 failed!"); + + change(scale, 5); + for (int i = 0; i < n - 1; ++i) { + if ((dests.get(i)).value != i * 5 + 1000) + error("Projection test 3 failed!"); + } + + change(offset, 2000); + for (int i = 0; i < n - 1; ++i) { + if ((dests.get(i)).value != i * 5 + 2000) + error("Projection test 4 failed!"); + } + } + + private void change(Variable var, int newValue) { + EditConstraint editC = new EditConstraint(var, Strength.preferred); + ArrayList editV = new ArrayList(); + editV.add(editC); + Plan plan = planner.extractPlanFromConstraints(editV); + for (int i = 0; i < 10; i++) { + var.value = newValue; + plan.execute(); + } + editC.destroyConstraint(); + } + + public static void error(String error) { + System.err.println(error); + } + +} + diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/core/Benchmark.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/core/Benchmark.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,42 @@ +package cz.cvut.fit.swing.calipel.core; + +import java.util.ArrayList; +import java.util.List; + +public class Benchmark { + private List benchmarkInstances; + private Configuration configuration; + + public Benchmark(List benchmarkInstances, + Configuration configuration) { + this.benchmarkInstances = benchmarkInstances; + this.configuration = configuration; + } + + public void run(BenchmarkResult result) { + for (BenchmarkInstance instance : benchmarkInstances) { + try { + + for (int i = 0; i < 10; i++) { + instance.timeIt(); + } + + List durations = new ArrayList(); + for (int i = 0; i < configuration.getNumOfTries(); i++) { + durations.add(instance.timeIt()); + } + + result.benchmarkMeasured(instance, durations); + } catch (Exception e) { + result.benchmarkFailed(this, e); + } + } + } + + @Override + public String toString() { + return "Benchmark{" + + "benchmarkInstances=" + benchmarkInstances + + '}'; + } +} diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkFailure.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkFailure.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,23 @@ +package cz.cvut.fit.swing.calipel.core; + +/** + * User: mh + */ +public class BenchmarkFailure { + + private Benchmark benchmark; + private Exception exception; + + public BenchmarkFailure(Benchmark benchmark, Exception exception) { + this.benchmark = benchmark; + this.exception = exception; + } + + @Override + public String toString() { + return "BenchmarkFailure{" + + "benchmark=" + benchmark + + ", exception=" + exception + + '}'; + } +} diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkInstance.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkInstance.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,35 @@ +package cz.cvut.fit.swing.calipel.core; + +import java.lang.reflect.InvocationTargetException; +import java.lang.reflect.Method; +import java.util.LinkedHashMap; +import java.util.Map; + +public class BenchmarkInstance { + + private Object benchmarkImplementation; + private String selector; + + public BenchmarkInstance(Object benchmarkImplementation, String selector) { + this.benchmarkImplementation = benchmarkImplementation; + this.selector = selector; + } + + public Long timeIt() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException { + Method measuredMethod = benchmarkImplementation.getClass().getDeclaredMethod(selector); + + Long start = System.currentTimeMillis(); + measuredMethod.invoke(benchmarkImplementation); + Long end = System.currentTimeMillis(); + + return end - start; + } + + public Map toMap() { + Map map = new LinkedHashMap(); + map.put("class", benchmarkImplementation.getClass().getSimpleName()); + map.put("selector", selector); + + return map; + } +} diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkOutcome.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkOutcome.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,34 @@ +package cz.cvut.fit.swing.calipel.core; + +import java.util.Collections; +import java.util.LinkedHashMap; +import java.util.List; +import java.util.Map; + +public class BenchmarkOutcome { + + private final BenchmarkInstance benchmarkInstance; + private final List durations; + + public BenchmarkOutcome(BenchmarkInstance benchmarkInstance, List durations) { + this.benchmarkInstance = benchmarkInstance; + this.durations = durations; + } + + @Override + public String toString() { + return "BenchmarkOutcome{" + + "benchmarkInstance=" + benchmarkInstance + + ", durations=" + durations + + '}'; + } + + public Map toMap() { + Map map = new LinkedHashMap(); + map.put("benchmark", benchmarkInstance.toMap()); + map.put("times", durations); + map.put("parameters", Collections.emptyMap()); + + return map; + } +} diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkResult.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkResult.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,31 @@ +package cz.cvut.fit.swing.calipel.core; + +import java.util.ArrayList; +import java.util.List; + +public class BenchmarkResult { + + private List failedBenchmarks = new ArrayList(); + private List measuredBenchmarks = new ArrayList(); + + + public void benchmarkFailed(Benchmark benchmark, Exception e) { + failedBenchmarks.add(new BenchmarkFailure(benchmark, e)); + } + + public void benchmarkMeasured(BenchmarkInstance benchmark, List durations) { + measuredBenchmarks.add(new BenchmarkOutcome(benchmark, durations)); + } + + @Override + public String toString() { + return "BenchmarkResult{" + + "failedBenchmarks=" + failedBenchmarks + + ", measuredBenchmarks=" + measuredBenchmarks + + '}'; + } + + public List getMeasuredBenchmarks() { + return measuredBenchmarks; + } +} diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkRunner.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkRunner.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,30 @@ +package cz.cvut.fit.swing.calipel.core; + +import cz.cvut.fit.swing.calipel.printer.Printer; + +/** + * User: mh + */ +public class BenchmarkRunner { + private final Configuration configuration; + private final BenchmarkSuite benchmarks; + private final Printer printer; + + public BenchmarkRunner(BenchmarkSuite benchmarks, + Printer printer, + Configuration configuration) { + this.benchmarks = benchmarks; + this.printer = printer; + this.configuration = configuration; + } + + public void start() { + BenchmarkResult result = new BenchmarkResult(); + + for (Benchmark benchmark : benchmarks.getAllBenchmarks()) { + benchmark.run(result); + } + + printer.printResult(result); + } +} diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkSuite.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/core/BenchmarkSuite.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,44 @@ +package cz.cvut.fit.swing.calipel.core; + +import java.lang.reflect.Method; +import java.util.ArrayList; +import java.util.List; + +public class BenchmarkSuite { + private final String[] benchmarks; + private final Configuration configuration; + + public BenchmarkSuite(String[] benchmarks, Configuration configuration) { + this.benchmarks = benchmarks; + this.configuration = configuration; + } + + public List getAllBenchmarks() { + List result = new ArrayList(); + for (String benchmarkName : benchmarks) { + result.add(lookupBenchmark(benchmarkName)); + } + + return result; + } + + private Benchmark lookupBenchmark(String benchmarkName) { + try { + Class benchmarkClass = getClass().getClassLoader().loadClass( + "cz.cvut.fit.swing.calipel.benchmarks." + benchmarkName); + + List instances = new ArrayList(); + for (Method method : benchmarkClass.getMethods()) { + Object benchmarkImplementation = benchmarkClass.newInstance(); + String selector = method.getName(); + + instances.add(new BenchmarkInstance(benchmarkImplementation, selector)); + } + + return new Benchmark(instances, configuration); + } catch (Exception e) { + throw new RuntimeException( + String.format("Don't know how to find [%s] benchmark", benchmarkName), e); + } + } +} diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/core/Configuration.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/core/Configuration.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,14 @@ +package cz.cvut.fit.swing.calipel.core; + +public class Configuration { + + private int numOfTries = 5; + + public int getNumOfTries() { + return numOfTries; + } + + public void setNumOfTries(int numOfTries) { + this.numOfTries = numOfTries; + } +} diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/printer/JsonPrinter.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/printer/JsonPrinter.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,25 @@ +package cz.cvut.fit.swing.calipel.printer; + +import cz.cvut.fit.swing.calipel.core.BenchmarkOutcome; +import cz.cvut.fit.swing.calipel.core.BenchmarkResult; +import org.json.simple.JSONObject; + +import java.util.ArrayList; +import java.util.List; +import java.util.Map; + +public class JsonPrinter extends Printer { + + @Override + public void printResult(BenchmarkResult result) { + JSONObject json = new JSONObject(); + List outcomes = new ArrayList(); + for (BenchmarkOutcome measurement : result.getMeasuredBenchmarks()) { + outcomes.add(measurement.toMap()); + } + + json.put("outcomes", outcomes); + + System.out.println(json.toJSONString()); + } +} diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/printer/Printer.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/printer/Printer.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,7 @@ +package cz.cvut.fit.swing.calipel.printer; + +import cz.cvut.fit.swing.calipel.core.BenchmarkResult; + +public abstract class Printer { + public abstract void printResult(BenchmarkResult result); +} diff -r 68c5970ac0c6 -r e7f75a252b17 java/src/main/java/cz/cvut/fit/swing/calipel/printer/StdOutPrinter.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/java/src/main/java/cz/cvut/fit/swing/calipel/printer/StdOutPrinter.java Wed Nov 05 21:15:34 2014 +0100 @@ -0,0 +1,11 @@ +package cz.cvut.fit.swing.calipel.printer; + +import cz.cvut.fit.swing.calipel.core.BenchmarkResult; + +public class StdOutPrinter extends Printer { + + public void printResult(BenchmarkResult result) { + System.out.println(result); + } + +}