Optimizing the vector math

Discuss issues specific the Scala port of Box2D
Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Wed Jul 08, 2009 1:14 pm

BorisTheBrave wrote:I'm telling you, move some of the burden onto the programmer. Require immutable vectors and matrices, and single static assignment, and it should be a doddle compared with what you are attempting.


I think you're right. If I'm making it more complex, it's going to be a real pain to add 3D later. I'm going to do some refactoring anyway though -- basically I ended up with the bulk of the code being one huge chain of nested pattern matches. I can't easily avoid that, but I'm moving some implementation to separate classes (separating them by Vector2, Matrix22 etc. where possible so Vector3 and so on can be added later)

Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Thu Jul 09, 2009 2:17 pm

Villane wrote:huge chain of nested pattern matches


Turns out it is not that good an idea to do a lot of nested patterns. I've happened on at least one bug in Scala's pattern matcher. They will all hopefully be fixed in 2.8 though. There are workarounds, so I will use those for now.

Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Fri Jul 10, 2009 3:25 pm

I've completed most of the refactoring now and actually adding support for more complex cases is easier now. As well as adding support for new types such as Vector3 and Matrix33. I'm not sure if the current version will be the final design (I don't really know much about compilers actually and maybe I will learn something better :)), but for now I'm happy with it.

I'm pretty sure it can now correctly optimize some complex expressions, and where it suspects the expression may contain mutable things, it will not reuse the cache variables.

This is a pretty contrived example, just to show off some things (length of mutable v is re-computed as required, v1-(2.0,2.0) is cached, for v1.unit, only the length of v1 is cached)

Code: Select all

--- ORIGINAL SOURCE ---
def selectNormalize(v1: org.villane.vecmath.Vector2): org.villane.vecmath.Vector2 = {
  var v: org.villane.vecmath.Vector2 = v1;
  val b: org.villane.vecmath.Vector2 = v.unit;
  val c: org.villane.vecmath.Vector2 = v.unit;
  v = v1.-(new org.villane.vecmath.Vector2(2.0, 2.0)).unit;
  v = v1.unit;
  val d: org.villane.vecmath.Vector2 = v.unit;
  d
}
--- OPTIMIZED SOURCE ---
def selectNormalize(v1: org.villane.vecmath.Vector2): org.villane.vecmath.Vector2 = {
  var v: org.villane.vecmath.Vector2 = v1;
  <synthetic> var v$length: Float = Preamble.sqrt(v.x.*(v.x).+(v.y.*(v.y)));
  final <synthetic> val b$x: Float = v.x./(v$length);
  final <synthetic> val b$y: Float = v.y./(v$length);
  final <synthetic> val c$x: Float = v.x./(v$length);
  final <synthetic> val c$y: Float = v.y./(v$length);
  final <synthetic> val $anon$v0$x: Float = v1.x.-(2.0);
  final <synthetic> val $anon$v0$y: Float = v1.y.-(2.0);
  final <synthetic> val $anon$v0$length: Float = Preamble.sqrt($anon$v0$x.*($anon$v0$x).+($anon$v0$y.*($anon$v0$y)));
  v = new org.villane.vecmath.Vector2($anon$v0$x./($anon$v0$length), $anon$v0$y./($anon$v0$length));
  val $anon$length1: Float = Preamble.sqrt(v1.x.*(v1.x).+(v1.y.*(v1.y)));
  v = new org.villane.vecmath.Vector2(v1.x./($anon$length1), v1.y./($anon$length1));
  v$length = Preamble.sqrt(v.x.*(v.x).+(v.y.*(v.y)));
  final <synthetic> val d$x: Float = v.x./(v$length);
  final <synthetic> val d$y: Float = v.y./(v$length);
  new org.villane.vecmath.Vector2(d$x, d$y)
}


And here it correctly does not reuse a cached expression:

Code: Select all

def mutableExprLength(v1: org.villane.vecmath.Vector2, h: test.Test2.MutHolder): Float = {
  val n: Float = v1.-(h.v).length;
  h.v_=(new org.villane.vecmath.Vector2(7.0, 7.0));
  val m: Float = v1.-(h.v).length;
  n.-(m)
}
--- OPTIMIZED SOURCE ---
def mutableExprLength(v1: org.villane.vecmath.Vector2, h: test.Test2.MutHolder): Float = {
  final <synthetic> val $anon$v0$x: Float = v1.x.-(h.v.x);
  final <synthetic> val $anon$v0$y: Float = v1.y.-(h.v.y);
  final <synthetic> val $anon$v0$length: Float = Preamble.sqrt($anon$v0$x.*($anon$v0$x).+($anon$v0$y.*($anon$v0$y)));
  val n: Float = $anon$v0$length;
  h.v_=(new org.villane.vecmath.Vector2(7.0, 7.0));
  final <synthetic> val $anon$v1$x: Float = v1.x.-(h.v.x);
  final <synthetic> val $anon$v1$y: Float = v1.y.-(h.v.y);
  final <synthetic> val $anon$v1$length: Float = Preamble.sqrt($anon$v1$x.*($anon$v1$x).+($anon$v1$y.*($anon$v1$y)));
  val m: Float = $anon$v1$length;
  n.-(m)
}

And later I might add some immutability analysis (although probably not unless Scala itself will support it) so if h.v would be immutable, the temporary variables can be reused.

Now I will finish the refactoring ( a few small things still to do ) and then try to apply this to a larger part of Box2D

Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Sat Jul 18, 2009 6:03 am

Hmm... ran into a strange issue. Maybe there's something really plain I'm not seeing here. Here are non-scalarized & scalarized versions of two expressions. For some reason, the second causes a test to be much slower and have lots of more vector creations. I can't really see how more vectors could get created here, though... Can anyone see something I might be missing?

Code: Select all

// xf2 is a Transform, vertices2 is an array of vectors

// non-scalarized
xf2 * vertices2(i1)
xf2 * vertices2(i2)

// scalarized
new Vector2(
  xf2.pos.x + xf2.rot.a11 * vertices2(i1).x + xf2.rot.a12 * vertices2(i1).y,
  xf2.pos.y + xf2.rot.a21 * vertices2(i1).x + xf2.rot.a22 * vertices2(i1).y
)
new Vector2(
  xf2.pos.x + xf2.rot.a11 * vertices2(i2).x + xf2.rot.a12 * vertices2(i2).y,
  xf2.pos.y + xf2.rot.a21 * vertices2(i2).x + xf2.rot.a22 * vertices2(i2).y
)

Note that I'm working on skipping scalarization for expressions like this: I think there is no improvement here, as they create a new vector in any case and normal inlining at compile time or by JIT should have the same result.

Oh, and these expressions in context:

Code: Select all

// original (last statement of PolygonCollider.findIncidentEdge)
  scala.List.apply[org.villane.box2d.collision.PolygonCollider.ClipVertex](new org.villane.box2d.collision.PolygonCollider.ClipVertex(xf2.*(vertices2.apply(i1)), new org.villane.box2d.collision.ContactID(edge1, i1, 0, false)), new org.villane.box2d.collision.PolygonCollider.ClipVertex(xf2.*(vertices2.apply(i2)), new org.villane.box2d.collision.ContactID(edge1, i2, 1, false)))

// scalarized
  scala.List.apply[org.villane.box2d.collision.PolygonCollider.ClipVertex](new org.villane.box2d.collision.PolygonCollider.ClipVertex(new org.villane.vecmath.Vector2(xf2.pos.x.+(xf2.rot.a11.*(vertices2.apply(i1).x).+(xf2.rot.a12.*(vertices2.apply(i1).y))), xf2.pos.y.+(xf2.rot.a21.*(vertices2.apply(i1).x).+(xf2.rot.a22.*(vertices2.apply(i1).y)))), new org.villane.box2d.collision.ContactID(edge1, i1, 0, false)), new org.villane.box2d.collision.PolygonCollider.ClipVertex(new org.villane.vecmath.Vector2(xf2.pos.x.+(xf2.rot.a11.*(vertices2.apply(i2).x).+(xf2.rot.a12.*(vertices2.apply(i2).y))), xf2.pos.y.+(xf2.rot.a21.*(vertices2.apply(i2).x).+(xf2.rot.a22.*(vertices2.apply(i2).y)))), new org.villane.box2d.collision.ContactID(edge1, i2, 1, false)))


[edit] This also happens if I'll do this replacement manually and don't compile with the optimizer.

Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Tue Jul 28, 2009 12:33 pm

Just letting you know I'm still working on it. Had some busy time at work and my brain was too fried for working on this at home.

I'm getting pretty close to being able to run this on all of ScalaBox2D, but I'm getting some errors that happen in later compile phases, especially where anonymous functions are involved. I think I lack some fundamental understanding on how a Scala transformer should work so I've made errors that show up only in some cases which I hadn't tested earlier.

I may ask for some help on the scala-tools list, but the people who know much about the compiler are probably super busy.

Happened on some nice surprises among the errors too:

Code: Select all

--- ORIGINAL SOURCE ---
def testTupleOp(): org.villane.vecmath.Vector2 = {
  val v: org.villane.vecmath.Vector2 = org.villane.vecmath.Preamble.tuple2fToVector2(new (Float, Float)(1.0, 2.0)).+(org.villane.vecmath.Preamble.tuple2fToVector2(new (Float, Float)(3.0, 4.0)));
  v
}
--- OPTIMIZED SOURCE ---
def testTupleOp(): org.villane.vecmath.Vector2 = {
  final <synthetic> val v$x: Float = 4.0;
  final <synthetic> val v$y: Float = 6.0;
  new org.villane.vecmath.Vector2(v$x, v$y)
}
--- END ---

I thought I was only eliminating the Tuple To Vector conversion but after that the compiler even decided to eliminate the + operation on two literals.

wjordan
Posts: 3
Joined: Wed Aug 12, 2009 11:55 am

Re: Optimizing the vector math

Postby wjordan » Wed Aug 12, 2009 12:33 pm

Just wanted to drop in and say that it sounds like you're up to some really awesome experimental automated low-level optimization techniques here. I probably couldn't offer any real help without digging deep into the details of it all, so for now all you get is encouragement and my hopes that it all comes together and pays off nicely in the end :D

Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Sun Dec 13, 2009 3:47 pm

Hi. I haven't worked on ScalaBox2D for a while, but I want to return to it in the beginning of the new year.

However, I think I'm going to put this particular optimization work aside for a while, for two reasons. The first is that updating the vector library is going to become difficult if I also have to update the optimizer (it's not general enough to adapt automatically). And I don't know what changes Scala 2.8 would require me to make. The second is that the optimizer code is still quite brittle, even after a few refactorings. I could simplify it at the cost of additional requirements for user code, but then the user code would become brittle, which is even worse.

