Jon said:
Following recent discussions here about benchmarking and when Java's
performance is worst, I proposed the idea of symbolic computation because
this entails very high allocation rates for short-lived objects when
written in an idiomatic functional style and Java should be uniquely bad at
this. While you might be able to work around the functional style using
imperative constructs, it will be extremely tedious and error-prone for
such applications.
So, perhaps someone would like to translate this simple symbolic simplifier
into Java:
http://www.lambdassociates.org/studies/study10.htm
[[CAVEAT: hacked together over a lunchtime or so, in no way any
official statement of anything from anyone, etc.]]
OK, my broken-handed implementation running on a 3.06GHz Xeon with 2GB
memory (not that that matters much, since the JVM is only using the
default which is more like 64M) using FC5 with
Java(TM) SE Runtime Environment (build 1.6.0-b105)
Java HotSpot(TM) Client VM (build 1.6.0-b105, mixed mode, sharing)
and running (of course) with -server takes 2.498s, 2.94s, 3.002s,
for the 10000000-times loop (ie neglecting start-up times, which
according to `time` are about 0.2s). I don't know why there's so
much variability in the reported times.
Drat. OK, those times are using BigDecimal, not BigInteger, which
gets me 3.258s, 3.281s, 3.207s as the loop times. (Using plain
`int` gets those times down to 1.986s, 1.62s, 1.987s, as a measure
of the work done by the big-integer arithmetics.)
-server about halves the runtime. My initial -server-free code took
about 9s [with BigDecimal], but some straightforward optimisation work
(none of which comes close to the obvious caching cheat; just reordering
the tests and ensuring that the important values 0 and 1 were testable
with ==) reduced that.
I tried the obvious tactic of going for double-dispatches to avoid
multiple consecutive instanceof tests, but that made it /slower/,
perhaps because hotspot couldn't collapse code across method
boundaries? I don't really mind because in this case the multiple
dispatches made the code rather more long-winded than it already
was.
Count the line-size yourselves and subtract lines you deem not
relevant to the benchmark.
;;; -- code starteth here ----------------------------------
package temp;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertSame;
import java.math.BigDecimal;
import java.util.StringTokenizer;
import org.junit.Test;
/*
let rec ( +: ) f g = match f, g with
| `Int n, `Int m -> `Int (n +/ m)
| `Int (Int 0), e | e, `Int (Int 0) -> e
| f, `Add(g, h) -> f +: g +: h
| f, g -> `Add(f, g)
let rec ( *: ) f g = match f, g with
| `Int n, `Int m -> `Int (n * / m)
| `Int (Int 0), e | e, `Int (Int 0) -> `Int (Int 0)
| `Int (Int 1), e | e, `Int (Int 1) -> e
| f, `Mul(g, h) -> f *: g *: h
| f, g -> `Mul(f, g)
let rec simplify = function
| `Int _ | `Var _ as f -> f
| `Add (f, g) -> simplify f +: simplify g
| `Mul (f, g) -> simplify f * : simplify g
*/
public class SimplifyViaInstanceOf
{
@test public void ensureParseCompleteConstants()
{
assertSame( zero, parse( "0" ) );
assertSame( one, parse( "1" ) );
assertEquals( new Val( new BigDecimal( "17" ) ), parse( "17" ) );
assertEquals( new Val( new BigDecimal( "1234567890" ) ), parse( "1234567890" ) );
}
@test public void ensureParseCompleteNames()
{
assertEquals( new Sym( "x" ), parse( "x" ) );
assertEquals( new Sym( "y" ), parse( "y" ) );
assertEquals( new Sym( "calico" ), parse( "calico" ) );
assertEquals( new Sym( "whoot" ), parse( "whoot" ) );
}
@test public void ensureParseSimpleExpression()
{
assertEquals( new Add( new Sym( "x" ), new Sym( "y" ) ), parse( "(x+y)" ) );
assertEquals( new Add( one, new Sym( "y" ) ), parse( "(1+y)" ) );
assertEquals( new Add( zero, new Sym( "y" ) ), parse( "(0+y)" ) );
assertEquals( new Add( new Sym( "x" ), zero ), parse( "(x+0)" ) );
assertEquals( new Mul( new Sym( "x" ), new Sym( "y" ) ), parse( "(x*y)" ) );
assertEquals( new Mul( new Sym( "z" ), zero ), parse( "(z*0)" ) );
assertEquals( new Mul( zero, new Sym( "x" ) ), parse( "(0*x)" ) );
}
@test public void ensureParseCompoundExpression()
{
assertEquals( new Mul( parse( "(x+y)" ), one ), parse( "((x+y)*1)" ) );
assertEquals( new Mul( parse( "(x+y)" ), zero ), parse( "((x+y)*0)" ) );
assertEquals( new Mul( parse( "(x+y)" ), new Sym( "x" ) ), parse( "((x+y)*x)" ) );
assertEquals( new Mul( parse( "(x+y)"), parse( "(0*1)" ) ), parse( "((x+y)*(0*1))" ) );
}
private Exp parse( String string )
{
StringTokenizer st = new StringTokenizer( string, "+*()", true );
return parse( st, st.nextToken() );
}
private Exp parse( StringTokenizer st, String current )
{
char ch = current.charAt(0);
if (ch == '(')
{
Exp L = parse( st, st.nextToken() );
ch = st.nextToken().charAt( 0 );
Exp R = parse( st, st.nextToken() );
String ket = st.nextToken();
if (!ket.equals( ")" )) throw new RuntimeException( "ket needed: " + ket );
return ch == '*' ? new Mul( L, R ) : new Add( L, R );
}
else if (Character.isDigit( ch ))
return Val.create( new BigDecimal( current ) );
else if (current.equals( "*" ) || current.equals( "+" ) || current.equals( " )" ))
throw new RuntimeException( "misplaced punctuation: " + current );
else
return new Sym( current );
}
@test public void ensureSimplifiesAddZero()
{
assertEquals( parse( "x" ), parse( "(x+0)" ).simplify() );
assertEquals( parse( "x" ), parse( "(0+x)" ).simplify() );
}
@test public void ensureAddsLiterals()
{
assertEquals( parse( "3" ), parse( "(1+2)" ).simplify() );
assertSame( zero, parse( "0+0" ).simplify() );
}
@test public void ensureMultipliesLiterals()
{
assertEquals( parse( "15" ), parse( "(5*3)" ).simplify() );
assertSame( zero, parse( "(0*0)" ).simplify() );
assertSame( zero, parse( "(x*0)" ).simplify() );
assertSame( zero, parse( "(0*y)" ).simplify() );
}
@test public void ensureSimplifiesMulZero()
{
assertSame( zero, parse( "(x*0)" ).simplify() );
assertSame( zero, parse( "(0*x)" ).simplify() );
}
@test public void ensureSimplifiesMulOne()
{
assertEquals( parse( "x" ), parse( "(x*1)" ).simplify() );
assertEquals( parse( "x" ), parse( "(1*x)" ).simplify() );
}
@test public void ensureLeftAssociatesAdds()
{
assertEquals( parse( "((x+y)+z)" ), parse( "(x+(y+z))" ).simplify() );
}
@test public void ensureLeftAssociatesMuls()
{
assertEquals( parse( "((x*y)*z)" ), parse( "(x*(y*z))" ).simplify() );
}
static abstract class Exp
{
abstract Exp simplify();
}
static final Val zero = new Val( BigDecimal.ZERO );
static final Val one = new Val( BigDecimal.ONE );
static class Val extends Exp
{
final BigDecimal val;
Val( BigDecimal val ) { this.val = val; }
Exp simplify() { return this; }
public String toString() { return val.toString(); }
public boolean equals( Object other )
{ return other instanceof Val && val.equals( ((Val) other).val ); }
public static Exp create( BigDecimal d )
{ return d.equals( BigDecimal.ZERO ) ? zero : d.equals( BigDecimal.ONE ) ? one : new Val( d ); }
}
static class Sym extends Exp
{
String name;
Sym( String name ) { this.name = name; }
Exp simplify() { return this; }
public boolean equals( Object other )
{ return other instanceof Sym && name.equals( ((Sym) other ).name ); }
public String toString() { return name; }
}
static abstract class Inf extends Exp
{
final Exp L, R;
Inf( Exp L, Exp R ) { this.L = L; this.R = R; }
}
static class Add extends Inf
{
Add( Exp L, Exp R ) { super( L, R ); }
Exp simplify()
{
return sum( L.simplify(), R.simplify() );
}
private Exp sum( Exp sL, Exp R )
{
if (sL ==zero) return R;
if (R == zero) return sL;
if (sL instanceof Val && R instanceof Val) return Val.create( ((Val) sL).val.add( ((Val) R).val ) );
if (R instanceof Add) return sum( sum( sL, ((Add) R).L ), ((Add) R).R );
return new Add( sL, R );
}
public String toString() { return "(" + L + " + " + R + ")"; }
public boolean equals( Object other )
{ return other instanceof Add && same( (Add) other ); }
private boolean same( Add other )
{ return L.equals( other.L ) && R.equals( other.R ); }
}
static class Mul extends Inf
{
Mul( Exp L, Exp R ) { super( L, R ); }
Exp simplify(){ return prod( L.simplify(), R.simplify() ); }
private Exp prod( Exp L, Exp R )
{
if (L == zero || R ==zero) return zero;
if (L == one) return R;
if (R == one) return L;
if (L instanceof Val && R instanceof Val) return Val.create( ((Val) L).val.multiply( ((Val) R).val ) );
if (R instanceof Mul) return prod( prod( L, ((Mul) R).L ), ((Mul) R).R );
return new Mul( L, R );
}
public String toString() { return "(" + L + " * " + R + ")"; }
public boolean equals( Object other )
{ return other instanceof Mul && same( (Mul) other ); }
private boolean same( Mul other )
{ return L.equals( other.L ) && R.equals( other.R ); }
}
public static void main( String [] args )
{
// [* x [+ [+ [* 12 0] [+ 23 8]] y]]
Exp a28_8 = new Add( Val.create( new BigDecimal( 23 ) ), Val.create( new BigDecimal( 8 ) ) );
Exp m12_0 = new Mul( Val.create( new BigDecimal( 12 ) ), Val.create( new BigDecimal( 0 ) ) );
Exp aAB = new Add( m12_0, a28_8 );
Exp aABY = new Add( aAB, new Sym( "y" ) );
Exp it = new Mul( new Sym( "x" ), aABY );
Exp itx = new SimplifyViaInstanceOf().parse( "(x*(((12*0)+(23+8))+y))" );
System.err.println( ">> original expression: " + it );
System.err.println( ">> original expression: " + itx );
System.err.println( ">> simplified expression: " + itx.simplify() );
long base = System.currentTimeMillis();
for (int i = 0; i < 10000000; i += 1) it.simplify();
long after = System.currentTimeMillis();
System.err.println( ">> took " + (after - base)/1000.0 + "s" );
}
}