I may continue with this someday, but I'm not sure when. Maybe when Scala 2.8 is stable... or maybe JVM optimizations will render this whole work unnecessary (I hope :))

toucansam
Posts: 356
Joined: Mon Jun 08, 2009 12:21 pm
Contact:

Re: Optimizing the vector math

Postby toucansam » Sat Jan 09, 2010 11:38 pm

Villane wrote:...or maybe JVM optimizations will render this whole work unnecessary (I hope :))


sigh....

fictiveLaark
Posts: 14
Joined: Mon Apr 26, 2010 4:18 am

Re: Optimizing the vector math

Postby fictiveLaark » Sat Jul 03, 2010 4:33 am

I likely know less than anyone else here about this subject but I had a suggestion, as a compromise between immutability and clean math perhaps you could cache your vectors. The obvious problem with that is that this cache will eat up a lot of memory, but Java does provide a SoftReference class that wraps a reference and only allows the garbage collector to trash your reference if a OutOfMemoryException is about to be thrown. I had in mind a class that maps long values( key = x-corrdinate << 32 & y-coordinate) to Vector wrapping SoftReference instances.

toucansam
Posts: 356
Joined: Mon Jun 08, 2009 12:21 pm
Contact:

Re: Optimizing the vector math

Postby toucansam » Mon Jul 05, 2010 7:18 pm

Pooling (caching) objects is definitely the way to go for java ports, that's what I've been working on for a while.


Return to “Scala”



Who is online

Users browsing this forum: No registered users and 2 guests